셸 정렬

셸 정렬

23, 10, 4, 1 갭(gap)이 있는 셸 정렬
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)
최선 시간복잡도	O(n log n) (most gap sequences) O(n log2n) (best known worst-case gap sequence)
평균 시간복잡도	갭 시퀀스에 따라
공간복잡도	О(n) 전체, O(1) 보조

셸 정렬 알고리즘 컬러 바

셸 정렬(영어: shell sort)은 가장 오래된 정렬 알고리즘의 하나이다. 이름은 1959년 이 방법을 발표한 창안자 도널드 셸의 이름을 따서 붙여졌다. 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다.

셸 정렬은 다음과 같은 삽입 정렬의 성질을 이용, 보완한 삽입정렬의 일반화로 볼 수 있다.

• 삽입 정렬은 입력되는 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다.
• 삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다.

셸 정렬은 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행한다. 즉, 매개변수 값에 따라 부파일(Subfile)이 발생하며, 매개변수값을 줄이며 이 과정을 반복하고 결국 매개변수 값이 1이면 정렬은 완성된다.

셸 정렬은 다음과 같은 과정으로 나눈다.

1. 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다.
2. 데이터를 다시 잘게 나누어서 삽입 정렬한다.
3. 이렇게 계속 하여 마침내 정렬이 된다.

셸 정렬에서 데이터를 나누는 값(이하 N)은 보통 전체에서 2로 나누는 값으로 진행한다. 그러나 3을 나누고 1을 더하는 경우가 더 빠르다고 알려져 있다. 즉 N/2 보다는 N/3+1이 더 빠르다.

알고리즘의 개요

1. 자료리스트를 2차원배열로 나열한다.
2. 각 배열의 열들을 정렬한다.

예제

[2 5 3 4 3 9 3 2 5 4 1 3]로 리스트가 주어졌을 때 이 리스트를 셸 정렬로 정렬해 보자.

1. 3행으로구성된 행렬로 나열하여 열단위로 정렬한다.

   2 5 3 4	⇒	2 4 1 2
   3 9 3 2		3 5 3 3
   5 4 1 3		5 9 3 4

2. 정렬된 3행 행렬을 6행렬로 나열하여 마찬가지로 열단위로 정렬한다.

   2 4	⇒	1 2
   1 2		2 3
   3 5		3 4
   3 3		3 4
   5 9		3 5
   3 4		5 9

3. 정렬된 행렬을 한 열단위로 나열해서 삽입 정렬한다.

   1 2 2 3 3 4 3 4 3 5 5 9

   ⇒

   1 2 2 3 3 3 3 4 4 5 5 9

   이 때, 자료가 멀리 이동될 필요가 없다는 장점이 있다.

소스 코드

파이썬(Python)

def Shellsort(arr):

    h = 1
    while h < len(arr):
        h = 3*h + 1
    h = h//3

    while h > 0:
        for i in range(h,len(arr)):
            k=i-h
            key=arr[i]
            while k>=0 and key < arr[k]:
                arr[k+h] = arr[k]
                k=k-h
            arr[k+h] = key
        h = h//3
    return arr

자바(Java)

public static void shellSort(Comparable[] array) {
   //각 단계의 시작값
   int[] cols = {1,5,12,23,62,145,367,815,1968,4711,11969,27901,84801,
                 213331,543749,1355339,3501671,8810089,21521774,
                 58548857,157840433,410151271,1131376761,2147483647};
   int c;
   for (c = 0; cols[c] < array.length / 4; c++)
       ;

   // 매개변수 값에 대한 순환
   for (; c >= 0; c--) {
      int step = cols[c];
      for (int i = step; i < array.length; i++) {
         Comparable m = array[i];
         int j;
         for (j=i; j>=step; j-=step) {
            if (isLastBigger(array[j-step],m))
               break;
            array[j] = array[j-step];
         }
         array[j] = m;
      }