정렬 알고리즘 - 셸 정렬(Shell Sort)

셸 정렬

• 단순 삽입 정렬의 장점을 살리고, 단점을 보완한 정렬 알고리즘
• 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법
• 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다.

장점

• 정렬을 맞쳤거나 정렬을 마친 상태에 가까워지면 정렬 속도가 매우 빨라진다.

단점

• 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아진다.

 

셸 정렬 알고리즘의 예제

 

정렬 알고리즘 시간 복잡도 비교

 

Python Code

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 Code

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;
      }