chapter 6 -3 단순 선택 정렬, 6 - 4 단순 삽입 정렬, 6 - 5 셸 정렬

1.단순 선택 정렬

가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

교환 과정은 다음과 같다.

아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택한다.

a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환한다.

# 단순 선택 정렬 알고리즘 구현하기
 
from re import I
from typing import MutableSequence
 
def selection_sort(a: MutableSequence) -> None:
    """단순 선택 정렬"""
    n = len(a)
    for i in range(n-1):
        min  = i  # 정렬할 부분에서 가장 작은 원소의 인덱스
        for j in range(i+1 , n):
            if a[j] < a[min]:
                min = j
        a[j], a[min] = a[min], a[i]  # 정렬할 부분에서 맨 앞의 원소와 가장 작은 원소를 교환
        
 

이 알고리즘은 서로 이웃하지 않는 떨어져 있는 원소를 교환하므로 안정적이지 않다.

예를 들어 배열 내 중복된 값이 있는 경우, 정렬이 필요 없는 데이터마저도 교환을 하게 되므로 안정적이지 않다.

 

2.단순 삽입 정렬

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘.

단순선택과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 점이 다르다.

장점 : 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상황에서는 속도가 아주 빠르다.

단점 : 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아진다.

 

# 단순 삽입 정렬 알고리즘 구현하기
 
from typing import MutableSequence
def insertion_sort(a:MutableSequence) -> None:
    """단순 삽입 정렬"""
    n = len(a)
    for i in range(1,n):
        j = i 
        tmp = a[i]
        while j > 0 and a[j - 1] > tmp:
            a[j] = a[j-1]
            j -= 1
        a[j] = tmp
 
if __name__ == '__main__':
    print('단순 삽입 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요.:'))
    x = [None] * num  # 원소 수가 num인 배열을 생성
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))
 
    insertion_sort(x)  # 배열 x를 단순 삽입 정렬
 
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')
 
 

이 알고리즘은 서로 떨어져 있는 원소를 교환하지 않으므로 안정적이라고 할 수 있다.

 

단순 삽입 정렬 알고리즘은 파이썬 표준 라이브러리 bisect모듈의 insort()함수로 제공된다.

 

버블, 선택, 삽입 알고리즘의 시간 복잡도는 모두 O(n2)로 프로그램의 효율이 좋지 않다.

이를 개선한 방법이 이진 삽입 정렬이다.

 

3.이진 삽입 정렬

이미 정렬을 마친 배열을 제외하고 원소를 삽입해야 할 위치를 검사하므로 비용을 줄일 수 있는 방법

 

# 이진 삽입정렬 알고리즘 구현하기
 
from typing import MutableSequence
 
def binary_insertion_sort(a: MutableSequence) -> None:
    """이진 삽입 정렬"""
    n = len(a)
    for i in range(1, n):
        key = a[i]
        pl = 0  # 검색범위의 맨 앞 인덱스
        pr = i-1  # 검색범위의 맨 끝 인덱스
 
        while True:
            pc = (pl + pr) // 2  # 검색범위의 가운데 원소 인덱스
            if a[pc] == key:   # 검색 성공
                break
            elif a[pc] < key:
                pl = pc +1  # 검색 범위를 뒤쪽 절반으로 좁힘
 
            else:
                pr = pc -1  # 검색 범위를 앞쪽 절반으로 좁힘
            
            if pl > pr:
                break
        
        pd = pc + 1 if pl <= pr else pr + 1  # 삽입해야 할 위치의 인덱스
 
        for j in range(i,pd,-1):
            a[j] = a[j-1]
        a[pd] = key 
 
if __name__ == "__main__":
    print("이진 삽입 정렬을 수행합니다.")
    num = int(input('원소 수를 입력하세요: '))
    x = [None] * num   # 원소 수가 num인 배열을 생성
 
    for i in range(num):
        x[i] = int(input(f"x[{i}]:"))
 
    binary_insertion_sort(x)   # 배열 x를 이진 삽입 정렬
 
    print("오름차순을 정렬했습니다.")
    for i in range(num):
        print(f'x[{i}] = {x[i]}')
 

 

4.셸 정렬

단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘

정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행 > 정렬된 그룹을 합치는 작업을 반복해 원소의 이동횟수를 줄이는 방법

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

# 셸 정렬 알고리즘 구현하기
 
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  # 원소 수가 num인 배열을 생성
 
    for i in range(num):
        x[i] = int(input('x[{i}]:'))
 
    shell_sort(x)  # 배열 x를 생성
 
    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i} = {x[i]}]')

h의 초깃값은 n // 2, while문을 반복할 때마다 다시 2로 나눈 값으로 업데이트(원소 수가 8이면 4-2-1)