[자료구조 with Python] 14. 정렬 알고리즘(7), 쉘 정렬(Shell Sort)

 
 
 
 
사실, 오늘 포스팅으로 다룰 쉘 정렬은 지난 포스팅에서 언급한 퀵 정렬 이전, 그러니까 삽입 정렬 바로 이후에 다루어야 했던 포스팅이다. 그럼에도 불구하고 지금에서야 쉘 정렬(Shell Sort)에 대해 이제야 다루게 된 것은... 엊그제 무렵 쉘 정렬에 대해 알게 되어서다... (포스팅 구성 다 꼬이네..)
 
 
 
1. 쉘 정렬(Shell Sort) 개요
 
쉘 정렬은 삽입 정렬과 연관이 있다고 필자가 위에서 힌트처럼 언급을 했으니, 다시 삽입 정렬을 살펴보자. 삽입 정렬은 좌측 또는 우측 끝단에 위치한 원소를 제외한 나머지 원소 중 하나를 선택한 뒤, 극값과의 크기 비교를 통해 자리 교체를 진행하는 정렬 방식이다. 그런데 원소의 교대 방식이 버블 정렬과 상당히 유사하기 때문에, 특수한 상태의 배열 정렬를 진행함에 있어 효율성이 낮아질 수 밖에 없다. 
 
         9, 7, 5, 3, 1  : 1번의 비교 및 원소 교대
=>    7, 9, 5, 3, 1   : 2번의 비교 및 원소 교대
=>    5, 7, 9, 3, 1   : 3번의 비교 및 원소 교대
=>    3, 5, 7, 9, 1   : 4번의 비교 및 원소 교대
=>    1, 3, 5, 7, 9   :  총 10번의 비교 및 원소 교대
 
 
위와 같이 완전 역순으로 나열된 배열의 경우, 삽입 정렬의 시간 복잡도인 O(N^2)에 완전하게 들어맞는 횟수로 비교가 진행된다. "저 비교 횟수를 줄일 수 있는 방법이 없을까?"를 열심히 고민하던 도날드 쉘(Donald Shell)이라는 분이 삽입 정렬을 개선한 정렬 알고리즘을 고안하게 되었고, 이 분의 이름을 따서  쉘 정렬(Shell Sort)이라고 부르게 되었다. 참고로 퀵 정렬이 나오기 전까지는 가장 빠른 선형 자료 정렬 알고리즘이었다고 한다.
 

Wikipedia가 아주 친절하게 주요 내용에 대해 Highlight 처리를 해 두었다.

 
 
Wikipedia에서 언급한대로, 쉘 정렬 역시 삽입 정렬의 일종이기 때문에, 원소를 교대(Exchange)하면서 삽입(Insertion)한다는 점은 삽입 정렬과 크게 다르지 않다. 다만, 차이점이 있다면 삽입 정렬이 바로 옆에 있는 원소와의 대소 비교 및 교대를 진행하는 것과 달리, 쉘 정렬은 바로 옆의 원소가 아니라 조금 멀리 떨어진 원소와의 비교 및 자리 교대를 진행한다는 것이다.
 
역시나 설명은 그림이 제일 편하다. 그림부터 그려보자.
 
13, 11, 9, 7, 5, 3, 1이라는 배열을 오름차순 배열하려한다. 대신, 비교하는 원소는 바로 옆이 아니라 3칸 떨어진 원소와 비교를 진행한다고 하자. 
 
[ 비교 원소 거리: 3 ]
 
       13, 11, 9, 7, 5, 3, 1      :  두 원소의 비교 및 교대
=>   7, 11, 9, 13, 5, 3, 1      :  두 원소의 비교 및 교대
=>   7,  5, 9, 13, 11, 3, 1     : 두 원소의 비교 및 교대 
=>   7, 5, 3, 13, 11, 9, 1      : 두 원소의 비교 및 교대
=>   7, 5, 3, 1, 11, 9, 13
 
원소 거리를 3으로 지정하고 삽입 정렬을 수행한 결과, 4번의 비교로 7, 5, 3, 1, 11, 9, 13이라는 배열이 나타났다. 이제 2칸 떨어진 원소와의 비교로 정렬을 진행해보자.
 
