가장 기초적이나 비효율적인 정렬

크리스가 카드 게임을 하려고 카드를 섞었다가 다시 순서대로 정리하고 있다.

그런데 정리하는 방식이 좀 특이하다.

맨 왼쪽부터 카드 두 장만 잡고 비교한다. "왼쪽이 더 크네? 자리 바꿔." 그리고 한 칸 옆으로 이동해서 또 두 장을 비교한다.

이 과정을 끝까지 반복하고, 다시 처음으로 돌아와서 또 반복한다.

"크리스, 뭐 해? 언제 다 정리하려고?"

이것이 바로 정렬 알고리즘의 조상님이자, 가장 비효율적인 정렬 방식인 버블 정렬(Bubble Sort)이다.

1. 거품처럼 떠오른다?

버블 정렬이라는 이름은 데이터가 정렬되는 과정이 마치 "물속에서 거품이 수면 위로 보글보글 떠오르는 모습"과 비슷하다고 해서 붙여졌다.

원리는 아주 단순하다.

"서로 인접한 두 원소를 검사하여, 순서가 잘못되어 있으면 자리를 바꾼다(Swap)."

이 작업을 한 번 순회(Pass) 할 때마다, 가장 큰 숫자가 배열의 맨 뒤(수면 위)로 이동해서 자리를 잡게 된다.

동작 과정 (오름차순 예시: [5, 3, 8, 1])

이 과정을 데이터 개수만큼 반복하면 정렬이 완료된다.

2. 자바스크립트로 구현하기

가장 기본적인 구현 방법은 이중 반복문을 사용하는 것이다.

function bubbleSort(arr) {
  // 뒤에서부터 범위를 줄여나간다 (i는 정렬해야 할 범위의 끝)
  for (let i = arr.length; i > 0; i--) {
    // 처음부터 i-1까지 비교하며 "거품"을 밀어 올린다
    for (let j = 0; j < i - 1; j++) {
      console.log(arr, arr[j], arr[j+1]); // 과정을 눈으로 확인해보자

      if (arr[j] > arr[j + 1]) {
        // SWAP! 구조 분해 할당으로 변수 교환
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

bubbleSort([37, 45, 29, 8]);

3. 성능 분석: 왜 비효율적인가?

이 코드를 빅오 표기법으로 분석해 보자.

데이터가 10개면 100번, 1,000개면 100만 번 연산한다. 데이터가 조금만 늘어나도 성능이 기하급수적으로 나빠진다. 정렬 알고리즘 중에서도 최하위권 성능이다.

4. 최적화: 멍청함을 조금 줄이기

만약 데이터가 [1, 2, 3, 5, 4]처럼 거의 정렬된 상태라면 어떨까?

기본 버블 정렬은 이미 정렬이 끝났는데도, 멍청하게 끝까지 비교를 계속한다.

이를 방지하기 위해 noSwaps 변수를 추가할 수 있다. 한 번의 패스 동안 “자리를 바꾼 적이 한 번도 없다"면, 이미 정렬이 끝났다는 뜻이므로 루프를 탈출(break)하면 된다.

// ✅ 최적화된 버블 정렬
function bubbleSortOptimized(arr) {
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
    noSwaps = true; // 일단 정렬됐다고 가정
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        noSwaps = false; // 자리를 바꿨으니 아직 멀었다고 표시
      }
    }
    if (noSwaps) break; // 교환이 없었으면 종료!
  }
  return arr;
}

이렇게 최적화하면, 이미 정렬된 데이터에 한해서는 O(N)에 가까운 놀라운 속도를 보여준다. (물론 평균적으로는 여전히 O(N^2)이다.)

핵심 정리

버블 정렬은 큰 수를 뒤로 밀어내는 방식이었다.

그렇다면 반대로, 가장 작은 수를 찾아서 맨 앞으로 가져오는 방식은 어떨까? 비교 횟수는 비슷하지만, "교환(Swap)" 횟수를 획기적으로 줄인 친구가 있다.

🔗 참고 링크