단순 정렬

단순 선택 정렬

1. 아직 정렬하지 않는 부분에서 값이 가장 작은 원소를 선택한다.
2. 가장 작은 원소와 아직 정렬하지 않는 부분에서 맨 앞에 있는 원소를 교환한다.

-> 중복된 값으로 정렬이 필요 없는 데이터의 위치가 바뀌는 경우가 존재하여 안정적이지 않다.

단순 삽입 정렬

1. 주목된 원소보다 더 앞쪽에 들어가야 하는 자리로 해당 원소를 이동시킨다.
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
# n^2/2

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 = (pr + pl) // 2
            if a[pc] == key:
                break
            elif a[pc] < key:
                pl = pc + 1
            else:
                pr = pc - 1
            if pl > pr:
                break

        if pl <= pr:
            pd = pc + 1
        else:
            pd = pr + 1

        for j in range(i, pd, -1):
            a[j] = a[j - 1]
        a[pd] = key

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