Page 224 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

06-6 퀵 정렬

퀵 정렬은 가장 빠른 정렬 알고리즘 중의 하나로 널리 사용되고 있습니다.

퀵 정렬 살펴보기

퀵 정렬(quick sort)은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘입니다. 퀵 정렬이라
는 이름은 이 알고리즘의 정렬 속도가 매우 빠른 데서 착안한 찰스 앤터니 리처드 호어(C. A.

R. Hoare)가 직접 붙인 이름입니다. 그림 6-19는 이 알고리즘으로 학생 수가 8명인 그룹을 키
순서대로 정렬한 모습을 나타낸 것입니다. 먼저 어느 한 사람의 키를 선택합니다. 키가
168cm인 학생 A를 선택할 경우 그 학생을 기준으로 학생 A의 키보다 작은 사람의 그룹과 큰
사람의 그룹으로 나눕니다. 이때 이 학생 A를(그룹을 나누는 기준) 피벗(pivot)이라고 합니다. 퀵

정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마
칩니다. 피벗은 마음대로 선택할 수 있습니다. 또한 이 피벗을 어느 하나의 그룹에 포함시
키고자 할 경우 왼쪽 그룹과 오른쪽 그룹 어디에 들어가도 상관없습니다.

퀵 정렬 알고리즘의 개념을 살펴봤으니 이제 좀 더 자세한 내용을 알아보겠습니다.

학생 A
피벗…그룹을 나누는 기준

175 170 160 168 165 170 155 150
키가 168 이하인 그룹 키가 168 이상인 그룹

160 165 155 150 175 170 168 170

155 이하 155 이상 170 이하 170 이상

155 150 160 165 170 168 170 175

150 155 160 165 168 170 170 175

[그림 6-19] 퀵 정렬 과정
224 C 알고리즘