Sorting (1)

 Graph 단원이 끝나고 이번엔 Sorting이다. 이번 (1)에서는 "비교 기반 정렬의 기초"에 해당하는 Selection-Sort, Insertion-Sort, Heap-Sort를 다루고, Merge-Sort는 (2)에서 단독으로, Quick-Sort와 Stable Sorting은 (3)에서 다룬다.

 

이번 글의 흐름:

• Selection-Sort: "최솟값을 찾아서 옮긴다"는 가장 단순한 방법. 항상 O(n^2)
• Insertion-Sort: "정렬된 부분에 끼워넣는다"는 방법. 입력에 따라 O(n) ~ O(n^2)
• 둘의 핵심 차이: early exit이 가능한가
• Heap-Sort: heap 자료구조를 이용해 "최댓값 찾기"를 O(n)에서 O(log n)으로 줄여서 O(n log n) 달성

---

1. Selection-Sort

1.1 아이디어

매 단계마다, "아직 정렬되지 않은 부분"에서 가장 작은 값을 찾아 정렬된 부분의 바로 다음 자리로 옮긴다(swap). 정렬된 부분은 배열의 앞쪽부터 한 칸씩 늘어난다.

 

1.2 예제

배열 [7,2,9,4,1]을 정렬해보자.

[7,2,9,4,1]   -> 전체에서 최솟값 1(idx4) 찾아서 idx0과 swap -> [1,2,9,4,7]
[1|2,9,4,7]   -> 나머지에서 최솟값 2(idx1, 이미 자리) -> [1,2,9,4,7]
[1,2|9,4,7]   -> 나머지에서 최솟값 4(idx3) 찾아서 idx2와 swap -> [1,2,4,9,7]
[1,2,4|9,7]   -> 나머지에서 최솟값 7(idx4) 찾아서 idx3과 swap -> [1,2,4,7,9]
[1,2,4,7|9]   -> 마지막 원소는 자동으로 자리 -> 완료

 

|는 "정렬된 부분 | 정렬 안 된 부분"의 경계를 나타낸다.

 

1.3 시간복잡도

각 단계에서 "최솟값 찾기"에 필요한 비교 횟수는 (남은 원소 개수 - 1)이다. 배열 크기가 n이면:

