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

니다. 동일한 요소를 교환하는 시도가 의미 없어 보이지만 이 시도는 아무리 많아야 1회이므로

해도 괜찮습니다. 계속해서 스캔하면 pl, pr이 교차하면서 그룹을 나누는 과정을 마칩니다( e ).
만약 이런 의미 없어 보이는 시도를 줄이기 위해 같은 요소를 교환하지 않는다면 요소를 교환하기 전에 ‘pl, pr이 동일한
요소 위에 있는지’ 매번 검사해야 합니다.

실습 6-8은 지금까지의 아이디어를 바탕으로 배열을 나누는 프로그램입니다. 배열 가운데에
있는 요소를 피벗으로 정하고 색칠한 부분에서 그룹을 나눕니다.

실습 6-8 •완성 파일 chap06/partition.c

01 /* 배열을 나누는 프로그램 */
02 #include <stdio.h>
03 #include <stdlib.h>
04
05 #define swap(type, x, y) do { type t = x; x = y; y = t;} while(0)
06
실행 결과
07 /*--- 배열을 나누는 함수 ---*/
배열을 나눕니다.
08 void partition(int a[], int n) 요소 개수 : 9
09 { x[0] : 1
10 int i; x[1] : 8
11 int pl = 0; /* 왼쪽 커서 */ x[2] : 7
x[3] : 4
12 int pr = n – 1; /* 오른쪽 커서 */
x[4] : 5
13 int x = a[n / 2]; /* 피벗은 가운데 요소를 선택합니다. */
x[5] : 2
14 do { x[6] : 6
15 while(a[pl] < x) pl++; x[7] : 3
16 while(a[pr] > x) pr--; x[8] : 9
17 if(pl <= pr) { 배열 a를 피벗 x를 기준으로 피벗의 값은 5입니다.
18 swap(int, a[pl], a[pr]); 나눕니다. 피벗 이하의 그룹
1 3 2 4 5
19 pl++;
피벗과 일치하는 그룹
20 pr--; 5
21 } 피벗 이상의 그룹
22 } while(pl <= pr); 5 7 6 8 9
23 printf("피벗의 값은 %d입니다.\n", x);
24 printf("피벗 이하의 그룹\n"); /* 피벗 이하의 그룹 */
25 for(i = 0; i <= pl - 1; i++) /* a[0] ~ a[pl – 1] */
26 printf("%d ", a[i]);
27 putchar('\n');
28 if(pl > pr + 1) {
29 printf("피벗과 일치하는 그룹\n"); /* 피벗과 같은 그룹 */
30 for(i = pr + 1; i <= pl - 1; i++) /* a[pr + 1] ~ a[pl – 1] */
31 printf("%d ", a[i]);

06•정렬 227