[Sorting] 쉘 정렬, Shell Sort

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 쉘 정렬 (Shell Sort)

• 삽입 정렬을 이용하여 작은 값을 가진 원소들을 리스트의 앞부분으로 옮기며 큰 값을 가진 원소들이 리스트의 뒷부분에 자리 잡도록 만드는 과정을 반복하여 정렬하는 알고리즘
• 삽입 정렬에 전처리 과정을 추가한 것
• 전처리 과정은 삽입 정렬이 현재 원소를 앞부분에 삽입하기 위해 이웃하는 원소들끼리 비교하며 한 자리씩 이동하는 단점을 보완하기 위해 고안되었으며 각 단계에서 일정 간격으로 떨어진 원소들에 대해 삽입 정렬을 수행
• 간격이 h인 원소들끼리 정렬하는 것을 h-정렬(h-Sort)라고 함
• 대표적인 간격의 순서(h-Sequence)

  Shell	n/2, n/4, ... , 1 (나누기 2를 계속하여 1이 될 때까지의 순서)
  Hibbard	2^k - 1, 2^(k-1) -1, ... , 7, 3, 1
  Knuth	(3^k - 1)/2, ... , 13, 4, 1
  Sedgewick	... , 109, 41, 19, 5, 1
  Marcin Ciura	1750, 701, 301, 132, 57, 23, 10, 4, 1

   

Shell Sort, 출처 위키피디아

- 수행 시간

• 쉘 정렬의 수행 시간은 간격을 어떻게 설정하느냐에 따라 달라짐
• Hibbard 간격을 사용하면 수행 시간이 O(n^1.5)
• Marcin Ciura 간격이 대체적으로 좋은 성능을 보임
• 쉘 정렬의 정확한 수행 시간을 측정하는 것은 아직 풀리지 않은 문제, 최적(Optimal) 간격을 찾고 나서야 쉘 정렬의 정확한 수행 시간을 측정할 수 있기 때문
• 일반적으로 쉘 정렬은 입력이 그리 크지 않은 경우에 매우 좋은 성능을 보임