삽입 정렬(Insertion sort)

삽입정렬

시간복잡도	공간복잡도
전체 요소를 순회하기 위해 N 검색 범위를 넓혀가며 전체 요소까지 비교하기 위해 N N x N = O(N²)	비교 후 배열 내 스왑을 하기 위해 O(1)

 

정렬 범위를 한칸씩 확장하여 새로 비교할 값을 이미 정렬된 값과 비교하여 정렬하는 알고리즘

 

[7, 4/, 5, 1, 3]

 

예를 들어 이렇게 주어진 배열을 정렬한다고 해보자.

 

배열은 총 5개의 요소를 가지고 있다.

이 중 맨 앞의 2개 요소만 두고 첫번째 비교를 시작한다.

 

7과 4중 4가 더 작기 때문에 둘의 위치를 바꿔준다.

[4, 7/, 5, 1, 3]

첫번째 순회가 끝났다.

 

두번째 순회를 시작한다.

이제 검색범위를 넓혀 3번째 요소, 2번 인덱스에 있는 요소를 추가하여 뒤에서부터 비교한다.

7과 5중 5가 더 작기 때문에 자리를 바꿔준다.

[4, 5, 7/, 1, 3]

다음으로 0번과 1번을 비교한다.

4가 5보다 작기 때문에 자리를 바꿔주지 않고 두번재 순회를 끝낸다.

 

이런 식으로 또 그다음번 요소를 추가하여 뒤에서부터 앞으로 비교해가며 새로운 요소의 위치를 찾아준다.

 

 

구현

def insertion_sort(input_array):
    print('>>', input_array)

    for i in range(1, len(input_array)):
        for j in range(i, 0, -1):
            if input_array[j] < input_array[j - 1]:
                input_array[j - 1], input_array[j] = input_array[j], input_array[j - 1]
            print(f'{j}와 {j-1} 비교 결과: {input_array}')

    return input_array


if __name__ == '__main__':
    insertion_sort([7, 4, 5, 1, 3])
    
    
>> [7, 4, 5, 1, 3]
1와 0 비교 결과: [4, 7, 5, 1, 3]
2와 1 비교 결과: [4, 5, 7, 1, 3]
1와 0 비교 결과: [4, 5, 7, 1, 3]
3와 2 비교 결과: [4, 5, 1, 7, 3]
2와 1 비교 결과: [4, 1, 5, 7, 3]
1와 0 비교 결과: [1, 4, 5, 7, 3]
4와 3 비교 결과: [1, 4, 5, 3, 7]
3와 2 비교 결과: [1, 4, 3, 5, 7]
2와 1 비교 결과: [1, 3, 4, 5, 7]
1와 0 비교 결과: [1, 3, 4, 5, 7]

 

비교할 대상 두개가 필요하므로 i는 1번부터 시작하여 0번과 1번을 비교한다. i는 탐색 범위를 나타낸다.

이후 정렬 범위를 늘릴 때마다 내부 loop의 범위가 넓어지며 j는 탐색범위의 맨 뒤부터 앞쪽으로 비교하며 자리를 바꾼다.

 

최적화

매 순회마다 앞부분의 탐색범위가 정렬된다. 따라서 새로운 비교 요소가 뒤에서부터 탐색을 시작하다가 더 작은 요소를 만나게 된다면 그 앞의 요소까지는 탐색할 필요가 없다.

 

def insertion_sort(input_array):
    print('>>', input_array)

    for i in range(1, len(input_array)):
        j = i
        while 0 < j and input_array[j] < input_array[j - 1]:
            input_array[j - 1], input_array[j] = input_array[j], input_array[j - 1]
            print(f'{j}와 {j - 1} 비교 결과: {input_array}')
            j -= 1

    return input_array
    
    
>> [7, 4, 5, 1, 3]
1와 0 비교 결과: [4, 7, 5, 1, 3]
2와 1 비교 결과: [4, 5, 7, 1, 3]
//1와 0 비교 결과: [4, 5, 7, 1, 3] 생략
3와 2 비교 결과: [4, 5, 1, 7, 3]
2와 1 비교 결과: [4, 1, 5, 7, 3]
1와 0 비교 결과: [1, 4, 5, 7, 3]
4와 3 비교 결과: [1, 4, 5, 3, 7]
3와 2 비교 결과: [1, 4, 3, 5, 7]
2와 1 비교 결과: [1, 3, 4, 5, 7]
//1와 0 비교 결과: [1, 3, 4, 5, 7] 생략

 

 

 

참고

https://www.dalecoding.com/algorithms/insertion-sort

삽입 정렬 (Insertion Sort) | 달레코딩