[정렬 알고리즘] 단순 삽입 정렬(셔틀 정렬), 이진 삽입 정렬

단순 삽입 정렬이란?

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

- 원소의 비교 횟수와 교환 횟수는 모두 n² / 2번

 

단순 삽입 정렬의 진행 과정

1. 두 번째 원소인 4부터 주목한다. 4는 6보다 앞쪽에 위치해야 하기때문에 맨 앞에 삽입하고 6을 오른쪽으로 옮긴다.

2. 세 번째 원소인 1에 주목한다. 1은 4보다 앞쪽에 위치해야 하기때문에 맨 앞에 삽입하고 4와 6을 오른쪽으로 옮긴다.

3. 단순 삽입 정렬은 위와 같이 '아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입' 하는 과정을 반복한다. 

 

단순 삽입 정렬은 다음과 같이 종료 조건이 두 가지이다.

1. 정렬된 배열의 왼쪽 끝에 도달한 경우 -> 가장 값이 작은 것이다. 2. tmp보다 작거나 키값이 같은 원소 a[j - 1]을 발견한 경우 -> 그 앞쪽은 이미 정렬되어 스캔할 필요가 없다.

 

위 조건을 모두 성립할 동안 스캔 작업을 반복하는데, 반대의 의미로 해석하면 다음과 같다.

1. j가 0보다 큰 경우 2. a[j - 1]의 값이 tmp보다 큰 경우

 

단순 삽입 정렬 알고리즘 구현 코드

# 단순 삽입 정렬 알고리즘 구현하기

from typing import MutableSequence

def insertion_sort(a:MutableSequence) -> None:
    """단순 삽입 정렬"""
    n = len(a) # 배열의 길이를 담아줌
    for i in range(1, n): # 1에서 n-1까지 순회
        j = i # j에 i를 담아줌 (i는 1에서 n-1까지)
        tmp = a[i] # tmp에 a[i]번째를 담아줌 (a[i]번째는 두번째 원소부터 n-1번째 원소까지
        while j > 0 and a[j - 1] > tmp: # j가 0보다 크고, a[j-1]번째 원소가 tmp보다 클때 동안 진행(계속 스캔해야 하는 조건)
            a[j] = a[j - 1] # 왼쪽 원소를 선택한 원소의 자리에 담아줌
            j -= 1 # 왼쪽으로 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]}")

 

실행 결과

단순 삽입 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9

Process finished with exit code 0

 

i를 1부터 n - 1까지 증가시키는 이유: 정렬이 완료되고 나면 가장 값이 작은 원소는 맨 앞으로, 가장 큰 원소는 맨 뒤로 밀리기 때문

 

이진 삽입 정렬이란?

단순 삽입 정렬은 배열의 원소 수가 많아지면 원소 삽입에 필요한 비교, 교환 비용이 커짐. 그러나 이진 검색법을 사용하여 삽입 정렬을 하면 이미 정렬을 마친 배열을 제외하고 원소를 삽입할 위치를 검사하기때문에 비용을 줄일 수 있음. 

 

이진 삽입 정렬 알고리즘 구현 코드

# 이진 삽입 정렬 알고리즘 구현하기

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]}")

 

실행 결과

이진 삽입 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9

Process finished with exit code 0

 

위 코드는 직접 이진 삽입 정렬 알고리즘을 구현한 코드이다.

 

파이썬에서는 표준 라이브러리의 bisect 모듈에서 insort( ) 함수를 제공하는데, 이를 이용하여 단순 삽입 정렬 알고리즘을 사용할 수 있다.

이 함수를 사용하면 다음 코드와 같이 매우 간결하게 이진 삽입 정렬 알고리즘을 구현할 수 있다.

 

'bisect.insort' 함수를 사용한 이진 삽입 정렬 알고리즘 구현 코드

# 이진 삽입 정렬 알고리즘 구현(bisect.insort 사용)

from typing import MutableSequence
import bisect

def binary_insertion_sort(a: MutableSequence) -> None:
    """이진 삽입 정렬(bisect.insort 사용)"""
    for i in range(1, len(a)):
        bisect.insort(a, a.pop(i), 0, i)

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]}")

 

실행 결과

이진 삽입 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9

Process finished with exit code 0

 

bisect.insort( ) 함수의 사용법: bisect.insort(a, x, lo, hi)를 호출하면 a가 이미 정렬된 상태를 유지하며, a[lo]~a[hi] 사이에 x를 삽입.(만약 a 안에 x와 같은 값을 갖는 원소가 여러개이면 가장 오른쪽에 삽입)