정렬 알고리즘 비교: 버블, 선택, 삽입

"그냥 sort() 쓰면 안 되나요?"

처음 JavaScript를 배울 때, 나는 Array.prototype.sort()가 얼마나 편한지 몰랐다. 그냥 배열에 .sort()만 붙이면 정렬이 됐다. 하지만 시니어가 물었다.

"그 sort() 내부는 어떻게 동작하나요?"

나는 멍하니 있었다. 내부가 뭔데? 그냥 정렬해주는 거 아니야?

그때 깨달았다. 나는 도구를 쓸 줄만 알았지, 원리는 전혀 몰랐다. 정렬 알고리즘을 이해해야 더 복잡한 알고리즘(Quick Sort, Merge Sort)도 이해할 수 있고, 언제 어떤 알고리즘이 유리한지도 판단할 수 있다.

첫 번째 좌절 - 버블 정렬의 비효율

정렬의 가장 기본이 뭐냐고 물었을 때, 선배가 버블 정렬을 알려줬다. 개념은 간단했다.

"인접한 두 수를 비교해서, 큰 수를 뒤로 보낸다."

마치 물속의 거품(bubble)이 위로 떠오르듯이, 큰 수가 배열의 끝으로 하나씩 이동한다. 나는 금방 구현했다.

function bubbleSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

한 번 순회할 때마다 가장 큰 수가 맨 뒤에 고정된다. 하지만 문제가 있었다. 너무 느렸다.

배열 크기가 100개만 되어도 눈에 띄게 느려졌다. 이중 루프니까 시간복잡도는 O(N²). 1만 개 배열이면? 1억 번 비교한다.

"실제에선 절대 안 써요." 선배가 단호하게 말했다.

선택 정렬 - "가장 작은 걸 콕 집어서"

버블 정렬이 너무 비효율적이라 다른 방법을 찾았다. 선택 정렬(Selection Sort)은 개념이 직관적이었다.

"전체를 훑어서 가장 작은 수를 찾는다. 그리고 맨 앞과 바꾼다."

카드 한 무더기를 펼쳐놓고, 가장 작은 카드를 골라서 맨 앞에 놓는다. 그 다음엔 나머지에서 가장 작은 걸 또 골라서 두 번째 자리에 놓는다. 이 과정을 반복하면 정렬이 된다.

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    // 최소값의 인덱스 찾기
    let minIndex = i;

    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // 최소값을 현재 위치와 교환
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

선택 정렬의 장점은 교환 횟수가 적다는 것이다. 버블 정렬은 인접한 요소를 계속 바꾸지만, 선택 정렬은 한 번의 순회마다 딱 한 번만 바꾼다. 교환 연산이 비싼 경우(예: 큰 객체를 복사하는 경우) 유리할 수 있다.

하지만 시간복잡도는 여전히 O(N²)이다. 최선, 평균, 최악 모두 O(N²)이다. 정렬되어 있어도 매번 최소값을 찾으려고 전체를 훑어야 하기 때문이다.

깨달음 - 삽입 정렬의 적응성

세 번째로 배운 건 삽입 정렬(Insertion Sort)이었다. 이건 비유가 명확했다.

"카드를 한 장씩 뽑아서, 이미 정렬된 카드들 사이에 적절한 위치에 끼워 넣는다."

포커를 칠 때 카드를 정리하는 방식과 똑같다. 왼손에 이미 정렬된 카드들을 들고 있고, 오른손으로 새 카드를 한 장씩 뽑아서 왼손의 적절한 위치에 끼워 넣는다.

function insertionSort(arr) {
  const n = arr.length;

  for (let i = 1; i < n; i++) {
    let key = arr[i]; // 현재 뽑은 카드
    let j = i - 1;

    // key보다 큰 요소들을 오른쪽으로 이동
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

    // key를 적절한 위치에 삽입
    arr[j + 1] = key;
  }

  return arr;
}

