29. 파이썬 - 삽입 정렬(insertion sorting)

삽입 정렬은 손안에 카드를 정렬하는 방식과 유사합니다.

 

[8, 5, 2, 4, 6] 카드가 있다면.. 

 

첫 번째 카드는 해줄 게 없고, 

 

두 번째 카드인 5를 뽑아서, 5보다 큰 카드는 pass 하고, 8 앞에 삽입하고...
[5, 8, 2, 4, 6]

 

세 번째 카드인 2를 뽑아서, 2보다 큰 카드는 pass, 5 앞에 삽입하고...
[2, 5, 8, 4, 6]

 

4를 뽑아서, ..., 5 앞에 삽입하고... 
[2, 4, 5, 8, 6]

 

8을 뽑지만, 8 앞은 8보다 작은 수만 있으니.... 바로 stop
[2, 4, 5, 8, 6]

 

6을 뽑아서, 8 앞에 삽입합니다. 
[2, 4, 5, 6, 8]

 

원리는 뽑고 큰 수는 pass 하고 삽입이지만,
구현은 뽑고 큰 수는 밀고 삽입입니다. 

def insertion_sort(array):
    """삽입 정렬"""

    for i in range(1, len(array)):
        temp = array[i]  # 뽑고
        j = i
        while j > 0 and array[j - 1] > temp:
            array[j] = array[j - 1]  # 밀고
            j -= 1
        array[j] = temp  # 삽입
        print(i, j, array)


insertion_sort([8, 5, 2, 4, 6])

1 0 [5, 8, 2, 4, 6]
2 0 [2, 5, 8, 4, 6]
3 1 [2, 4, 5, 8, 6]
4 3 [2, 4, 5, 6, 8]