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

실습 6-10 •완성 파일 chap06/quick_nr.c
01 /*--- 퀵 정렬을 비재귀적으로 구현한 프로그램 ---*/
02 void quick (int a[], int left, int right)
03 {
04 IntStack lstack; /* 나눌 첫 요소 인덱스의 스택 */
05 IntStack rstack; /* 나눌 끝 요소 인덱스의 스택 */
06
07 Initialize(&lstack, right - left + 1);
스택의 생성
08 Initialize(&rstack, right - left + 1);
09
10 Push(&lstack, left);
11 Push(&rstack, right);
12
13 while(!IsEmpty(&lstack)) {
14 int pl = (Pop(&lstack, &left), left); /* 왼쪽 커서 */
15 int pr = (Pop(&rstack, &right), right); /* 오른쪽 커서 */
16 int x = a[(left + right) / 2]; /* 피벗은 가운데 요소 */
17 do {
18 while(a[pl] < x) pl++;
19 while(a[pr > x) pr--;
실행 결과
20 if(pl <= pr) {
퀵 정렬
21 swap(int, a[pl], a[pr]); 실습 6-8, 6-9와 같습니다. 요소 개수 : 9
22 pl++; x[0] : 5
23 pr--; x[1] : 8
24 } x[2] : 4
25 } while(pl <= pr); x[3] : 2
x[4] : 6
26
x[5] : 1
27 if(left < pr) { x[6] : 3
28 Push(&lstack, left); /* 왼쪽 그룹 범위의 */ x[7] : 9
29 Push(&rstack, pr); /* 인덱스를 푸시 */ x[8] : 7
30 } 오름차순으로 정렬했습니다.
31 if(pl < right) { x[0] = 1
x[1] = 2
32 Push(&lstack, pl); /* 오른쪽 그룹 범위의 */
x[2] = 3
33 Push(&rstack, right); /* 인덱스를 푸시 */ x[3] = 4
34 } x[4] = 5
35 } x[5] = 6
36 Terminate(&lstack); x[6] = 7
37 Terminate(&rstack); x[7] = 8
x[8] = 9
38 }

06•정렬 233