알고리즘 - 쉘 정렬

쉘 정렬 (Shell Sort)

- 삽입 정렬을 간단하게 변형

- 멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시킴

- h-정렬 화일 : 모든 h번째 원소를 정렬한 화일

- 증가 순서의 예 : …, 1093, 364, 121, 40, 13, 4, 1

 

 

 

 

 

특징

- 순열 h가 1, 4, 13, 40, … 일 때, 쉘 정렬의 비교 횟수는 N 3/2 을 넘지 않음

- 제자리 정렬

- 멀리 떨어진 원소끼리 교환할 때 동일한 원소가 어디로 갈지 알 수 없으므로 불안정적

 

 

 

 

 

 

수행 과정