[알고리즘] 파이썬으로 삽입정렬 구현하기 :: insertion sort in python

파이썬으로 삽입정렬 구현하기 :: insertion sort in python

1. 삽입정렬이란? What is a insertion sort?

삽입 정렬은 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

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

2. insertion sort in python

이를 python3에서 구현하면 다음과 같다.

# insertion sort
def insert(v) :
    for i in range(1,len(v)) :
        j=i-1
        while(j>=0 and v[i]<v[j]):
            j-=1
        v.insert((j + 1), v[i])
        del v[i+1]
    return v

2번째 요소부터 앞에 요소들과 비교하여 본인의 자리를 찾아간다.

* 삽입 정렬(insertion sort) 예시

> insert([7, 6, 1, 8, 5, 3, 9, 4])

[1, 3, 4, 5, 6, 7, 8, 9]

v[i] : 정렬의 대상이 되는 요소

j : v[i]의 적절한 위치

i = 1 : 

j = 0 : 6 7 1 8 5 3 9 4

i = 2 : 

j = 0 : 1 6 7 8 5 3 9 4

i = 3 :

j = 3 : 1 6 7 8 5 3 9 4

i = 4 :

j = 1 : 1 5 6 7 8 3 9 4

i = 5 :

j = 1 : 1 3 5 6 7 8 9 4

i = 6 :

j = 6 : 1 3 5 6 7 8 9 4

i = 7 :

j = 2 : 1 3 4 5 6 7 8 9