Sorting (3)

 (1)에서 Selection/Insertion/Heap-Sort, (2)에서 Merge-Sort를 다뤘다. 이번 (3)은 Sorting 단원의 마지막으로, Quick-Sort와 Stable Sorting, 그리고 지금까지 다룬 5개 정렬 알고리즘의 전체 비교/정리를 다룬다.

 

이번 글의 흐름:

• Quick-Sort: Merge-Sort와 정반대 구조(divide가 어렵고 conquer가 trivial)
• pivot 선택이 시간복잡도에 미치는 영향 - 최악의 경우 O(n^2)
• in-place partitioning
• Stable Sort의 정의와, 각 알고리즘의 stability
• 5개 알고리즘 전체 비교표와 trade-off 정리

---

1. Quick-Sort

1.1 Merge-Sort와 정반대 구조

Merge-Sort는 "Divide는 trivial(그냥 반으로), Conquer(merge)가 어려움"이었다. Quick-Sort는 정반대다: "Divide(partition)가 어려운 일을 다 하고, Conquer는 trivial"하다.

 

1.2 알고리즘

1. Pivot 하나를 고른다 (보통 마지막 원소)
2. Partition: 배열을 pivot보다 작은 그룹 / pivot / pivot보다 큰 그룹 세 부분으로 재배열한다. 이 과정에서 pivot은 자기 최종 위치에 자리잡는다
3. 작은 그룹과 큰 그룹을 각각 재귀적으로 Quick-Sort
4. 합치는 과정이 따로 필요 없다 - partition이 끝나면 "작은 그룹 | pivot | 큰 그룹" 순서가 이미 보장되므로, 양쪽이 각자 정렬되면 전체가 정렬된 것
   
   

1.3 예제: [5,2,8,1,9,3] (pivot = 마지막 원소)

[5,2,8,1,9,3] pivot=3
  partition -> [2,1 | 3 | 5,8,9]
   /                          \
[2,1] pivot=1             [5,8,9] pivot=9
partition->[1|2]          partition->[5,8 | 9]
 /     \                       pivot=8
[1]    [2]                  partition->[5|8]
                              /      \
                            [5]      [8]

각 단계에서 partition은 그 레벨의 배열 크기만큼 한 번 훑으면서, pivot보다 작은/큰 값으로 나눈다. 최종 결과: [1,2,3,5,8,9]

1.4 Pivot 선택이 왜 중요한가 - 시간복잡도

Merge-sort tree는 항상 정확히 반씩 나뉘어서 height=O(log n)이 보장됐다. 그런데 Quick-sort tree의 모양은 partition이 얼마나 균등하게 나누는지, 즉 pivot을 잘 고르느냐에 달려있다.

• 균등하게 나뉘는 경우(평균/최선): 매번 절반씩 나뉘면 height=O(log n) -> 전체 O(n log n)
• 최악의 경우: pivot이 매번 "가장 작은 값" 또는 "가장 큰 값"이라면, partition 결과가 "한쪽은 0개, 다른 쪽은 나머지 전부"가 된다

최악의 예: 이미 정렬된 배열 [1,2,3,4,5], pivot=마지막 원소

[1,2,3,4,5] pivot=5 -> partition -> [1,2,3,4 | 5 | ]
  -> [1,2,3,4] pivot=4 -> [1,2,3 | 4 | ]
    -> [1,2,3] pivot=3 -> [1,2 | 3 | ]
      -> [1,2] pivot=2 -> [1 | 2 | ]

 
매 단계마다 "큰 쪽 그룹이 0개"라서, 트리가 한 줄로 길게 늘어선 체인(height=n-1)이 된다. 각 레벨에서 partition은 그 시점에 남은 크기만큼 비교를 하므로:

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

 

이 패턴은 1부의 Selection-Sort와 정확히 같은 구조다 - "매번 전체를 훑으면서 하나씩만 확정해나가는" 것과 동일하다. pivot을 잘못 고르면 Quick-Sort가 Selection-Sort처럼 퇴화한다.

 

