[5.22] 06-4 단순 삽입 정렬

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

단순 삽입 정렬 알아보기

for i in range(1, n):

tmp = a[i]

tmp를 (0, i) 사이의 알맞은 위치에 삽입한다. 

from typing import MutableSequence

def insertion_sort(a:MutableSequence) -> None:
    n = len(a)
    for i in range(1, n):
        j = i
        std = a[i]
        while j > 0 and a[j-1] > std:
            a[j] = a[j-1]
            j -= 1
        a[j] = std
    return a

a = [3, 4, 5, 1, 2]
print(insertion_sort(a))

이진 삽입 정렬 binary insertion sort

from typing import MutableSequence

def 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
    return a 

a = [3, 4, 9, 1, 2]
print(insertion_sort(a))

bisect.insort 를 이용할 수도 있다

from typing import MutableSequence
import bisect

def binary_insertion_sort(a:MutableSequence) -> None:
    for i in range(1, len(a)):
        bisect.insort(a, a.pop(i), 0, i)
    return a

print(binary_insertion_sort([3, 4, 2,1]))