퀵 정렬

퀵 정렬은 가장 많이 쓰이는 정렬 알고리즘 중 하나입니다. 피벗을 고르고, 목록을 피벗보다 작은 값과 나머지로 나눈 뒤, 양쪽을 같은 방식으로 정렬합니다. 실제로 빠르고 추가 목록도 필요 없지만, 얼마나 빠른지는 피벗에 달려 있습니다.

피벗 막대를 기준으로 분할된 막대: 작은 막대는 한쪽에, 큰 막대는 다른 쪽에, 피벗은 그 사이에 있음
피벗 막대를 기준으로 분할된 막대: 작은 막대는 한쪽에, 큰 막대는 다른 쪽에, 피벗은 그 사이에 있음

기본 아이디어

값 하나를 피벗으로 고릅니다. 피벗보다 작은 값은 모두 그 앞에, 나머지 값은 모두 그 뒤에 오도록 목록을 재배치합니다. 이 재배치를 분할이라고 하며, 분할 후 피벗은 정렬된 목록에서 있어야 할 바로 그 자리에 놓입니다. 이제 양쪽은 서로 독립된 문제이므로 각각 퀵 정렬로 정렬합니다. 값이 하나뿐이거나 없는 쪽은 이미 정렬되어 있습니다.

분할 단계별로 보기

이 앱은 Lomuto 분할을 사용합니다. 피벗은 부분의 끝으로 옮겨집니다. 표시는 맨 앞에서 시작하며, 표시 앞의 값은 모두 피벗보다 작습니다. 나머지 각 값을 피벗과 비교해 더 작으면 표시 위치로 교환하고 표시를 한 칸 옮깁니다. 마지막으로 피벗을 표시 위치로 교환합니다. 5, 1, 4, 2, 8에서 마지막 값을 피벗으로 쓰면, 네 값이 모두 8보다 작으므로 8은 끝에 그대로 남습니다. 부분 5, 1, 4, 2는 2를 기준으로 분할되어 1, 2, 4, 5가 되고, 4, 5는 5를 기준으로 분할됩니다. 비교 8번, 교환 2번, 분할 3번입니다.

좋은 피벗과 나쁜 피벗

모든 피벗이 가운데에 놓인다면 분할할 때마다 문제가 절반으로 줄어, 정렬에 약 n log₂ n번의 비교가 듭니다. 무작위 목록에서는 피벗이 완벽한 경우는 드물지만 대개 충분히 좋아서, 무작위 값 40개에 대해 앱은 약 190번의 비교를 셉니다. 최악의 경우는 피벗이 항상 가장 작거나 가장 큰 값일 때입니다. 마지막 값을 피벗으로 쓰면 이미 정렬된 목록이나 역순 목록이 바로 그렇습니다. 분할마다 피벗만 빠지고, 정렬에 n(n − 1)/2번, 값 40개라면 780번의 비교가 필요합니다.

피벗 고르기

무작위 피벗은 어떤 특정한 순서로도 속일 수 없으므로, 어떤 입력에서도 최악의 경우가 생길 가능성이 극히 낮습니다. 세 값의 중앙값, 즉 첫 번째, 가운데, 마지막 원소 중 가운데 값은 계산 비용이 적고 정렬된 목록과 역순 목록을 잘 처리합니다. 앱에서 정렬된 목록에 두 방법을 모두 써 보면 비교 횟수가 780번에서 약 150번으로 줄어듭니다. 같은 값이 많은 경우는 다른 문제입니다. 그런 값은 모두 피벗의 한쪽으로 몰립니다. 피벗과 같은 값을 가운데 부분에 모으는 3-way 분할이 이를 해결합니다.

역사와 활용

Tony Hoare는 1959년에 퀵 정렬을 고안해 1961년에 발표했습니다. 그가 만든 분할은 양 끝에서 훑어 교환 횟수가 더 적으며, 여기서 보여 주는 더 단순한 Lomuto 방식은 교과서를 통해 널리 퍼졌습니다. 퀵 정렬은 제자리에서 정렬하고 안쪽 루프가 매우 짧아서 실제로는 대개 병합 정렬보다 빠르지만, 안정 정렬은 아닙니다. C++ 표준 라이브러리의 정렬에 쓰이는 introsort는 퀵 정렬을 실행하다가 분할이 너무 고르지 않으면 힙 정렬로 바꾸므로, 최악의 경우에도 n log n을 유지합니다.

토니 호어. 1959년에 퀵 정렬을 고안하고 1961년에 발표했다.
토니 호어. 1959년에 퀵 정렬을 고안하고 1961년에 발표했다.

직접 해 보기

앱을 열고 ‘단계’를 누르세요. 분할 중인 부분은 음영으로 표시되고, 피벗은 고유한 색을 띠며, 점선은 왼쪽 부분, 즉 피벗보다 작은 값들의 끝을 나타냅니다. 각 피벗은 최종 위치에 도달하면 초록색으로 바뀝니다. 정렬된 목록과 마지막 값 피벗을 고른 다음 세 값의 중앙값으로 바꿔서 카운터를 비교해 보세요.

자주 묻는 질문

퀵 정렬의 시간 복잡도는 얼마인가요?

평균적으로, 그리고 피벗이 좋을 때는 O(n log n), 최악의 경우에는 O(n²)입니다. 제자리에서 정렬하며, 작은 쪽을 먼저 정렬하면 재귀에 필요한 추가 메모리는 O(log n)입니다.

Lomuto 분할과 Hoare 분할의 차이는 무엇인가요?

Lomuto는 표시 하나를 두고 왼쪽에서 오른쪽으로 훑습니다. 따라가기 쉬우며 이 앱이 보여 주는 방식입니다. Hoare는 양 끝에서 서로를 향해 훑으며 잘못된 쪽에 있는 값 쌍을 교환하므로, 평균적으로 교환 횟수가 약 3분의 1로 줄어듭니다.

같은 값이 많으면 퀵 정렬이 느려지는 이유는 무엇인가요?

피벗과 같은 값은 모두 같은 쪽으로 가므로, 서로 다른 값이 적은 목록은 고르지 않게 나뉘고, 모두 같은 값인 목록은 최악의 경우만큼 나쁩니다. 피벗과 같은 값을 가운데에 모으는 3-way 분할로 이를 피할 수 있습니다.

퀵 정렬은 안정 정렬인가요?

아니요. 분할 중 교환이 값을 먼 거리로 옮기므로 같은 값의 순서가 바뀔 수 있습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

퀵 정렬 해 보기