쉘정렬

• 삽입/선택/버블 정렬 알고리즘은 모든 다른 숫자들이 1칸 씩 이동해야 함
• 삽입 정렬을 이용해 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게 이동시키고, 동시에 앞부분의 큰숫자는 뒷부분으로 빠르게 이동

1. 간격을 이용

• 간격의 크기만큼 숫자들을 그룹으로 나눔
• 그룹별로 삽입 정렬을 수행
• 간격의 크기가 1이 될때 까지 간격을 줄여가며 반복

2. 소스코드

for each gap h = {h0>h1>...>hk=1}
  for i=h to n-1
    CurrentDlement = A[i]
    j = i;
    while (j>=h) and (A[j-h]>CurrentElement)
      A[j] = A[j-h]
      j = j-h
    A[j] = CurrentElement
return A

3. 시간복잡도

• 사용하는 간격에 따라 분석
  • 최악의 경우 시간 복잡도: 히바드(Hibbard)의 간격의 경우
    • O(n^1.5)
  • 지금까지 알려진 가장 좋은 성능을 보인 간격
    • Marcin Ciura
• 쉘정렬의 시간 복잡도는 아직 풀리지 않은 문제임