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

06-5 셸 정렬

셸 정렬은 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘
입니다.

단순 삽입 정렬의 특징
다음 배열에서 단순 삽입 정렬을 수행한다고 가정합니다.

1 2 3 4 5 0 6

2, 3, …, 5의 순서대로 선택하며 정렬합니다. 여기까지는 이미 정렬을 마친 상태이기 때문에

요소의 이동(대입)은 발생하지 않습니다. 그래서 5까지의 정렬은 빨리 마칠 수 있습니다. 그러
나 0을 삽입하려면 그림 6-14처럼 총 6회에 걸쳐 요소를 이동해야 합니다.

1 2 3 4 5 0 6
①~⑤ … 0보다 작은 요소를 만날 때까지 왼 ①
쪽 요소를 하나씩 대입하는 작업을
반복합니다. 1 2 3 4 5 5 6
⑥ … 멈춘 위치에서 0을 대입합니다. ②
1 2 3 4 4 5 6
③
1 2 3 3 4 5 6
④
1 2 2 3 4 5 6
⑤
0 1 2 3 4 5 6
⑥
[그림 6-14] 단순 삽입 정렬에서 요소 0의 이동 과정

다음은 단순 삽입 정렬의 특징을 정리한 것입니다.

ⓐ 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라집니다. (장점)
ⓑ 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아집니다. (단점)

06•정렬 217