[자료구조] 삽입정렬이란?

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편입니다. 그렇다면 다른 접근 방법에 대해서 생각해볼 필요성이 있습니다.

 

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?

 

삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때, 훨씬 효율적으로 작동합니다.

 

삽입정렬 이미지

 

삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬이라고 부릅니다.

더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정합니다.

 

정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위에 삽입된다는 점이 특징입니다.

 

소스 코드로 보시면 이해가 수월하실 것입니다.

 

소스코드

# 삽입정렬

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
    # i 인덱스부터 j는 뒤로 이동합니다.
    for j in range(i, 0, -1):
        # 바로 이전거랑 비교한다. 바로 이전이 가장 시점 상 가장 작은 수
        # 그래서 맨 처음 7이랑 5를 비교해서 참이므로 스와핑이 진행되는 것이다.
        if array[j] < array[j-1]: # 5 < 7
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
print(array)

 

삽입 정렬(Insertion Sort)은 정렬되지 않은 리스트를 정렬된 부분과 비교하여 적절한 위치에 삽입하는 정렬 알고리즘입니다. 

 

아래는 주어진 리스트를 사용하여 삽입 정렬을 진행하는 과정을 표로 나타낸 것입니다. 

 

원래 리스트는 `[7, 5, 9, 0, 3, 1, 6, 2, 4, 8]`입니다.

 

 

단계	현재 리스트	정렬된 부분
초기	[7, 5, 9, 0, 3, 1, 6, 2, 4, 8]	[]
1단계	[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]	[5]
2단계	[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]	[5, 7]
3단계	[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]	[5, 7, 9]
4단계	[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]	[0, 5, 7, 9]
5단계	[0, 5, 7, 9, 3, 1, 6, 2, 4, 8]	[0, 3, 5, 7, 9]
6단계	[0, 3, 5, 7, 9, 1, 6, 2, 4, 8]	[0, 1, 3, 5, 7, 9]
7단계	[0, 1, 3, 5, 7, 9, 6, 2, 4, 8]	[0, 1, 3, 5, 6, 7, 9]
8단계	[0, 1, 3, 5, 6, 7, 2, 4, 8]	[0, 1, 2, 3, 5, 6, 7, 9]
9단계	[0, 1, 2, 3, 5, 6, 7, 4, 8]	[0, 1, 2, 3, 4, 5, 6, 7, 9]
10단계	[0, 1, 2, 3, 4, 5, 6, 7, 8]	[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

위 표에서 굵게 표시된 원소는 현재 비교되고 이동되는 원소를 나타냅니다. 삽입 정렬은 정렬되지 않은 리스트를 하나씩 들면서 해당 원소를 정렬된 부분에 삽입하는 과정을 반복하여 리스트를 정렬합니다.

 

결과적으로, 리스트가 정렬된 순서로 변경됩니다.