버블 정렬 (Bubble Sort)

 

 

버블 정렬

버블 정렬(bubble sort)은 인접한 두 수를 비교하여 조건에 맞지 않으면 두 수의 자리를 교환하여 정렬하는 알고리즘입니다.

 

https://visualgo.net/en/sorting

 

오름차순으로 정렬하는 위의 그림을 보면, 첫 번째 데이터와 두 번째 데이터를 비교하여 크기가 큰 데이터를 오른쪽의 자리로 교환하는 것을 볼 수 있습니다. 이후 두 번째와 세 번째, 다시 세 번째와 네 번째 ... 한 칸씩 이동하면서 조건이 맞지 않으면 서로의 자리를 교환합니다. 1회전이 끝나면 가장 큰 수가 맨 뒤에 위치하기 때문에 맨 끝 데이터는 정렬에서 제외됩니다. n회전에서 n개의 데이터가 정렬이 되었다고 판단하기 때문에, 뒤에서 n개의 데이터를 정렬에서 제외합니다.

 

시간 복잡도

버블 정렬은 최악의 경우에 $O(n^2)$의 시간 복잡도를 가집니다. 버블 정렬은 한 번의 회전에 데이터 하나를 제외하기 때문에, 데이터가 n개 일 때, n-1 번의 순회가 필요합니다. 이를 수식으로 나타내면 아래와 같습니다.

$$ (n-1) + (n-2) + ... + 2 + 1 = {n(n-1)} / {2} $$

 

 

 

자바스크립트 코드

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

console.log(bubbleSort([5, 3, 9, 7, 1]));

 

 

장점

• 소스 코드가 직관적이고, 구현이 쉽습니다.
• 제자리 정렬 (in-place sorting), 이미 존재하는 배열 안에서 교환이 이루어 지므로, 다른 메모리 공간이 필요하지 않습니다.

단점

• $O(n^2)$이라는 시간 복잡도로 데이터의 개수가 늘어날수록 성능이 많이 저하됩니다.
• 정렬되어있지 않은 데이터를 교환(swap)하는 연산이 많이 발생합니다.

 

정리

버블 정렬은 직관적인 코드와 쉬운 구현에도 불구하고 잘 사용되지 않습니다. 시간 복잡도로 인해 데이터가 많으면 많을수록 성능이 급격하게 저하됩니다. 그래도 정렬에 대한 기본 개념을 익히기 좋으며, 쉽게 이해할 수 있기 때문에 알아두시면 좋을 것 같습니다! : )