[정렬 알고리즘] #2. 버블 정렬(Bubble Sort)

버블 정렬을 이용해서 오름차순으로 정렬한다면 인접한 두 수를 비교하여 작은 수 를 앞으로 보내면 된다. 내림차순으로 정렬한다면 큰 수를 앞으로 보내면 된다. 이렇게 배열을 한 번 순회할 때마다 마지막 원소가 정렬되는 모습이 거품이 수면 위로 올라가는 모습과 같다고 하여 버블 정렬이라고 한다.

알고리즘은 단순하지만 상당히 비효율적이다. 전체 원소의 개수가 n개 일때, 각 순회 때마다 n-1, n-2,..., 2 ,1번 비교 및 자리 교체가 이루어지기 때문에 시간 복잡도는 O(n²)가 된다.

 

구현 방법 (javascript)

function bubbleSort(arr){
  for(let i = 0; i < arr.length; i++){
    for(let j = 0; j < arr.length - 1 - i; j++){
      if(arr[j] > arr[j+1]){
        const temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
  }
  for(let i = 0; i < arr.length; i++){
  	console.log(arr[i]);
  }
}