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

이 과정을 거치고 나면 스캔하기 위한 커서의 시작 위치는 아래와 같이 변경할 수 있습니다(나
눌 대상의 범위가 좁아졌습니다).

left right
a 8 7 6 5 4 3 2 1 0

첫 요소 · 가운데 요소 · 끝 요소를 정렬합니다.
b 0 7 6 5 4 3 2 1 8

가운데 요소와 끝에서 두 번째 요소를 교환합니다.

피벗
c 0 7 6 5 1 3 2 4 8
pl pr
피벗 이하 피벗 이상
여기부터 스캔합니다. 여기부터 스캔합니다.

[그림 6-27] 피벗의 선택과 나눌 범위의 축소 과정

1. 왼쪽 커서 pl의 시작 위치 … left ⇨ left + 1
2. 오른쪽 커서 pr의 시작 위치 … right ⇨ right - 2

이 방법은 나눌 그룹의 크기가 한쪽으로 치우치는 것을 피하면서도 나눌 때 스캔할 요소를
3개씩 줄일 수 있다는 장점이 있습니다. 이렇게 하면 이 방법을 사용하지 않을 때보다는 조금
더 빠른 속도로 정렬할 수 있습니다.
방법 1, 2를 사용한 프로그램은 연습문제 Q17, Q18에서 다룹니다.

시간 복잡도
퀵 정렬은 배열을 조금씩 나누어 보다 작은 문제를 해결하는 과정을 반복하므로 시간 복잡도

는 O(n log n)입니다. 다만 정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간 복잡도
가 증가하는 경우도 있습니다. 예를 들어 매번 단 하나의 요소와 나머지 요소로 나누어지면 n
2
번의 분할이 필요합니다. 따라서 최악의 시간 복잡도는 O(n )이 됩니다.

연습 Q17 방법 1을 사용하여 Q16의 quick 함수(재귀, 비재귀 버전)를 수정하세요.
문제
Q18 방법 2를 사용하여 Q16의 quick 함수(재귀, 비재귀 버전)를 수정하세요.

06•정렬 241