(n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2 = O(n^2)

 위 예제(n=5)에서는 4+3+2+1 = 10번의 비교가 발생했다.

 

가장 중요한 포인트: 이 비교 횟수는 입력이 어떤 순서든(이미 정렬돼있어도) 항상 동일하다. "최솟값 찾기"는 남은 부분을 전부 훑어봐야만 "이게 최솟값이다"라고 확신할 수 있기 때문에, 입력 상태와 무관하게 항상 O(n^2)이다.

반면 swap(자리 교환)은 패스당 최대 1번이므로, 전체적으로 최대 n-1번뿐이다.

---

2. Insertion-Sort

2.1 아이디어

배열의 왼쪽부터 "정렬된 부분"을 한 칸씩 늘려나간다. 새로 추가되는 원소를 정렬된 부분 안의 올바른 위치에 "끼워넣을" 때, 자기보다 큰 원소들을 한 칸씩 뒤로 밀면서(shift) 자리를 찾는다.

 

2.2 예제

같은 배열 [7,2,9,4,1]을 Insertion-Sort로 정렬해보자.

[7 | 2,9,4,1]
2 삽입: 7>2 -> 7을 한 칸 밀고 2를 맨앞에 -> [2,7 | 9,4,1]
9 삽입: 7<9 -> 비교 1번으로 끝, 9는 그대로 맨뒤 -> [2,7,9 | 4,1]
4 삽입: 9>4, 7>4 두 개를 밀고, 2<4에서 멈춤 -> [2,4,7,9 | 1]
1 삽입: 9,7,4,2 전부 밀고 맨앞에 -> [1,2,4,7,9]
완료

2.3 Best case와 Worst case

• 새 원소를 끼워넣을 때마다 비교+이동 횟수가 원소마다 다르다. 위 예제에서 9를 넣을 때는 비교 1번, 1을 넣을 때는 비교+이동 4번이 필요했다.
• 이미 정렬된 배열이라면: 매 원소가 "바로 왼쪽 원소보다 크다"는 것만 확인하고 즉시 끝난다 -> 비교 n-1번, O(n) (best case)
• 역순(최악) 배열이라면: 매 원소가 맨 앞까지 밀려간다 -> O(n^2) (worst case)

이렇게 입력 상태에 따라 성능이 달라지는 성질을 adaptive하다고 한다.

---

3. Selection-Sort vs Insertion-Sort - Early Exit의 차이

 두 알고리즘 모두 worst case는 O(n^2)이지만, 이미 정렬된 입력을 줬을 때 Insertion-Sort는 O(n)으로 빨라지는 반면 Selection-Sort는 여전히 O(n^2)이다. 왜 이런 차이가 생길까?

 

핵심은 early exit(조기 종료)이 가능한가이다.

• Insertion-Sort: 새 원소를 왼쪽 원소와 비교해서 "더 크네, 여기가 맞는 자리"라고 판단되면 그 즉시 멈출 수 있다. 더 왼쪽까지 볼 필요가 없다.
• Selection-Sort: "이 값이 남은 부분 중 최솟값이다"라는 걸 확인하려면, 남은 원소를 전부 비교해봐야 한다. 미리 "이게 최솟값이다"라고 알 수 있는 방법이 없으므로 early exit이 불가능하다.

	비교 횟수	swap/shift	adaptive
Selection-Sort	항상 O(n^2)	최대 n-1번	아니오
Insertion-Sort	최선 O(n) ~ 최악 O(n^2)	입력에 따라 다름	예

---

4. Heap-Sort

4.1 Array 기반 Heap 복습

Heap-Sort는 배열을 max-heap으로 다루면서 정렬한다. Array 기반 heap의 핵심 규칙:

• index 0 = 항상 root(최댓값) - 이건 array 기반 heap의 정의 자체이다. 찾는 게 아니라 항상 그 자리에 있어야 한다.
• index i인 노드의 자식은 index 2i+1, 2i+2에 위치한다.
• max-heap property: 모든 노드는 자기 자식보다 크거나 같다.

예를 들어 array = [9,5,7,1]은 다음 트리에 대응된다.

       9        (index0, root)
      / \
     5   7      (index1, index2)
    /
   1            (index3, 5의 자식)

9>=5, 9>=7, 5>=1 이므로 유효한 max-heap이다.

(이 점이 헷갈릴 수 있는데, 만약 array의 index0에 있는 값이 자식보다 작다면 그건 처음부터 max-heap이 아닌 것이다. "root가 무엇인지"를 보고 array를 만드는 게 아니라, array의 index0이 곧 root라는 점을 기억해야 한다.)

 

4.2 알고리즘 - 두 단계

1. Build-heap: 배열 전체를 max-heap으로 변환한다. (bottom-up 방식으로 O(n)에 가능)
2. 반복 (heap 크기가 1이 될 때까지):
   • array[0](root, 현재 heap에서 최댓값)과 array[heap크기-1](현재 heap의 마지막 원소)을 swap
   • heap 크기를 1 줄인다
   • array[0]에 대해 down-heap(sift-down) 수행: 새 root가 max-heap property를 만족하지 않으면, 더 큰 자식과 swap을 반복하며 내려간다. heap의 높이가 O(log n)이므로 down-heap은 O(log n)
     
     

4.3 예제 - 전체 trace

array = [9,5,7,1] (위에서 확인했듯 유효한 max-heap)

 

Step 1: heap크기=4

• swap(array[0]=9, array[3]=1) -> [1,5,7,9]
• heap크기 -> 3 (9는 이제 자기 자리, 즉 정렬 완료 영역으로 확정)
• down-heap(array[0]=1), heap크기3 -> [1,5,7] 범위. 1의 자식은 idx1=5, idx2=7. 더 큰 자식 7과 swap -> [7,5,1,9]. 1은 이제 idx2인데, heap크기3에서 idx2의 자식(idx5,6)은 범위 밖 -> 종료

결과: [7,5,1,9], heap크기=3, 정렬완료=[9]

 

Step 2: heap크기=3

• swap(array[0]=7, array[2]=1) -> [1,5,7,9]
• heap크기 -> 2 (7은 자기 자리로 확정)
• down-heap(array[0]=1), heap크기2 -> [1,5] 범위. 1의 자식은 idx1=5뿐. 1<5 -> swap -> [5,1,7,9]. idx1의 자식(idx3,4)은 범위 밖 -> 종료

결과: [5,1,7,9], heap크기=2, 정렬완료=[7,9]

 

Step 3: heap크기=2

• swap(array[0]=5, array[1]=1) -> [1,5,7,9]
• heap크기 -> 1 (5는 자기 자리로 확정)
• down-heap(array[0]=1), heap크기1 -> 자식 없음 -> 종료

결과: [1,5,7,9], heap크기=1, 정렬완료=[5,7,9]

 

Step 4: heap크기=1 -> 더 진행할 것 없음, 종료

최종 결과: [1,5,7,9] - 정렬 완료!

 

4.4 down-heap이 왜 중요한가 - Selection-Sort와의 연결

 여기서 자연스럽게 떠오르는 질문: "어차피 매 단계마다 root를 끝으로 보내는 건데, 굳이 down-heap으로 다음 최댓값을 매번 array[0]으로 갖다 놓을 필요가 있나?"

 

답은: 그래, 그게 바로 Heap-Sort가 빠른 이유의 핵심이다.

 

만약 down-heap을 하지 않는다면, 다음 차례의 최댓값(예: Step2 시작 시점의 [1,5,7] 중 7)이 어디 있는지 알아내기 위해 heap 영역 전체를 훑어봐야 한다 - 이건 Selection-Sort가 "최솟값 찾기"를 위해 매번 전체를 훑는 것과 똑같은 비용(O(n))이다.

 반면 down-heap을 매번 수행해두면, "다음 최댓값은 항상 array[0]에 있다"는 사실이 항상 보장된다. 그러면 다음 최댓값을 찾는 데는 O(1)이면 되고, 그 보장을 유지하는 데(= down-heap)는 O(log n)만 든다.

 즉, down-heap은 "다음 최댓값이 어디 있는지 매번 새로 찾는 비용 O(n)"을 "heap 모양을 살짝 복구하는 비용 O(log n)"으로 바꿔주는 장치다. 이것이 Selection-Sort(O(n^2))와 Heap-Sort(O(n log n))의 본질적인 차이다.

 

4.5 시간복잡도와 공간

• Build-heap: O(n)
• 반복문에서 down-heap을 최대 n번 수행, 각 O(log n) -> O(n log n)
• 합쳐서 전체 O(n log n)
• swap만으로 동작하므로 추가 공간 O(1) - in-place

---

마무리

이번 글의 흐름: Selection-Sort(항상 O(n^2), early exit 불가) -> Insertion-Sort(O(n)~O(n^2), early exit 가능, adaptive) -> 이 둘의 차이(early exit) -> Heap-Sort(heap 구조로 "최댓값 찾기"를 O(1)+O(log n)으로 만들어 O(n log n) 달성).

 

핵심 정리:

• Selection-Sort: 비교 n(n-1)/2 = O(n^2), 항상 동일. swap은 최대 n-1번
• Insertion-Sort: adaptive. 정렬된 입력에서 O(n), 역순 입력에서 O(n^2). "더 큰 원소를 만나면 즉시 멈춤"이 핵심
• early exit 가능 여부가 두 알고리즘의 차이를 만든다 - "최솟값 찾기"는 끝까지 봐야 하고, "삽입 위치 찾기"는 도중에 멈출 수 있다
• Heap-Sort: array 기반 heap에서 index0=root, 자식은 2i+1,2i+2. swap(root,마지막) -> heap크기 감소 -> down-heap을 반복. down-heap이 "다음 최댓값은 항상 array[0]"이라는 보장을 O(log n)에 유지해주는 게 핵심. 전체 O(n log n), in-place