[ 비교 원소 거리: 2 ]
       7, 5, 3, 1, 11, 9, 13  :  원소 비교 및 자리 교대
=>   3, 5, 7, 1, 11, 9, 13  :  원소 비교 및 자리 교대
=>   3, 1, 7, 5, 11, 9, 13  :   11은 7 및 3과 순서대로 비교를 진행하나, 7보다 크기 때문에  자리 교대 없음.
=>   3, 1, 7, 5, 11, 9, 13  :   9는 5, 1과 순서대로 비교를 진행하나, 5보다 크기 때문에 자리 교대 없음.
=>   3, 1, 7, 5, 11, 9, 13  :   13 역시 마찬가지.
 
두 번 정렬 시, 원소 및 자리 교대는 단 2차례만 일어났으며, 조금 더 정렬된 배열이 나타난다. 이제 1칸 떨어진 원소와의 비교를 진행해보자.
 
[ 비교 원소 거리: 1 ]
 
      3, 1, 7, 5, 11, 9, 13  : 원소 비교 및 자리 교대
=>  1, 3, 7, 5, 11, 9, 13  : 자리 교대 없음
=>  1, 3, 7, 5, 11, 9, 13  : 원소 비교 및 자리 교대
=>  1, 3, 5, 7, 11, 9, 13  : 자리 교대 없음
=>  1, 3, 5, 7, 11, 9, 13  : 원소 비교 및 자리 교대
=>  1, 3, 5, 7, 9, 11, 13  
 
마지막으로, 비교하는 원소의 거리가 1인 경우, 3번의 교대만으로 완전 정렬이 이루어졌다. 즉, 총 4 + 2+ 3 = 9 번의 비교로 모든 원소가 정렬이 되었는데, 이를 삽입정렬에서 동일하게 진행하면 15번의 비교가 이루어진다. 비교 횟수가 획기적으로 줄어든 것을 확인할 수 있다. 
 
혹시 비교하는 원소의 거리를 감소시킬 때, 1씩 감소시키지 않고 절반 값으로 감소시키면 어떨까? 
 
[ 비교 원소 거리: 3 ]
13, 11, 9, 7, 5, 3, 1   : 원소 교대 1회
7, 11, 9, 13, 5, 3, 1   : 원소 교대 1회
7, 5,
9
, 13, 11, 3, 1   : 원소 교대 1회
7, 5, 3, 13, 11, 9, 1   : 원소 교대 1회
7, 5, 3, 1, 11, 9, 13   : 원소 교대 1회
1, 5, 3, 7, 11, 9, 13   : 총 5회 원소 교대
 
[ 비교 원소 거리: 1 ]
1, 5, 3, 7, 11, 9, 13 : 원소 교대 없음
1, 5, 3, 7, 11, 9, 13 : 원소 교대 1회
1, 3, 5, 7, 11, 9, 13 : 원소 교대 없음
1, 3, 5, 7, 11, 9, 13 : 원소 교대 없음
1, 3, 5, 7, 11, 9, 13 : 원소 교대 1회
1, 3, 5, 7, 9, 11, 13 : 원소 교대 없음,  총 7회 교대로 정렬
 
쉘 정렬이 특이한 점은, 동일한 배열에 대해서도 비교하는 원소 사이의 거리를 감소하는 방법에 따라 비교 횟수가 조금씩은 차이가 발생한다는 것이다.
 
비교한 원소의 거리를 쉘 정렬에서는 Gap이라는 용어로 표시하는데, 쉘 정렬은 Gap을 감소 방법에 따라 세부적으로 나뉘어진다. 기본적인 쉘 정렬은 Gap을 절반씩 감소시키면서 사용한다.
 
이제 쉘 정렬을 구현해보자.
 
 
 
2. 쉘 정렬(Shell Sort) 구현
 
 
병합 정렬과 퀵 정렬을 - 머리싸매가면서 - 구현해봤다면, 쉘 정렬의 구현은 크게 어렵지 않다. 먼저 함수의 뼈대부터 만들어보자. 기본 쉘 정렬은 배열을 절반으로 뽀개어(?) 두 원소를 차례로 비교/교대하며, Gap을 감소시킨 다음 동일한 절차를 반복한다. 
 

