필요한 위치에 삽입하면서 정렬하는 삽입정렬(insertion sort)

1. 개요

 

선택 정렬은 실제 사용하기에는 매우 느린편이다. 그렇다면 다른 접근 방법은 없을까?

 

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

 

삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉽지만, 구현 난이도가 더 어려운데, 하지만 선택 정렬에 비해 실행 시간 측면에서 효율적이라고 알려져있다

 

특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 "데이터가 거의 정렬되어 있을때" 매우 효율적이다

 

선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 그렇지 않다

 

삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬(insertion sort)이라고 부른다.

 

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

 

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

 

 

2. 예시를 통해 이해하는 삽입정렬

 

다음과 같은 배열 리스트에서 삽입 정렬을 수행한다고 생각해보자

 

 

삽입 정렬은 두번째 데이터부터 시작한다. 첫번째 데이터는 일단 정렬되어 있다고 생각한다

 

두번째 데이터인 5가 어떤 위치로 들어갈지 판단해야한다. 

 

7의 왼쪽으로 들어가거나, 오른쪽으로 들어가거나 2가지 경우만 존재한다. 5는 7보다 작으므로 오름차순으로 정렬하기 위해 7의 왼쪽에 삽입한다

 

 

 

이어서 3번째 데이터인 9가 어디에 들어갈지 판단한다. 삽입 가능한 위치는 5의 왼쪽, 오른쪽, 7의 오른쪽으로 3가지이다.

 

9는 5와 7보다 크므로 7의 오른쪽인 현재 위치 그대로 둔다

 

 

 

이어서 0이 어떤 위치에 들어갈지 판단한다

 

5의 왼쪽, 오른쪽

 

7의 오른쪽

 

9의 오른쪽 중 4가지이다. 가장 작기 때문에 5의 왼쪽에 삽입한다

 

 

 

이어서 3도 위와 똑같은 과정을 반복한다. 0과 5 사이에 삽입하면 된다

 

0,3,5,7,9,1,6,2,4,8

 

그 다음 1은 0과 3사이에 넣으면 된다

 

0,1,3,5,7,9 , 6,2,4,8

 

그 다음 6은 5와 7 사이에 넣고 2는 1과 3 사이에 넣으면 된다

 

0,1,2,3,5,6,7,9, 4,8

 

다음 4는 3과 5 사이에 넣으면 0,1,2,3,4,5,6,7,9,8

 

마지막으로 8은 7과 9 사이에 넣으면 0,1,2,3,4,5,6,7,8,9로 정렬이 완료된다

 

 

 

이와 같이 데이터 수가 n=10개 일때, 0~8까지 n-1=9개의 데이터를 적절한 위치에 삽입하는 과정을 반복하면, 모든 데이터가 정렬된다

 

삽입 정렬은 재미있는 특징이 있다

 

정렬이 이루어진 원소들은 항상 오름차순 상태를 유지하고 있다는 점이다

 

위 그림에서 빨간색으로 된 부분은 정렬이 이루어진 원소들인데 항상 오름차순으로 되어있음에 주목하라

 

그러므로 특정 데이터가 어떤 위치에 삽입될지 위치를 결정하고 싶을때, 왼쪽으로 1칸씩 이동하면서,

 

처음으로 특정 데이터보다 작은 값을 만나게 된다면.. 그 위치에서 멈추고 거기에 삽입하면 된다

 

 

그러므로 특정한 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태이므로, 자기 자신보다 작은 데이터를 만났다면 더 이상 데이터를 살펴볼 필요 없이 그 자리에 삽입하면 된다.

 

 

3. 구현 예시

 

위에서 설명한대로 

 

1번부터 n-1번까지 삽입시킬 원소를 선택하고.. 왼쪽으로 1칸씩 이동을 시킨다

 

왼쪽 원소와 비교를 하면서 왼쪽 원소가 더 크면 자리를 바꾸고

 

왼쪽 원소가 처음으로 더 작다면, 반복을 멈추고 다음 삽입시킬 데이터를 선택한다

 

#삽입 정렬

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

n = len(array) ##배열의 길이

for i in range(1,n): ##첫번째부터 끝까지 삽입시킬 데이터를 선택
    
    for j in range(i,0,-1): #i번째부터 1번까지 감소하면서.. 바로 왼쪽 원소 j-1번과 비교함
        
        if array[j] < array[j-1]: ##왼쪽 j-1번 원소가 더 크다면.. j번 원소를 왼쪽으로 1칸씩 이동함
            
            array[j],array[j-1] = array[j-1],array[j]
        
        else: ##처음으로 현재 j번째 원소가 왼쪽 원소보다 더 크다면.. 이동을 멈춘다
            
            break

print(array)
"""
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
"""

 

 

참고로 range()함수는 range(start,end,step)으로 세번째 매개변수 step은 -1이 들어가면

 

start부터 end+1까지 1씩 감소하면서 순회한다

 

 

4. 시간복잡도

 

반복문이 2중으로 사용되어 시간복잡도는 $O(n^{2})$

 

실제로 수행 시간을 테스트해보면 선택 정렬과 비슷한 시간이 소요된다.

 

하지만 삽입정렬은 현재 리스트가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다

 

최선의 경우는 O(N)에 동작한다. 

 

심지어 거의 정렬되어 있는 상태에서는 매우 빠른 정렬 알고리즘으로 알려진 퀵 정렬보다 더 강력하다

 

 

5. 연습문제

 

2750번: 수 정렬하기 (acmicpc.net)

2750번: 수 정렬하기

 

역시 $O(n^{2})$인 삽입정렬로도 해결할 수 있다

 

근데 버블, 선택정렬보다 더 느리게 나오는디?

 

from sys import stdin

n = int(stdin.readline())

array = []

for _ in range(n):
    
    i = int(stdin.readline())

    array.append(i)

for i in range(1,n):
    
    for j in range(i,0,-1):
        
        if array[j] < array[j-1]:
            
            array[j],array[j-1] = array[j-1],array[j]
        
        else:
            
            break

for num in array:
    
    print(num)