기준값 하나를 골라 그보다 작은 값은 왼쪽, 크거나 같은 값은 오른쪽으로 나눈 뒤, 양쪽을 같은 방법으로 다시 정렬합니다. 나누기가 끝나는 순간 기준값의 최종 자리가 정해집니다.

퀵 정렬의 분할 과정과 호출 스택을 보여 주는 시뮬레이터

[자동 재생]을 누르거나 [다음 단계]로 한 단계씩 넘겨 보세요. 슬라이더를 끌면 원하는 단계로 바로 이동합니다. [이미 정렬됨]을 고르면 퀵 정렬이 가장 느려지는 경우를 볼 수 있습니다.

최선O(n log n)

평균O(n log n)

최악O(n²)

추가 공간O(log n)

안정 정렬아니요

실전 속도매우 빠름

분할: i와 j 두 손가락

j는 아직 확인하지 않은 값을 왼쪽부터 하나씩 훑고, i는 "기준값보다 작은 값이 들어갈 다음 자리"를 가리킵니다. 초록 구간(lo ~ i−1)에는 기준값보다 작은 값이, 빨간 구간(i ~ j−1)에는 크거나 같은 값이 모입니다. j가 끝까지 가면 기준값을 i 자리로 옮겨 두 구간 사이에 끼웁니다.

최악의 경우

이미 정렬된 배열에서 맨 오른쪽 값을 기준값으로 고르면, 기준값이 매번 구간에서 가장 커서 한쪽 구간이 통째로 남습니다. 재귀 깊이가 n이 되고 비교가 n(n−1)/2번으로 늘어납니다. 그래서 실제 구현은 기준값을 무작위로 고르거나, 처음·가운데·끝 세 값의 중앙값을 씁니다.

코테에서는: 퀵 셀렉트

분할을 마치면 기준값이 i번 자리에 확정됩니다. i가 k와 같으면 그 값이 k번째로 작은 값이고, 아니면 k가 있는 쪽만 다시 분할하면 됩니다. 한쪽만 재귀하므로 평균 O(n)에 k번째 값을 찾습니다. 단순히 정렬이 필요하면 sort()를, 상위 k개가 필요하면 heapq.nsmallest, heapq.nlargest를 쓰는 편이 안전합니다.