[파이썬 자료구조] 쉘정렬(Shell sort)

쉘 정렬(Shell sort)는 삽입 정렬에 전처리 과정을 추가한 것입니다.

전처리과정이란 작은 값을 가진 원소들을 앞쪽으로 옮겨서 큰 값들을 배열의 뒷쪽에 있게 하는 과정입니다.

전처리과정에서 일정한 간격으로 떨어진 원소들에 대해 삽입정렬을 수행합니다. 일정한 간격을 h-sort라고 합니다.

4-정렬은 인덱스0, 4, 8 한덩어리로 만들고 인덱스1, 5, 9를 한덩어리로 만들어서 수행하는 정렬입니다.

인덱스에 4를 더한것들을 모아서 한덩어리로 만드는겁니다. 그림에서 같은 색깔로 되어있는 부분이 한덩어리입니다.

같은 색깔내에서 삽입정렬을 수행합니다. 그러면 작은 값은 앞으로 큰 값은 뒤에 위치하게 됩니다.

이제 4-정렬에서 2-정렬로 바꿔서 다시 삽입정렬을 수행합니다. 그다음은 1-sort 결과적으로 정렬된 리스트를 얻습니다.

쉘 정렬의 수행시간

최악의 경우에 O(N^2)의 수행시간을 가지고 최선은 O(n^1.5)의 수행시간을 가집니다.

def shell_sort(L):
    gap = len(L)//2
    while gap > 0:
        for i in range(gap, len(L)):
            j = i
            while j >= gap and L[j-gap] > L[j]:
                L[j], L[j-gap] = L[j-gap], L[j]
         j -= 

1단계. 일정한 간격 gap을 리스트의 길이의 절반으로 해서 수행

2단계 삽입정렬 수행

3단계. gap을 다시 절반으로 나눠서 수행

이과정을 반복하면 정렬된 리스트를 얻을 수 있습니다.