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

05-2절의 recur 함수는 데이터를 임시 저장하기 위해 ‘스택’을 사용했습니다. 이번 퀵 정렬도

마찬가지로 ‘스택’을 사용합니다. quick 함수는 다음 2개의 스택을 사용하고 있습니다.

1. lstack … 나눌 범위의 왼쪽 끝 요소의 인덱스를 저장하는 스택입니다.
2. rstack … 나눌 범위의 오른쪽 끝 요소의 인덱스를 저장하는 스택입니다.

이 스택을 생성하는 부분이 초록색 박스로 표시한 부분입니다. 두 스택의 용량은 right – left
+ 1입니다(나눌 배열의 요소 개수). 실제로 필요한 용량에 대해서는 다음에 자세히 알아보겠습니다.

프로그램의 주요 부분을 오른쪽에 나타냈
Push(&lstack, left); 0
습니다. 그림 6-22와 비교하면서 살펴보 Push(&rstack, right);
1
세요. while(!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
0 lstack에 left를, rstack에 right를 푸시 /* 중략 : a[left] ~ a[right]를 나눕니다. */
2
합니다. 그림의 a 에서 볼 수 있듯이 lstack if(left < pr) {
Push(&lstack, left); /* 왼쪽 그룹 범위의 */
에 푸시되는 값은 0, rstack에 푸시되는 값 Push(&rstack, pr); /* 인덱스를 푸시합니다. */
}
은 8입니다. if(pl < right) {
Push(&lstack, pl); /* 오른쪽 그룹 범위의 */
Push(&rstack, right); /* 인덱스를 푸시합니다. */
}
1 lstack에서 팝한 값을 left에 대입한 다
}
음 그 left의 값을 다시 pl에 대입합니다
(rstack도 같은 과정을 거칩니다). 그 결과 left와 pl의 값은 0, right와 pr의 값은 8이 됩니다. 이 값
은 정렬할 배열의 범위를 의미합니다. 이렇게 값을 설정하면 a[0] ~ a[8]이 배열 왼쪽 그룹

(a[0] ~ a[4])과 오른쪽 그룹(a[5] ~ a[8])으로 나누어집니다.

2 첫 번째 if문에서 lstack, rstack에 각각 0과 4를 푸시하고 두 번째 if문에서 각각 5와 8을

푸시합니다. 그 결과 스택은 c 상태가 되고 그런 다음 while문에 의해 루프 본체( 1 , 2 )가 반
복됩니다.

1 lstack에서 5가 팝되어 left와 pl에 대입되고, rstack에서 8이 팝되어 right와 pr에 대입됩

니다( d ). 이 과정을 거치고 나면 배열의 한 부분(a[5] ~ a[8])으로 나누어집니다. 즉, a[5] ~
a[6]의 왼쪽 그룹과 a[7] ~ a[8]의 오른쪽 그룹으로 나누어집니다.

234 C 알고리즘