퀵·병합·힙 정렬

퀵 정렬(quick sort)·병합 정렬(merge sort)·힙 정렬(heap sort)은 줄을 나누거나 나무 꼴로 세워 견주는 횟수를 크게 줄인 정렬입니다. 앞 레슨의 선택·버블·삽입 정렬은 두 겹 반복이라 O(n²)인데, 이 셋은 평균 O(n log n)이라 데이터가 많을수록 차이가 벌어집니다. 다만 퀵 정렬은 줄이 놓인 모양에 따라 O(n²)까지 느려집니다. 아래 그림은 같은 줄 4, 2, 7, 1, 3, 8, 5를 세 방법으로 가르고, 합치고, 나무로 세우는 과정을 보여 줍니다.

1퀵 정렬 — 피벗을 기준으로 가른다

퀵 정렬은 값 하나를 피벗(pivot)으로 골라, 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 가릅니다. 첫 값 4를 피벗으로 고르면 2, 1, 3과 7, 8, 5로 갈리고, 4는 넷째 자리에 섭니다. 가르고 나면 피벗은 제자리입니다. 양쪽 덩어리도 같은 방법으로 다시 가르다 덩어리가 한 칸이 되면 끝납니다. 덩어리 안의 차례는 코드에 따라 다를 수 있지만, 피벗이 서는 자리는 같습니다. 이 레슨은 덩어리 안 값을 원래 줄의 차례대로 두고, 그 약속으로 견주는 횟수를 셉니다.

고르게 갈리면 층이 log n개라 평균 O(n log n)입니다. 이미 정렬된 줄에서 첫 값을 피벗으로 고르면 한쪽 덩어리가 늘 비어 층이 n − 1개가 되고, 견주기가 n(n − 1)/2번이라 O(n²)입니다. 그림의 7칸에서는 10번이 21번으로 늘었습니다.

2병합 정렬 — 반씩 쪼갰다가 둘씩 합친다

병합 정렬은 줄을 반씩 쪼개 한 칸이 될 때까지 내려간 뒤, 정렬된 두 줄의 맨 앞끼리 견줘 작은 값부터 옮기며 하나로 합칩니다. 2, 4와 1, 7을 합치면 1, 2, 4를 차례로 옮기고 남은 7을 붙여 1, 2, 4, 7이 됩니다.

쪼개는 층이 log n개이고 층마다 n칸을 옮기므로 줄의 모양과 상관없이 O(n log n)입니다. 대신 보통 합칠 때 줄 길이만큼 칸을 따로 씁니다. 자료에 따라 합병 정렬이라고도 부릅니다.

퀵 정렬과 병합 정렬처럼 큰 문제를 작은 문제로 나눠 풀고 합치는 방식을 분할 정복이라고 합니다. 알고리즘 설계 기법에서 다시 봅니다.

3힙 정렬 — 가장 큰 값을 루트에서 꺼낸다

힙(heap)은 부모가 자식보다 늘 크거나 같은(최대 힙), 또는 늘 작거나 같은(최소 힙) 완전 이진 트리(트리)입니다. 줄을 칸 번호 차례로 트리에 놓으면 i번 칸의 자식은 2i번과 2i + 1번 칸입니다.

힙 정렬은 먼저 아래쪽 부모부터 자식 가운데 큰 값과 자리를 바꿔 올려 최대 힙을 만듭니다. 바꿔 내려간 값은 새 자리에서 다시 자식과 견줍니다. 그림의 줄은 8, 3, 7, 1, 2, 4, 5가 되어 루트에 가장 큰 8이 섭니다.

루트를 맨 끝 칸과 바꿔 떼어 두고, 남은 칸으로 다시 힙을 세우기를 되풀이하면 뒤에서부터 큰 값이 쌓입니다. 다시 세울 때마다 트리 높이 log n만큼만 내려가므로 언제나 O(n log n)이고, 칸을 따로 쓰지 않습니다.

예제

정렬 프로그램 셋을 지켜본 기록입니다. 각각 어느 정렬인지 먼저 골라 보세요.

(가) 정렬하는 동안 줄 길이만큼 빈 줄을 따로 잡아 두고, 반으로 나눈 두 줄을 그 빈 줄에 옮기며 합칩니다.

(나) 따로 잡는 칸 없이 줄 안에서 나무 꼴을 세우고, 맨 위의 값을 줄 맨 뒤로 보내기를 되풀이합니다.

(다) 평소에는 빠른데, 이미 정렬된 줄을 넣었더니 견주는 횟수가 n²에 가깝게 늘었습니다.

답을 정했으면 아래 표로 맞춰 보세요. 첫 칸은 세 정렬을 가르는 물음입니다.

• (가) 병합 정렬, (나) 힙 정렬, (다) 퀵 정렬입니다.
• 최악을 보면 퀵만 O(n²)이고, 따로 쓰는 칸을 보면 병합만 줄 길이만큼 씁니다. 이 두 줄로 셋을 다 가를 수 있습니다.

시험 포인트

• 필기(시험에서는 1과목): 퀵 정렬은 평균 O(n log n)이지만 최악 O(n²)이고, 병합·힙 정렬은 언제나 O(n log n)입니다. 퀵 정렬의 최악을 O(n log n)으로 적은 보기가 함정입니다. 힙 정렬은 완전 이진 트리(최대 힙)를 쓰고, 퀵·병합 정렬은 분할 정복으로 풉니다. 최대 힙을 만든 결과를 묻기도 합니다 — 바꿔 내려간 값은 새 자리에서 다시 자식과 견줍니다.
• 실기: 이름을 한글 이름과 영문으로 씁니다 — 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort, 자료에 따라 합병 정렬), 힙 정렬(Heap Sort), 피벗(Pivot).

확인 문제

1. 첫 값을 피벗으로 고르는 퀵 정렬로 줄을 정렬합니다. 견주는 횟수가 가장 많아 O(n²)에 이르는 줄을 고르세요.

• ① 1, 2, 3, 4, 5, 6, 7
• ② 2, 1, 4, 3, 6, 5, 7
• ③ 4, 2, 6, 1, 3, 5, 7
• ④ 4, 7, 1, 6, 2, 5, 3

2. (가)~(라)에 맞는 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 기준값 하나를 골라 그보다 작은 값과 큰 값으로 나누고, 나뉜 양쪽을 같은 방법으로 다시 나누는 정렬
• (나) (가)에서 고른 기준값
• (다) 줄을 반씩 쪼개 한 칸까지 내려간 뒤, 정렬된 두 줄의 맨 앞끼리 견주며 한 줄로 이어 붙이는 정렬
• (라) 부모가 자식보다 늘 큰 완전 이진 트리를 세우고, 맨 위의 값을 하나씩 떼어 맨 뒤로 보내는 정렬

3. 줄 2, 6, 3, 9, 5, 8을 칸 번호 차례로 완전 이진 트리에 놓고, 아래쪽 부모부터 자리를 바꿔 올려 최대 힙을 만드세요. 결과를 칸 번호 차례로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.