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

32 putchar('\n');
33 }
34 printf("피벗 이상의 그룹\n"); /* 피벗 이상의 그룹 */
35 for(i = pr + 1; i < n; i++) /* a[pr + 1] ~ a[n – 1] */
36 printf("%d ", a[i]);
37 putchar('\n');
38 }
39
40 int main(void)
41 {
42 int i, nx;
43 int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
44 puts("배열을 나눕니다.");
45 printf("요소 개수 : ");
46 scanf("%d", &nx);
47 x = calloc(nx, sizeof(int)); /* 요소의 개수가 nx인 int형 배열을 생성 */
48 for(i = 0; i < nx; i++) {
49 printf("x[%d] : ", i);
50 scanf("%d", &x[i]);
51 }
52 partition(x, nx); /* 배열 x를 분할 */
53 free(x); /* 배열을 해제 */
54
55 return 0;
56 }

퀵 정렬

앞에서는 배열을 피벗을 기준으로 나누기만 했습니다. 이 방법을 좀 더 발전시키면 퀵 정렬
알고리즘이 됩니다. 그림 6-21은 이 아이디어를 그림으로 나타낸 것입니다. 요소가 9개인 배
열을 나누면 a 처럼 왼쪽 그룹(a[0] ~ a[4])과 오른쪽 그룹(a[5] ~ a[8])으로 나누어집니다. 그러

면 이 두 그룹을 다시 같은 방법으로 나눕니다( b , c ). 즉, b 는 a[0] ~ a[4]를 다시 두 그룹
으로 나누고 c 는 a[5] ~ a[8]을 다시 두 그룹으로 나눕니다.

228 C 알고리즘