삽입 정렬(Insertion Sort) - 파이썬 코드 구현

Insertion sort python code implemetation
삽입 정렬을 파이썬 코드로 구현해 보자.

---

삽입 정렬 (Insertion sort)

위키피디아에 나온 정의를 참고해 보자.

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n^2) 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

위의 예시를 보면, (b)에서, 3번째 블록에 있는 2가 미리 정렬된 길이 2짜리 배열에 '삽입'되는 것을 볼 수 있다.

이때, 삽입되는 블록은 이미 정렬된 배열들의 값들과의 비교가 이루어진다. (b)의 과정을 스텝별로 보면,

1. 3번째 블록의 '2'가 2번째 블록의 '7'과 자리를 바꾼다
2. 2번째 블록의 '2'(자리가 바뀜)가 1번째 블록의 '3'과 자리를 바꾼다.
3. 1번째 블록의 '2'는 1번째 블록이므로 자리바꾸기를 멈춘다.

삽입되는 블록은, 자신의 위치보다 1만큼 작은 블록과 값을 비교하여 자신이 더 작으면 자리를 바꾸다가 자신보다 더 작은 값을 가진 블록과 만나면 자리바꾸기를 멈춘다. 그 자리가 새로 삽입되는 블록의 올바른 위치이기 때문이다.

그럼 삽입 정렬을 파이썬 코드로 구현해보자.

# Insertion sort implementation
import sys #for sys.maxsize

array1 = [4,3,9,1,5,6,7,22,3243,436,56,4,73,45,24,23,5]
array2 = [100]


#
# Helper functions
#
# swap, print_array
#

def swap(array, a, b):
    array[a], array[b] = array[b], array[a]

def print_array(input):
    for i in range(len(input)):
        print(input[i], end=' ')
    print()    

#
# Main sorting function : 
#

def insert_sort(arr):
    for i in range(len(arr)):

        for j in range(i):
            if arr[i-j] < arr[i-j-1]:
                swap(arr, i-j, i-j-1)
            else: 
                # prevent redundant compare
                # inserted index is in the right place
                break

    return arr

print_array(array1)

array3 = insert_sort(array1)
insert_sort(array3)

print_array(array3)