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

첫 번째 분할에 의해 배열이 왼쪽 그룹(a[0] ~ a[1])과 오른쪽 그룹(a[2] ~ a[7])으로 나누어집니

다. 여기서 오른쪽 그룹은 다시 왼쪽 그룹(a[2] ~ a[5])과 오른쪽 그룹(a[6] ~ a[7])으로 나누어집
니다. 배열을 나눈 다음에 수행하는 ‘스택에 푸시하는 부분’의 코드를 다시 보겠습니다.

if(left < pr) {
Push(&lstack, left); /* 왼쪽 그룹 범위의 */
Push(&rstack, pr); /* 인덱스를 푸시합니다. */
}

if(pl < right) {
Push(&lstack, pl); /* 오른쪽 그룹 범위의 */
Push(&rstack, right); /* 인덱스를 푸시합니다. */
}

두 if문은 아래의 순서대로 왼쪽 그룹 범위의 값과 오른쪽 그룹 범위의 값을 푸시합니다.

1. 왼쪽 그룹의 인덱스 left와 pr을 푸시합니다.
2. 오른쪽 그룹의 인덱스 pl과 right를 푸시합니다.

그림 6-24는 정렬이 시작될 때부터 정렬이 끝날 때까지의 스택 변화를 나타낸 것입니다.

왼쪽 그룹을 먼저 푸시합니다.
왼쪽 그룹을 먼저 푸시합니다(분할을 나중에 수행).
오른쪽 그룹을 나중에 푸시합니다(분할을 먼저 수행).
{0, 7} {0, 7}을 분할 {0, 1}, {2, 7} {2, 7}을 분할 {2, 5}, {6, 7} {6, 7}을 분할

6 7
2 7 2 5 2 5
0 7 0 1 0 1 0 1 0 1
a b c d e f

{2, 5}를 분할 {2, 3}, {4, 5} {4, 5}를 분할 {2, 3}을 분할 {0, 1}을 분할 종료

4 5
2 3 2 3
0 1 0 1 0 1 0 1
g h i j k l
[그림 6-24] 스택의 변화 과정(1)

06•정렬 237