pivot을 첫 번째 원소로 바꿔도 마찬가지

 같은 배열 [1,2,3,4,5]에서 pivot을 마지막 원소가 아니라 첫 번째 원소로 바꿔보자. 첫 번째 원소(1)는 이 배열의 최솟값이므로, partition하면 "작은 그룹은 0개, 큰 그룹은 나머지 4개"가 된다 ([1 | 2,3,4,5]). 그 다음도 마찬가지로 pivot(2)이 다시 남은 배열의 최솟값이라 [2 | 3,4,5]... 똑같이 한 줄 체인이 되어 O(n^2)이다.

 

일반화: last-element pivot이든 first-element pivot이든, "이미 정렬된(혹은 역순) 배열"에서는 pivot이 매번 그 구간의 극값(최소 또는 최대)이 되어버린다. 그러면 partition 결과가 항상 "한쪽은 0개"가 되고 O(n^2)이 된다. 즉 어느 쪽 끝을 pivot으로 고르든, "이미 정렬된 배열"이라는 흔한 입력 패턴에 대해 똑같이 최악의 경우를 만난다.

(참고: 이 때문에 실전에서는 "랜덤하게 pivot 고르기"나 "median-of-three"(첫/중간/끝 중 중간값) 같은 방법을 써서, 이미 정렬된 배열처럼 자주 등장하는 입력에 대해 우연히 최악의 경우에 빠지는 걸 피한다.)

1.5 In-place Quick-Sort

Merge-Sort는 merge할 때 O(n)의 새 배열이 필요했다. Quick-Sort의 partition은 같은 배열 안에서 swap만으로 수행할 수 있다 (Lomuto partition 방식):

partition(A, lo, hi):
    pivot = A[hi]
    i = lo - 1
    for j = lo to hi-1:
        if A[j] <= pivot:
            i = i + 1
            swap(A[i], A[j])
    swap(A[i+1], A[hi])   # pivot을 최종 위치로
    return i+1            # pivot의 최종 인덱스

 

i는 "지금까지 확인한 것 중 pivot보다 작거나 같은 원소들의 마지막 위치"를 추적한다. j가 그런 원소를 만날 때마다 i를 한 칸 늘리고 그 자리와 swap - 결국 pivot보다 작은 원소들이 앞쪽에 모인다. 마지막에 pivot을 i+1 자리로 옮기면 partition 완성.

swap만 쓰므로 추가 공간 O(1) (재귀 호출 스택까지 고려하면 O(log n)~O(n)) - Merge-Sort가 O(n) 추가 공간이 필요했던 것과 대조적이다.

---

2. Stable Sorting

2.1 Stable Sort란?

같은 key(값)를 가진 원소가 여러 개 있을 때, 정렬 후에도 그 원소들의 "원래 순서"가 그대로 유지되면 그 정렬을 stable하다고 한다.

왜 중요할까? 예를 들어 학생 명단을 먼저 이름순으로 정렬해놓고, 그 다음 "학년"으로 stable sort를 하면 - 같은 학년 안에서는 이름순이 그대로 유지된다. 여러 기준으로 순차 정렬할 때 stability가 이런 보장을 준다.

 

2.2 예제: Selection-Sort는 stable이 아니다

배열 [(3,a),(3,b),(1,c)] - 값이 같은 a,b의 원래 순서(a가 먼저)가 유지되는지 보자.

 

Selection-Sort:

[(3,a),(3,b),(1,c)]
최솟값 (1,c)(idx2) 찾아서 idx0과 swap -> [(1,c),(3,b),(3,a)]
나머지 [(3,b),(3,a)]에서 최솟값은 (3,b)(idx1, 이미 자리) -> 그대로
결과: [(1,c),(3,b),(3,a)]

a와 b의 순서가 b,a로 뒤바뀌었다! (1,c)를 idx0으로 끌어오는 swap 때문에, 원래 맨 뒤에 있던 a가 b보다 앞으로 튕겨나갔다.

 

Insertion-Sort:

