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

2. 요소의 개수가 적은 그룹을 먼저 푸시하는 경우
예를 들어 b 에서 꺼낸 a[0] ~ a[7]은 a[0] ~ a[1], a[2] ~ a[7]로 나누어집니다. 그런 다음 요

소의 개수가 적은 {0, 1}을 먼저 푸시하면 스택은 c 의 상태가 됩니다. 먼저 팝되어 나누어지
는 배열은 요소의 개수가 많은 그룹 {2, 7}입니다( d ). 이렇게 하면 스택에 쌓여 있는 데이터
의 최대 개수는 4가 됩니다( g ).

요소의 개수가 적은 그룹을 먼저 푸시합니다.

{0, 7} {0, 7}을 분할 {0, 1}, {2, 7} {2, 7}을 분할 {6, 7}, {2, 5} {2, 5}를 분할

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

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

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

일반적으로 요소의 개수가 적은 배열일수록 적은 횟수로 분할을 종료할 수 있습니다. 따라서
1번과 같이 요소의 개수가 많은 그룹을 나누기보다는 요소의 개수가 적은 그룹을 먼저 나누

면 스택에 쌓여 있는 데이터의 최대 개수를 줄일 수 있습니다. 이때 1, 2번의 경우 모두 스택에
넣고 꺼내는 횟수는 같지만 스택에 쌓이는 데이터의 최대 개수는 달라집니다. 1번의 경우 배
열의 요소 개수가 n이라고 하면 스택에 쌓이는 데이터의 최대 개수는 log n보다 적습니다. 따

라서 요소의 개수가 백만 개여도 스택의 최대 용량은 20개면 충분합니다.

Q15 실습 6-9, 6-10의 quick 함수를, 요소의 개수가 적은 그룹을 먼저 나누는 함수로 수정하세요.
연습
문제
Q16 퀵 정렬은 요소의 개수가 적은 배열에 대해서는 처리가 아주 빠르게 진행되지는 않는다고
알려져 있습니다. Q15에서 작성한 두 quick 함수를 나눈 그룹의 요소 개수가 9개 이하이면 단순
삽입 정렬로 동작하는 함수로 수정하세요.

06•정렬 239