정렬 - 삽입정렬

[삽입정렬]

전체에서 하나씩 올바른 위치에 "삽입" 하는 방식

 

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만

삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식임

 

[4, 6, 2, 9, 1]  # 정렬되지 않은 배열

1단계 : [4, 6, 2, 9, 1] 
        4는 현재 정렬되어 있는 원소입니다. 
			  그럼 이제 새로운 원소 6을 받습니다.
        4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다.
       [4, 6, 2, 9, 1]

이제 한 바퀴를 돌린 상태입니다.
이 과정에서 새로운 원소인 4, 6은 현재 정렬된 상태입니다.
이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다.

2단계 : [4, 6, 2, 9, 1]
        4, 6 은 현재 정렬되어 있는 원소입니다.
        그럼 이제 새로운 원소인 2를 받습니다.
        4, 6, 2 가 되는데 6 > 2 이므로 둘을 변경합니다.
        4, 2, 6 가 되는데 4 > 2 이므로 둘을 변경합니다.
       [2, 4, 6, 9, 1]

3단계 : [2, 4, 6, 9, 1]
        2, 4, 6 은 현재 정렬되어 있는 원소입니다.
        그럼 이제 새로운 원소인 9를 받습니다.
        2, 4, 6, 9 가 되는데 6 < 9 이므로 그대로 냅둡니다.
       [2, 4, 6, 9, 1]

4단계 : [2, 4, 6, 9, 1]
        2, 4, 6, 9 은 현재 정렬되어 있는 원소입니다.
        그럼 이제 새로운 원소인 1을 받습니다.
        2, 4, 6, 9, 1 가 되는데 9 > 1 이므로 둘을 변경합니다.
        2, 4, 6, 1, 9 가 되는데 6 > 1 이므로 둘을 변경합니다.
        2, 4, 1, 6, 9 가 되는데 4 > 1 이므로 둘을 변경합니다.
        2, 1, 4, 6, 9 가 되는데 2 > 1 이므로 둘을 변경합니다.
       [1, 2, 4, 6, 9]

 

 

 

---

문제)

다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 삽입 정렬을 이용해서 정렬하시오.

 

 

 

 

풀이)

array[i - j - 1] > array[i - j] 라면 두 값을 변경해주고

아니라면 이미 앞에 있는 원소들이 정렬이 되었으므로 더 비교할 이유가 없기 때문에 나가기

input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return


insertion_sort(input)
print(input) # [1, 2, 4, 6, 9]

[시간복잡도]

O(N^2)

그러나, 버블정렬과 다른 면이 있음

버블정렬과 선택정렬은 최선이든 최악이든 항상 O(N^2)만큼의 시간이 걸렸지만

최선의 경우에는 Ω(N)만큼의 시간 복잡도가 걸림

거의 정렬된 배열이 매개변수로 들어간다면 break문에 의해

더 많은 원소와 비교하지 않고 탈출할 수 있기 때문!