[(3,a) | (3,b),(1,c)]
(3,b) 삽입: (3,a)와 비교, 3>3은 거짓(같으면 안 밀음) -> 그대로 뒤에 -> [(3,a),(3,b)]
(1,c) 삽입: (3,b),(3,a) 모두 밀고 맨앞 -> [(1,c),(3,a),(3,b)]

a,b 순서(a가 먼저) 그대로 유지된다 - Insertion-Sort는 "같으면 옮기지 않는다"(> 비교, >= 아님)는 규칙 덕분에 stable하다.

 

2.3 각 알고리즘의 stability

• Selection-Sort: 아니오 - 위 예제처럼, "최솟값을 멀리서 끌어오는 swap"이 다른 원소들의 순서를 망가뜨릴 수 있다
• Insertion-Sort: 예 - 비교에서 "크면" 옮기고 "같으면" 안 옮기면 순서 보존
• Merge-Sort: 예 - merge에서 두 값이 같을 때 왼쪽 배열의 원소를 먼저 가져오면(왼쪽 배열은 원래 더 앞쪽에 있던 원소들이므로) 순서 보존
• Heap-Sort: 아니오 - heap 연산(down-heap 등)은 원래 위치 정보를 추적하지 않음
• Quick-Sort: 아니오 (일반적인 in-place 구현) - partition 중의 swap이 같은 값들의 상대 순서를 바꿀 수 있음

---

3. 전체 비교표

알고리즘	최선	평균	최악	추가공간	stable	in-place
Selection-Sort	O(n^2)	O(n^2)	O(n^2)	O(1)	아니오	예
Insertion-Sort	O(n)	O(n^2)	O(n^2)	O(1)	예	예
Heap-Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	아니오	예
Merge-Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	예	아니오
Quick-Sort	O(n log n)	O(n log n)	O(n^2)	O(log n)	아니오	예(대체로)

 

적용 예시: "메모리가 매우 제한적이고, 같은 점수를 가진 학생들의 원래 등록 순서를 반드시 유지해야 한다"면?

 

표에서 O(1) 공간과 stable을 동시에 만족하는 건 Insertion-Sort뿐이다.

• Selection-Sort: O(1)이지만 not stable - 탈락
• Heap-Sort: O(1)이지만 not stable - 탈락
• Merge-Sort: stable이지만 O(n) 공간 - 탈락
• Quick-Sort: O(log n)이고 not stable - 탈락
• Insertion-Sort: O(1) + stable 둘 다 만족 (대신 O(n^2) worst case를 감수)

이렇게 어떤 알고리즘도 "시간 빠름 + 공간 적음 + stable + worst case 보장"을 전부 만족하진 못한다 - 상황에 맞게 어떤 조건을 희생할지 선택하는 게 알고리즘 선택의 본질이다.

---

마무리 - Sorting 단원 전체 정리

세 편에 걸쳐 본 5개 알고리즘을 한 줄로 정리하면:

• Selection-Sort: 항상 O(n^2). "최솟값 찾기"에 early exit이 없어서 입력 상태와 무관
• Insertion-Sort: O(n)~O(n^2), adaptive, stable. "맞는 자리를 찾으면 즉시 멈춤"
• Heap-Sort: O(n log n), in-place, not stable. down-heap으로 "다음 최댓값은 항상 array[0]"을 O(log n)에 유지
• Merge-Sort: 항상 O(n log n), O(n) 공간, stable. "divide는 trivial, merge가 핵심"이고 레벨당 O(n) x 레벨수 O(log n)
• Quick-Sort: 평균 O(n log n), 최악 O(n^2), in-place, not stable. "partition이 핵심"이고 pivot 선택이 균형을 좌우 - 잘못 고르면 Selection-Sort처럼 퇴화

 큰 그림으로 보면: O(n^2) 알고리즘들은 "한 번에 하나씩 확정"하는 방식이고, O(n log n) 알고리즘들은 모두 어떤 형태로든 "문제를 절반 크기로 줄여나가는" 구조(heap의 트리 구조, merge/quick의 divide-and-conquer)를 갖고 있다 - 이게 O(n^2)에서 O(n log n)으로의 도약이 일어나는 공통된 이유다.