삽입 정렬의 진짜 강점은 이미 거의 정렬되어 있는 데이터에 대해 엄청나게 빠르다는 것이다. 만약 배열이 이미 정렬되어 있다면? 각 요소는 딱 한 번만 비교하고 넘어간다. 시간복잡도가 O(N)으로 떨어진다.

이걸 "적응적(adaptive)" 알고리즘이라고 한다. 이 특징 때문에 삽입 정렬은 실제로도 꽤 자주 쓰인다.

실제 적용 - 언제 O(N²) 알고리즘을 쓸까?

이론은 알겠는데, 실제로 언제 써먹을까? 선배가 재밌는 사실을 알려줬다.

"Python의 sorted()와 Java의 Arrays.sort()는 내부적으로 삽입 정렬을 사용한다."

정확히 말하면 TimSort라는 하이브리드 알고리즘을 쓴다. TimSort는 전체 데이터를 작은 덩어리(Run)로 나누는데, 덩어리가 32개 이하라면 삽입 정렬로 정렬해버린다.

왜냐하면:

1. 작은 데이터셋(N < 64)에서는 퀵 정렬이나 병합 정렬의 오버헤드(재귀 호출 등)가 더 크다.
2. 삽입 정렬은 오버헤드가 거의 없고, 메모리 접근 패턴이 순차적이라 캐시 효율이 좋다.
3. 실제 데이터는 "완전히 무작위"인 경우보다 "부분적으로 정렬된" 경우가 많다. 이럴 때 삽입 정렬이 매우 빠르다.

그래서 무조건 "퀵 정렬이 최고야"라고 말하는 건 하수다. 데이터의 크기와 상태에 따라 최적의 알고리즘은 달라진다.

전체 비교 테이블

알고리즘	최선	평균	최악	공간복잡도	안정성	적응성	특징
버블 정렬	O(N)	O(N²)	O(N²)	O(1)	안정	적응적	구현 쉬움, 너무 느림
선택 정렬	O(N²)	O(N²)	O(N²)	O(1)	불안정	비적응적	교환 적음, 항상 느림
삽입 정렬	O(N)	O(N²)	O(N²)	O(1)	안정	적응적	작은 데이터/부분 정렬 시 최고

퀵 정렬(Quick Sort) vs 병합 정렬(Merge Sort) 더 알아보기

실제로 O(N log N)이 필요할 때, 우리는 보통 언어 내장 함수를 씁니다. 하지만 실무에서는 이 둘의 차이를 알아야 합니다.

1. 퀵 정렬 (Quick Sort):
   • 장점: 추가 메모리가 거의 필요 없음(In-place sort). 평균적으로 가장 빠름(캐시 히트율 높음).
   • 단점: 최악의 경우(이미 정렬된 경우 등) O(N²)으로 느려짐. 불안정 정렬(Unstable).
2. 병합 정렬 (Merge Sort):
   • 장점: 언제나 O(N log N) 보장. 안정 정렬(Stable).
   • 단점: 추가 메모리(N)가 필요함.

결론: 메모리가 충분하고 안정성이 중요하다면 병합 정렬(Java, Python의 TimSort 기반), 메모리가 부족하거나 일반적인 속도가 중요하다면 퀵 정렬(C++, Go 등)이 선호됩니다.

---

"Can't we just use sort()?"

When I first learned JavaScript, I didn't appreciate how convenient Array.prototype.sort() was. Just slap .sort() on an array and boom, sorted. But then an interviewer asked me:

"How does sort() work internally?"

I stared blankly. Internally? It just... sorts stuff, right?

That's when I realized: I knew how to use the tool, but I had zero understanding of the principles. Understanding sorting algorithms is the foundation for grasping more complex algorithms (Quick Sort, Merge Sort) and knowing when each approach shines.

First Struggle: Bubble Sort's Inefficiency

