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

2 lstack과 rstack에 {5, 6}과 {7, 8}을 푸시합니다( e ).

스택에 푸시한 값은 나눌 배열의 ‘첫 요소’와 ‘끝 요소’의 인덱스입니다. 배열을 나누는 작업이
끝나면 왼쪽 그룹 인덱스와 오른쪽 그룹 인덱스를 푸시합니다. 그리고 스택에서 팝한 범위를
나누는 작업을 반복하여 정렬을 수행합니다. 스택이 비면 정렬이 끝납니다( n ).

０ １ ２ ３ ４ ５ ６ ７ ８
5 8 4 2 6 1 3 9 7

０ １ ２ ３ ４ ５ ６ ７ ８
5 3 4 2 1 6 8 9 7
０ １ ２ ３ ４ ５ ６ ７ ８
1 3 2 4 5 6 7 9 8

０ １ ２ ３ ４ ５ ６ ７ ８
1 2 3 4 5 6 7 8 9
０ １
1 2

lstack ... 나눌 배열의 첫 요소 인덱스를 left 스택에 푸시합니다.
rstack ... 나눌 배열의 끝 요소 인덱스를 right 스택에 푸시합니다.
스택에서 팝한 값 0, 8을 left, right에 대입하여 배열을 나눕니다.
{0, 8} {0, 8}을 분할 {0, 4}, {5, 8} {5, 8}을 분할 {5, 6}, {7, 8} {7, 8}을 분할 {5, 6}을 분할

7 8
5 8 5 6 5 6
0 8 0 4 0 4 0 4 0 4 0 4
a b c d e f g

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

3 4
0 2 0 2 0 2 0 1
h i j k l m n

[그림 6-22] 비재귀적으로 구현한 퀵 정렬에서 배열의 분할과 스택의 변화

06•정렬 235