yeolyi.com성열의 컴퓨터공학

퀵 정렬

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

병합 정렬은 반으로 자르기만 하고, 비교는 합칠 때 합니다. 거꾸로 나눌 때 미리 작은 값과 큰 값을 갈라 두면 어떨까요? 나눈 조각들이 처음부터 제 순서에 있으니 합칠 필요가 없을 겁니다.

피벗으로 나누기

반 아이들을 키 순서로 세운다고 해 봅시다. 아무나 한 명을 기준으로 정하고, 그보다 작은 아이는 왼쪽, 큰 아이는 오른쪽에 서게 합니다. 줄은 아직 엉망이지만 기준이 된 아이의 자리는 이제 바뀌지 않습니다.

배열에서도 같은 일을 할 수 있습니다. 기준으로 삼는 값을 피벗(pivot)이라 합니다. 피벗을 뺀 값을 하나씩 피벗과 비교해 작은 쪽과 큰 쪽으로 보내는 것을 분할(partition)이라 합니다. 여기서는 맨 앞 값을 피벗으로 씁니다.

배열
27143834521933
작은 쪽 (27보다 작음)
큰 쪽 (27보다 큼)

맨 앞 값 27을 피벗으로 고릅니다.비교 0번

피벗을 뺀 n − 1개를 한 번씩 비교하니 분할 한 번은 O(n)입니다.

나눈 조각 정렬

나눈 뒤 작은 쪽과 큰 쪽은 서로 섞일 일이 없습니다. 각 쪽을 정렬하면 끝이고, 합치는 단계가 없습니다. 각 쪽은 재귀로 풀고, 값이 하나 이하인 조각이 기저 사례입니다. 이 방법이 퀵 정렬(quick sort)입니다.

1#include <stdio.h>
2
3int arr[6] = {5, 2, 7, 1, 6, 3};
4int tmp[6];
5
6// arr[lo]~arr[hi - 1]을 정렬한다
7void quick_sort(int lo, int hi) {
8 if (hi - lo <= 1) {
9 return;
10 }
11 // 맨 앞 값이 피벗
12 int pivot = arr[lo];
13 int k = lo;
14 // 피벗보다 작은 값들을 먼저
15 for (int i = lo + 1; i < hi; i++) {
16 if (arr[i] < pivot) {
17 tmp[k++] = arr[i];
18 }
19 }
20 // 그다음 피벗
21 int p = k;
22 tmp[k++] = pivot;
23 // 피벗 이상인 값들을 뒤에
24 for (int i = lo + 1; i < hi; i++) {
25 if (arr[i] >= pivot) {
26 tmp[k++] = arr[i];
27 }
28 }
29 for (k = lo; k < hi; k++) {
30 arr[k] = tmp[k];
31 }
32 // 피벗 양쪽을 따로 정렬한다
33 quick_sort(lo, p);
34 quick_sort(p + 1, hi);
35}
36
37int main(void) {
38 quick_sort(0, 6);
39 for (int i = 0; i < 6; i++) {
40 printf("%d ", arr[i]);
41 }
42 printf("\n");
43 return 0;
44}

변수 없음
출력 없음

재생하며 피벗마다 arr가 작은 쪽과 큰 쪽으로 어떻게 갈리는지 봅시다.

나눌 때마다 배열 전체를 보면 다음과 같습니다.

처음 배열
27143834521933

맨 앞 값을 피벗으로 삼아 나눕니다.비교 0번

섞인 입력을 끝까지 정렬한 뒤 정렬된 입력으로도 해 봅시다.

섞인 입력은 네 번 나누면 끝나지만, 정렬된 입력은 일곱 번 나눠야 합니다.

피벗 고르기

섞인 입력에서는 피벗이 대개 가운데쯤이라 반쯤으로 나뉩니다. 병합 정렬처럼 층마다 비교가 n번을 넘지 않고 층이 log₂ n개쯤이니 O(n log n)입니다.

정렬된 입력에서는 맨 앞 값이 늘 가장 작습니다. 큰 쪽에 나머지가 모두 몰려, 한 번 나눌 때 피벗 하나만 제자리를 찾습니다. 비교는 n − 1번, n − 2번, …, 1번이라 모두 n(n − 1)/2번, 선택 정렬과 똑같은 O(n²)입니다. 퀵 정렬의 최악의 경우입니다.

피벗을 무작위로 고르면 이 함정을 피할 수 있습니다. 매번 가장 작거나 큰 값만 고르는 일은 거의 일어나지 않습니다.

피벗
숫자 n 500개
퀵 정렬 · 섞인 입력비교 4,990번
퀵 정렬 · 정렬된 입력비교 124,750번
병합 정렬 · 섞인 입력비교 3,871번
선택 정렬비교 124,750번

피벗을 무작위 값으로 바꾸고 다시 섞기를 여러 번 눌러 봅시다.

n이 500일 때 피벗이 맨 앞 값이면 정렬된 입력에서 선택 정렬과 똑같이 124,750번 비교하지만, 무작위 값이면 어느 입력이든 5,000번 안팎입니다. 무작위 피벗도 최악의 경우는 여전히 O(n²)이지만, 비교 횟수의 기댓값은 입력 모양과 상관없이 O(n log n)입니다.

마무리

이번 파트에서는 재귀로 경우를 빠짐없이 만들어 보는 백트래킹과, 문제를 쪼개 풀고 합치는 분할 정복을 다뤘습니다. 하지만 경우가 많으면 가지치기를 해도 느리고, 쪼갠 문제가 서로 겹치면 재귀는 같은 계산을 되풀이합니다. 그래서 다음 파트에서는 작은 답을 쌓아 큰 답을 만드는 그리디와 동적 계획법을 다룹니다. 첫 글은 그리디 알고리즘입니다.

도전 문제

1부터 8까지 여덟 값을 무작위 순서로 늘어놓고(40320가지 순서가 모두 같은 확률) 글의 quick_sort로 정렬합니다. 3과 7이 서로 비교될, 즉 한쪽이 피벗일 때 다른 쪽이 그 피벗과 비교될 확률은 몇 %일까요? 숫자로 답하세요.