When I asked what the most basic sorting algorithm was, a senior dev showed me Bubble Sort. The concept was straightforward.

"Compare adjacent elements and push the larger one backward."

Like bubbles rising in water, larger numbers float to the end of the array one by one. I implemented it quickly.

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

Each pass fixes the largest unsorted element at the end. But there was a problem: it was painfully slow.

Even 100 elements made the difference noticeable. Nested loops mean O(N²) time complexity. 10,000 elements? 100 million comparisons.

"Never use this in production," my senior said firmly.

Selection Sort: "Pick the smallest one"

Bubble Sort's inefficiency led me to Selection Sort. The concept was intuitive.

"Scan the entire array, find the smallest element, and swap it with the first position."

Imagine spreading cards on a table, picking the smallest card, and placing it first. Then pick the next smallest and place it second. Repeat until sorted.

function selectionSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j;
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

Selection Sort's advantage is fewer swaps. Bubble Sort constantly swaps adjacent elements, but Selection Sort only swaps once per pass. This helps when swap operations are expensive (e.g., copying large objects/writing to Flash memory).

But time complexity is still O(N²). Best, average, worst—all O(N²). Why? Even if the array is sorted, we still scan everything to find the minimum each time.

Aha Moment: Insertion Sort's Adaptiveness

The third algorithm I learned was Insertion Sort. The analogy was crystal clear.

"Pick one card at a time and insert it into the correct position among already-sorted cards."

Exactly like organizing poker cards in your hand. Your left hand holds sorted cards, your right hand picks a new card, and you slide it into the right spot in your left hand.

function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

Insertion Sort's real strength is blazing speed on nearly sorted data. If the array is already sorted, each element only needs one comparison. Time complexity drops to O(N).

This is called an "adaptive" algorithm. Performance varies based on input state.

Real-World Application: When O(N²) Beats O(N log N)

Theory is fine, but when do we actually use this? My senior shared a fascinating fact.

"Python's sorted() and Java's Arrays.sort() use TimSort. And TimSort uses Insertion Sort internally."

TimSort is a hybrid algorithm combining Merge Sort and Insertion Sort. Why mix in Insertion Sort?

Because Insertion Sort is actually faster for small datasets.

Algorithms like Quick Sort and Merge Sort have recursion overhead. For small data (typically 16-64 elements), this overhead can exceed actual sorting time. Insertion Sort has minimal overhead and excellent cache efficiency for small datasets.

So in production libraries, they combine approaches:

1. Divide array into small chunks (runs).
2. Sort chunks using Insertion Sort.
3. Merge chunks using Merge Sort.

Another case is nearly sorted data. Log files, time-series data, sorted arrays with a few new elements added. Here, Insertion Sort approaches O(N) and significantly beats Quick Sort's average O(N log N).

Stability: Why Order Matters

While studying sorting, I encountered "stability". "Does the algorithm preserve the relative order of equal elements?"

Example: Checkin list sorted by Time. Now sort by Name.

• Stable Sort: Alice (10:00), Bob (10:00). If we sort by another criteria, their relative order remains if values are equal.

• Unstable Sort: Their order might flip unpredictably.

• Stable: Bubble, Insertion, Merge

• Unstable: Selection, Quick, Heap

Stability is crucial in UI tables (sorting by multiple columns) and complex database queries.

---

Deep Dive: Quick Sort vs Merge Sort

In production, we use built-in sort functions. In practice, we explain why they are implemented that way.

1. Quick Sort:
   • Pros: Minimal extra memory (In-place). Fastest on average due to cache locality.
   • Cons: Worst case is O(N²). Unstable.
2. Merge Sort:
   • Pros: Guaranteed O(N log N). Stable.
   • Cons: Requires O(N) extra memory.

Verdict: If stability and predictable performance are key (e.g., Python, Java), Merge Sort (or TimSort) is used. If raw speed and memory efficiency matter (e.g., C++, embedded systems), Quick Sort wins.