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

왼쪽, 오른쪽의 각 그룹을 다시 나누기 위해 초록색 박스로 표시한 부분에서 2회의 재귀 호출

이 있는 것을 제외하면 앞에서 작성한 실습 6-8과 거의 같습니다.
퀵 정렬은 서로 이웃하지 않고 멀리 떨어져 있는 요소를 교환해야 하므로 안정적이지 않습니다.

연습 Q13 아래 형식으로 동작하는 quick_sort 함수를 구현하세요. 두 번째 매개변수인 n은 요소의
문제 개수입니다.

void quick_sort(int a[], int n);

보충수업 6-1 퀵 정렬에서 분할 과정 출력하기
앞에서 작성한 퀵 정렬 프로그램은 진행 과정을 출력하지 않습니다. 퀵 정렬을 수행하는 quick 함수를
실습 6C-1처럼 수정하면(초록색 박스로 표시한 부분 추가) 배열을 나누는 모습이 출력되어 이해하기가
조금 더 쉬워집니다.

실습 6C-1 •완성 파일 chap06/quick_v.c
01 /*--- 배열의 분할 과정을 출력하는 퀵 정렬 프로그램 ---*/
초록색 박스로 표시한 부분의 실행 결과
02 void quick (int a[], int left, int right)
a[0]~a[8] : {5, 8, 4, 2, 6, 1, 3, 9, 7}
03 { a[0]~a[4] : {5, 3, 4, 2, 1}
04 int pl = left; /* 왼쪽 커서 */ a[0]~a[2] : {1, 3, 2}
05 int pr = right; /* 오른쪽 커서 */ a[0]~a[1] : {1, 2}
06 int x = a[(pl + pr) / 2]; /* 피벗(가운데 요소) */ a[3]~a[4] : {4, 5}
a[5]~a[8] : {6, 8, 9, 7}
07
a[5]~a[6] : {6, 7}
08 int i;
a[7]~a[8] : {9, 8}
09 printf("a[%d]~a[%d] : {", left, right);
10 for(i = left; i < right; i++)
11 printf("%d ", a[i]);
12 printf("%d}\n", a[right]);
13
14 do {
15 while(a[pl] < x) pl++;
16 while(a[pr] > x) pr--;
17 if(pl <= pr) {
18 swap(int, a[pl], a[pr]);
19 pl++;
20 pr--;

06•정렬 231