[AL] 거품 정렬 (Bubble Sort) - JavaScript

Bubble Sort 란

Bubble Sort (거품 정렬)란 서로 인접한 두 수를 비교하여 더 큰 수를 뒤로 보내서 전체 배열을 오름차순으로 정렬하는 정렬 알고리즘 간단한 알고리즘에 속한다.

(값들의 이동이 거품이 수면에 올라오는 것과 같은 모습을 해서 이런 이름이 되었다고 한다.)

사진 출처

사진을 보면 알 수 있듯이 한차례 정렬이 끝나게 되면 배열에서 가장 큰 값이 맨 오른쪽, 즉 맨 끝으로 이동하는 것을 확인 할 수 있다. 이렇게 반복할때마다 그다음으로 큰 값이 우측으로 이동하는 형태를 띄고 있는 알고리즘이다.

Bubble Sort 코드

const bubbleSort = (arr) => {
  var len = arr.length;
  var i, j;
  
  for(i=0; i<len-1; i++){	// 전체 사이클
    for(j=0; j<len-1-i; j++){	// 끝까지 돌면서 정렬 진행 (-i 를 통해 마지막 배열은 제외)
      if(arr[j]>arr[j+1]){	// 인접한 두 수를 비교했을때, 앞수가 더 크면 교환
        [arr[j], arr[j+1]] = [arr[j+1],arr[j]];
      }
    }
  }
  return arr;
}

bubbleSort([3,1,6,9,2,4]);
// [1, 2, 3, 4, 6, 9]

Bubble Sort 장단점

• 장점
  - 구현이 간단하다.
• 단점
  - 정렬 시간이 오래걸린다.
  - 특정 요소가 이미 최종 정렬 위치에 있는 경우에도 교환이 일어나는 경우가 존재한다.
  - 한 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하는 경우에는 다른 요소들과 다 교환되어야 한다.
  

간단하지만 그에 비해 어마무시한 단점 때문에 실제로는 잘 사용하지 않는 정렬 알고리즘이다!

Bubble Sort 시간 복잡도

Worst	Best	Avg
$n^2$	$n$ (이미 정렬된 경우)	$n^2$

참고 자료