[삽입 정렬] Insertion sort - python

출처: https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

Insertion Sort

---

삽입 정렬(Insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입한다.

배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다.

선택정렬이나 거품정렬과 같은  알고리즘과 비교하면,  안정적인 정렬이고 in-place 알고리즘이다.

(공간복잡도: 원소 자체를 저장하는 메모리 말고 추가적으로 필요한 임시 메모리에 대한 복잡도)

def insert_sort(a):
    for i in range(1, len(a)):
        j = i-1
        key = a[i]
        while a[j] > key and j >= 0:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = key
    return a
 
a = [31, 25, 12, 22, 11]
 
print(insert_sort(a))
 

Key: 25

before [31, 25, 12, 22, 11]

aftre [25, 31, 12, 22, 11]

Key: 12

before [25, 31, 12, 22, 11]

aftre [12, 25, 31, 22, 11]

Key: 22

before [12, 25, 31, 22, 11]

aftre [12, 22, 25, 31, 11]

Key: 11

before [12, 22, 25, 31, 11]

aftre [11, 12, 22, 25, 31]

[11, 12, 22, 25, 31]