def shell_sort(arr: list ) -> None:
 
    gap = len(arr) // 2  # 첫 gap은 배열 절반 크기로 설정
 
    # gap 크기가 1이 될 때까지 Loop 수행
    while gap > 0:
 
        # 쉘 정렬 시 비교를 진행할 원소의 Index
        cursor = gap
 
        # gap 값 출력
        print(f" * Gap Value: {gap}")
        print("---------------------")
 
        while cursor < len(arr): 
 
            # cmp_idxcursor index와 비교할 값의 index 지정: cursor - gap * N
            cmp_idx = cursor - gap
 
            while cmp_idx >= 0:
 
                # 비교 Index 출력
                print(f" - 선택 Index: {cursor}, 비교 Index: {cmp_idx}")
                cmp_idx -= gap
 
            print()
            # cursor 값 증가
            cursor += 1
 
        # gap 감소
        gap //= 2

 
 
위 코드를 수행하면, 아래와 같이 gap 값에 따라 비교하는 두 원소의 Index 위치가 출력된다.
 

 
 
Index 비교를 위한 매칭은 큰 문제가 없는 듯 하니, 이제 비교 및 자리 교대 코드만 가장 안쪽의 while 문에 작성해주면 된다. 단, 자리 교대가 일어나면 비교해야하는 index도 변하기 때문에 cursor 변수를 대신하여 움직일 임시 cursor 변수가 하나 있어야 한다.
 

def shell_sort(arr: list ) -> None:
   #count = 0
 
    gap = len(arr) // 2  # 첫 gap은 배열 절반 크기로 설정
 
    # gap 크기가 1이 될 때까지 Loop 수행
    while gap > 0:
 
        # 쉘 정렬 시 비교를 진행할 원소의 Index
        cursor = gap
 
        while cursor < len(arr): 
            cmp_idx = cursor - gap
            
            # gap 비교 시, cursor 이동을 고려한 변수 추가
            tmp_cursor = cursor
 
            while cmp_idx >= 0:
                if arr[tmp_cursor] < arr[cmp_idx]:
                   #count += 1
                    arr[tmp_cursor], arr[cmp_idx] = arr[cmp_idx], arr[tmp_cursor]
                   #print(arr)
                    tmp_cursor -= gap
                cmp_idx -= gap
 
            cursor += 1
        gap //= 2
 
   #print(f"\n * 총 원소 교대 횟수: {count}")
    return None

 
위 코드에서 Line 22의 print(arr)은 값의 변동이 일어난 뒤 배열의 모습을 출력한다. 이를 개요의 마지막 배열에 적용하여 실행하면 아래와 같은 결과가 나타난다.
 

 
 
 
 
3. 최적의 gap 값 적용하기
 
서두의 개요 마지막 부분에서 언급한대로, 쉘 정렬은 gap에 사용될 값을 어떠한 수열로 고르느냐에 따라 성능에 차이가 난다. 이러한 이유로 평균 시간 복잡도도 명확히 계산하기가 까다로운데, 여러 수열을 적용한 쉘 정렬의 시간 복잡도 평균 수식이 O(N^1.25)가 나온다고 한다. 앞서 구현한 코드는 일반 쉘 정렬을 구현한 것을, Loop 2개가 중첩되어 사용되었으므로 최악의 경우 O(N^2)가 나타난다.
 
쉘 정렬의 경우 배열의 크기가 증가할수록 수행 시간도 비례해서 증가할 수 밖에 없는 구조다보니, 수열이라도 조절하여 수행 시간을 줄이려는 시도가 많이 있었던 듯 하다. 아래는 쉘 정렬에 적합한 수열과 수열에 따른 쉘 정렬의 종류를 나타낸다.
 

Shell Sort Name	Sequence
Originial Shell Sort	N/2, N/4, N/8 ... N/(2^k), 1
Knuth's increments	1, 4, 13, 40, 121 ... (3k + 1)
Hibbard's increments	1, 3, 7, 15, 31 ... (2k + 1)
Papernov & Stasevich increment	1, 3, 5, 9, 17, 33, 65...
Papernov & Stasevich increment	1, 3, 5, 9, 17, 33 ... 2^(k-1) - 1 (단, k >= 2 일 때,)

 

---

 
다음 포스팅에서는 선형 자료의 정렬 마지막인 Heap 정렬에 대해 알아보려한다.
 
 
 
End.