정렬 알고리즘 - 버블 정렬 알고리즘

정렬 알고리즘은 배열과 같은 컬렉션 내의 항목을 재배열하는 과정을 말한다. 정렬 알고리즘은 여러 종류가 있는데, 버블 정렬 알고리즘에 대해 정리해 보자.

버블 정렬 (Bubble Sort)

버블 정렬은 가장 비효율적인 정렬 방식 중 하나로, 실제로는 잘 사용되지 않는다.

버블 정렬은 아래와 같은 방식으로 동작한다.

1. 두 인접한 값을 비교한다.
2. 앞에 있는 값이 뒤에 있는 값보다 크면 두 값의 위치를 바꾼다.
3. 위 과정을 배열이 정렬될 때까지 반복한다.

작동 방식은 아래 링크에서 시각화된 차트를 통해 확인할 수 있다.

버블 정렬 시각화 차트

버블 정렬 코드

const bubbleSort = (arr) => {
  let noSwaps;
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
    noSwaps = false;
  }

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

console.log(bubbleSort([1, 2, 3, 10, 5, 6])); // [1, 2, 3, 5, 6, 10]

버블 정렬은 최적화되지 않은 경우 이미 정렬된 배열에서도 모든 요소를 비교한다. 이를 최적화하기 위해 noSwaps 변수를 사용할 수 있다. noSwaps 변수는 배열을 한 번 순회하는 동안 요소의 교환이 발생했는지를 체크한다.

• 배열의 요소를 하나씩 비교하여 교환이 발생하면 noSwaps를 false로 설정한다.
• 만약 교환이 발생하지 않았다면 배열이 이미 정렬된 상태이므로 반복을 중단하기 위해 break를 사용한다.

이 최적화를 통해 불필요한 반복을 줄여 알고리즘의 효율성을 높일 수 있다.

시간복잡도

버블 정렬은 일반적으로는 O(n²)의 복잡도를 가진다. 배열이 거의 정렬된 상태이고, noSwap을 사용한 경우에는 O(n)의 복잡도를 가진다.