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

a ０ １ ２ ３ ４ ５ ６ ７ ８
5 8 4 2 6 1 3 9 7
 분할
5 3 4 2 1 6 8 9 7
left pr pl right

b ０ １ ２ ３ ４ c ５ ６ ７ ８
5 3 4 2 1 6 8 9 7
 분할  분할
1 3 2 4 5 6 7 9 8
left pr pl right left pr pl right

… 생략 … … 생략 …

[그림 6-21] 퀵 정렬

요소의 개수가 1개인 그룹은 더 이상 그룹을 나눌 필요가 없으므로 요소의 개수가 2개 이상인
그룹만 나누면 됩니다. 따라서 아래처럼 배열을 반복해서 나누게 됩니다.

1. pr이 a[0]보다 오른쪽에 있으면(left < pr) 왼쪽 그룹을 나눕니다.
2. pl이 a[8]보다 왼쪽에 있으면(pl < right) 오른쪽 그룹을 나눕니다.

가운데 그룹(a[pr + 1] ~ a[pl – 1])은 나눌 필요가 없습니다(분할 대상에서 제외됩니다).

조금만 더!

left < pr, pl < right는 모두 그룹의 개수가 1개인 경우에는 성립하지 않는 조건입니다. 다시 말해 요소의
개수가 2개 이상인 그룹만 나누기 위해 필요한 조건입니다.

퀵 정렬은 앞에서 공부했던 8퀸 문제와 마찬가지로 분할 정복 알고리즘이므로 재귀 호출을

사용하여 구현할 수 있습니다. 실습 6-9는 퀵 정렬 프로그램입니다. quick 함수는 배열 a, 나
눌 구간의 첫 번째 요소(left), 마지막 요소(right)의 인덱스를 매개변수로 받습니다.

실습 6-9 •완성 파일 chap06/quick.c
01 /* 퀵 정렬 */
02 #include <stdio.h>
03 #include <stdlib.h>
04 #define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)
05
06 /*--- 퀵 정렬 함수 ---*/

06•정렬 229