퀵정렬 (Quick Sort)
쉽게 풀면
줄 서 있는 학생 30명을 키 순서로 세운다고 해봅시다. 먼저 아무나 한 명을 "기준"으로 뽑습니다(이 학생이 피벗입니다). 그리고 나머지 학생들을 기준보다 키가 작으면 왼쪽 무리로, 크면 오른쪽 무리로 보냅니다. 이렇게 한 번 나누고 나면 기준 학생은 이미 자기 자리(왼쪽 무리와 오른쪽 무리 사이)를 찾은 셈입니다. 이제 왼쪽 무리와 오른쪽 무리 각각에 대해 똑같은 과정을 반복하면, 무리의 크기가 1명이 될 때까지 계속 쪼개지면서 전체가 정렬됩니다. 기준을 잘 뽑으면 매번 무리가 절반씩 줄어들어 평균적으로 O(n log n) 시간이 걸리지만, 하필 매번 가장 작거나 가장 큰 학생만 기준으로 뽑는 최악의 경우에는 O(n²)까지 느려질 수 있습니다.
왜 중요한가
퀵정렬은 평균적으로 매우 빠르고 추가 메모리를 거의 쓰지 않는 제자리 정렬 방식이라, 실제 소프트웨어 라이브러리의 기본 정렬 함수로 흔히 채택되며 알고리즘 교육과 성능 비교 연구에서 기준점 역할을 합니다. 대용량 데이터를 다루는 시스템에서는 정렬 성능이 전체 처리 속도에 직접 영향을 미치기 때문에, 퀵정렬의 변형이나 피벗 선택 전략을 개선하는 연구가 컴퓨터과학 여러 분야에서 꾸준히 이루어집니다.
논문에서는 이렇게 쓰입니다
이 문장은 "데이터를 빠르게 정렬하려고 퀵정렬을 썼는데, 최악의 경우(느려지는 경우)를 피하기 위해 기준값을 무작위로 고르지 않고 세 값의 중앙값으로 골랐다"는 뜻입니다.
병렬컴퓨팅 연구에서는 원래 순차적으로 진행되는 퀵정렬의 분할 과정을 여러 처리 장치가 동시에 나눠 맡도록 바꿔 속도를 높였다는 것을 보여줍니다.
데이터베이스 시스템 연구에서는 데이터 조각이 매우 작아졌을 때는 퀵정렬 대신 더 단순한 정렬 방식으로 전환하는 방식이 실제 성능 향상에 기여한다는 것을 보여줍니다.
조금 더 깊게 보면
퀵정렬의 실제 성능은 피벗을 어떻게 선택하느냐에 크게 좌우되므로, 실무 구현에서는 첫 원소나 마지막 원소를 그대로 쓰기보다 무작위 선택이나 세 값의 중앙값을 이용하는 전략을 흔히 사용합니다. 또한 재귀 호출이 작은 크기의 부분 배열까지 계속되면 함수 호출 오버헤드가 커지므로, 일정 크기 이하로 줄어든 구간은 삽입정렬 같은 더 단순한 알고리즘으로 처리하는 하이브리드 방식이 실제 라이브러리 구현에서 흔히 쓰입니다. 이런 최적화들은 알고리즘의 점근적 시간복잡도 자체를 바꾸지는 않지만, 실제 실행 시간을 눈에 띄게 줄여줍니다.
주의할 점
퀵정렬은 평균적으로는 매우 빠르지만 이미 정렬된 배열의 첫 원소를 그대로 피벗으로 쓰는 등 운이 나쁘면 O(n²)까지 느려질 수 있어, 안정적으로 O(n log n)이 보장되는 병합 정렬과는 이 점에서 차이가 있습니다. 또한 퀵정렬은 별도의 큰 임시 배열 없이 제자리(in-place)에서 정렬을 수행한다는 점도 병합정렬과 다릅니다.