셸 정렬

Preface

 

오늘은 다음날 공부할 시간이 없을 것 같아 한 파트를 추가로 업로드한다.

 

이번 파트에선 셸 정렬에 대해 공부했다.

 

불과 몇 시간 전 단순 삽입 정렬을 직접 계산할 땐 계산할 부분이 너무 많아서 복잡하게 느껴진다는 생각을 했었는데, 셸 정렬을 사용하여 계산을 하자 확실히 원소들을 정렬하기 쉬워졌다는 것을 느낄 수 있었다.

 

또한, 셸 정렬의 앞 부분을 읽어보며 아무리 원소들을 그룹으로 나누어 정렬한다고 한들 이들이 순서 없이 다시 합쳐지면 결국 단순 삽입 정렬과 동일해질 것 같다는 생각이 들어 직접 두 가지 방법으로 계산을 해보기도 했는데,

 

뒷 부분에 이러한 문제점을 완화시킬 수 있는 수열을 사용한 셸 정렬이 소개되어 있어 셸 정렬의 효율성을 인정할 수 있었다.

 

처음 정렬 알고리즘을 공부할 땐 정말 어려웠지만, 한 번 시간을 들여 기본적인 구조를 생성하는 코드를 이해하고 나니 전보다 수월하게 진도를 나갈 수 있게 된 것 같다.

---

 

- 단순 삽입 정렬의 특징

1) 장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 빠름

2) 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아짐

 

 

- 셸 정렬 : 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한 후 정렬된 그룹을 합치는 작업을 반복하는 알고리즘

1) 단순 삽입 정렬의 장점은 살리고 단점은 보완함

2) 정렬 횟수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어 효율적임

→ 서로 떨어져 있는 원소를 교환하므로 안정적이지 않다. 

 

 

- h-정렬 : 셸 정렬 과정에서 수행하는 각각의 정렬

→ 4-정렬, 2-정렬, -1정렬 등

 

 

- 셸 정렬 코드

from typing import MutableSequence


def shell_sort(a: MutableSequence) -> None:
    n = len(a)
    h = n // 2
    while h > 0:
        for i in range(h, n):
            j = i - h
            tmp = a[i]
            while j >= 0 and a[j] > tmp:
                a[j + h] = a[j]
                j -= h
            a[j + h] = tmp
        h //= 2


if __name__ == '__main__':
    print('셸 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    shell_sort(x)

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

 

- h값이 서로 배수가 되지 않도록 해야 원소가 충분히 뒤섞여 효율 좋은 정렬이 가능하다.

→ but, h의 초깃값이 지나치게 크면 효과가 없으므로 배열의 원소 수인 n을 9로 나누었을 때 그 몫을 넘지 않도록 정하는 것이 좋다.

 

 

- (h * 3 + 1)의 수열을 사용한 셸 정렬 코드

from typing import MutableSequence


def shell_sort(a: MutableSequence) -> None:
    n = len(a)
    h = 1

    while h < n // 9:
        h = h * 3 + 1

    while h > 0:
        for i in range(h, n):
            j = i - h
            tmp = a[i]
            while j >= 0 and a[j] > tmp:
                a[j + h] = a[j]
                j -= h
            a[j + h] = tmp
        h //= 3


if __name__ == '__main__':
    print('셸 정렬을 수행합니다(h * 3 + 1의 수열 사용).')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    shell_sort(x)

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')