[알고리즘] 삽입 정렬(Insertion Sort) in Python

카드 놀이를 할 때 나도 모르게 카드를 정렬한 적이 있는가? 그때 어떠한 방식으로 정렬을 했는지 생각해 보자.

 

정렬 알고리즘에서 세 번째로 배워 볼 것은 바로 삽입 정렬이다. 삽입 정렬이 어떻게 동작하는지 알아 보고 실제 코드로 구현해 보자.

 

📌 정의

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

삽입 정렬(Insertion Sort)은 손에 쥔 카드를 정렬하는 방식과 매우 유사한 간단한 정렬 알고리즘이다. 배열은 실제로 정렬된 부분과 정렬되지 않는 부분으로 나뉜다. 정렬되지 않는 부분의 값을 선택하여 정렬된 부분의 올바른 위치로 옮긴다.

Insertion Sort - GeeksforGeeks

 

쉽게 말하여, 정렬 안 된 값이 정렬된 부분의 올바른 위치로 찾아가는 알고리즘이다.

Insertion Sort - Wikipedia

 

📌 주의점

삽입 정렬과 선택 정렬의 공통점, 차이점을 알아 보자.

개인적으로 이 둘을 헷갈릴 때가 종종 있다.

공통점

• 주어진 리스트를 정렬된 부분과 정렬되지 않는 부분으로 나눈다는 공통점이 있다.

차이점

• 삽입 정렬은 정렬된 부분의 올바른 위치를 찾는 것이다.
• 선택 정렬은 정렬되지 않는 부분의 최솟값을 찾는 것이다.

 

📌 동작 과정

빨간색 박스는 현재 위치를 의미하고, 검은색 박스는 정렬이 완료된 데이터를 의미한다.

현재 위치에서, 왼쪽에 위치한 값을 비교해 가면서 올바른 위치로 찾아가는 과정이다.

Insertion Sort - Wikipedia

 

📌 구현 in Python

# 삽입 정렬 함수 정의
def insertion_sort(array):
    n = len(array) # 배열의 길이를 n으로 할당
    for i in range(1, n):  # 현재 교환할 인덱스로 i를 할당
        for j in range(i, 0, -1):  # 인덱스 i부터 1까지 1씩 감소
            if array[j - 1] > array[j]:  # 왼쪽 인덱스의 값보다 현재 인덱스의 값이 클 경우
                array[j - 1], array[j] = array[j], array[j - 1]  # 두 값을 서로 교환
            else: # 작은 숫자가 이미 앞에 있으면 정렬이 된 것이므로
                break  # 안쪽 반복물 탈출
            # print(array)  # 배열의 정렬 과정 출력
    return array

# 테스트 코드
if __name__ == "__main__":
    array = [6, 5, 3, 1, 8, 7, 2, 4] # 임의의 배열 할당
    print(f"BEFORE INSERTION SORT: {array}") # 정렬되지 않은 배열 화면 출력
    insertion_sort(array) # 삽입 정렬 함수 실행
    print(f"AFTER INSERTION SORT: {array}") # 정렬된 배열 화면 출력

BEFORE INSERTION SORT: [6, 5, 3, 1, 8, 7, 2, 4]
AFTER INSERTION SORT: [1, 2, 3, 4, 5, 6, 7, 8]

 

위의 코드 중에서 10번 줄의 각주 # print(array)를 해제하고 다시 파일을 실행하면 아래의 과정을 볼 수 있다.

# 처음의 배열
[6, 5, 3, 1, 8, 7, 2, 4]

# 반복문을 돌며 정렬되어 가는 배열
[5, 6, 3, 1, 8, 7, 2, 4]
[5, 3, 6, 1, 8, 7, 2, 4]
[3, 5, 6, 1, 8, 7, 2, 4]
[3, 5, 1, 6, 8, 7, 2, 4]
[3, 1, 5, 6, 8, 7, 2, 4]
[1, 3, 5, 6, 8, 7, 2, 4]
[1, 3, 5, 6, 7, 8, 2, 4]
[1, 3, 5, 6, 7, 2, 8, 4]
[1, 3, 5, 6, 2, 7, 8, 4]
[1, 3, 5, 2, 6, 7, 8, 4]
[1, 3, 2, 5, 6, 7, 8, 4]
[1, 2, 3, 5, 6, 7, 8, 4]
[1, 2, 3, 5, 6, 7, 4, 8]
[1, 2, 3, 5, 6, 4, 7, 8]
[1, 2, 3, 5, 4, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

반복할수록 인덱스에 위치한 값이, 바로 왼쪽의 값과 비교해가면서 위치가 점점 이동하는 것을 확인할 수 있다.