Shell 정렬 (셸 정렬)

Shell 정렬

Shell 정렬은 “분할 증분 정렬”(diminishing Incremental Sort)이라고도 불리는 방법으로 삽입정렬을 원래 리스트를 더 작은 서브리스트들로 나눠서 정렬함으로써 성능을 향상시키는 방법이다. 즉 리스트를 더 작은 조각들로 나눈다음 각각을 삽입정렬을 사용하여 정렬한다. 이 때 서브리스트들을 나누는 기준을 정하는 방법이 독특한데, 연속된 원소들로 구성된 서브리스트를 나누는게 아니라 i개씩 건너뛰고 원소들을 선택하여 서브리스트를 만든다. 이 때 i는 gap이라고도 불리운다.

9개의 원소가 있는 리스트를 삽입정렬을 사용해서 정렬하는 과정을 살펴보자.

54  26  93  17  77  31  44  55  20
^^          ^^          ^^          <-- sublist 1
    ^^          ^^          ^^      <-- sublist 2
        ^^          ^^          ^^  <-- sublist 3
-----------------------------------
17  26  93  44  77  31  54  55  20  <-- sorted sublist 1
17  26  93  44  55  31  54  77  20  <-- sorted sublist 2
17  26  20  44  55  31  54  77  93  <-- sorted sublist 3
-----------------------------------
17  20  26  44  55  31  54  77  93  <-- sort with full insertion sort
    ^^^^^^
17  20  26  31  44  55  54  77  93 
            ^^^^^^^^^^
17  20  26  31  44  54  55  77  93    
                    ^^^^^^        

각 서브리스트를 정렬하는 것은 길이가 짧으므로 상대적으로 간단히 수행된다. 이렇게 각 서브리스트를 정렬한 최종 결과는 완전히 정렬된 리스트가 아니다. 하지만, 서브리스트 정렬이 완료된 결과는 처음에 비해서 부분적으로 정렬된 형태에 많이 가까워져있는 형태가 되었다. 삽입정렬의 경우 이렇게 부분적으로나마 정렬된 상태에 가까우면 가까울수록 효율이 좋아진다.

각 서브리스트의 길이는 편의상 리스트 길이의 절반, 1/4, 1/8… 과 같은 식으로 점점 줄여나가면서 서브리스트 정렬을 반복하는데, 결국 gap은 1이 되어 리스트 전체에 대한 삽입 정렬을 최종적으로 수행하게 된다.

def gapInsertionSort(alist, interval, startposition):
    # the 'nth' element in sublist is alist[startposition + gap*n]
    for index in range(startposition, len(alist), interval):
        position = index
        currentValue = alist[index]
        while position >= interval and alist[position-interval] > currentValue:
            alist[position] = alist[position - interval]
            position -= interval
        alist[position] = currentValue

def shellSort(alist):
    interval = len(alist) // 2
    while interval > 0:
        for i in range(interval):
            gapInsertionSort(alist, interval, i)
        interval = interval // 2

alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
shellSort(alist)

일반적인 쉘 정렬의 수행성능을 계산하는 일은 이 글의 수준에서 다루기는 어렵지만, (O(n^{\frac{2}{3}}))가량 된다고 볼 수 있다.