[알고리즘] 삽입정렬

 

Python Code

def insert_sort(x):
    for i in range(1, len(x)):
        j = i - 1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1] = x[j]  # 비교 값을 오른쪽으로 이동
            j = j - 1 # 앞쪽 값을 비교하기 위해 -1
        x[j+1] = key
    return x

 

삽입 정렬은 현재 값을 기준으로 앞쪽의 값들과 비교해 자기 자리에 삽입하는 정렬 알고리즘이다. 

삽입 정렬의 구체적인 알고리즘은 다음과 같다.

 

- 삽입 정렬은 두 번째 자료부터 알고리즘을 수행한다.

- 두 번째 자료(인덱스)부터 시작해 그 앞쪽의 값들과 비교해 삽입될 자리를 찾는다.

- 자리를 찾은 후 현재 값을 넣은 다음 나머지 값들은 한 칸씩 이동시킨다.(오른쪽)

- 세 번째 자료가 현재 값이 되고, 앞쪽 값인 첫 번째, 두 번째 값과 비교해 자리를 찾는다.

- 자리를 찾아 삽입되고 다른 값들은 옆으로 이동시킨다.

- 네 번째 값도 마찬가지로 왼쪽의 값들(1,2,3번째 값)과 비교해 삽입될 자리를 찾는다.

- 나머지 값들도 같은 방식으로 알고리즘이 수행된다.

 

 

위의 코드에서 보면 key가 선택된 값이 되고 j 인덱스가 왼쪽의 비교하는 값들이 된다.

j 번째 비교 값과 key 값을 비교했을 때 key가 작다면 j 번 값을 +1(즉 오른쪽으로 하나씩 이동) 시킨다. 계속 앞쪽의 값들과 비교해 비교 값들을 한 칸씩 오른쪽으로 이동시킨다.

만약 key 값이 더 크거나, 젤 앞의 값까지 비교가 끝나면 그 자리에 현재 값(key)을 넣어준다. 

 

 

삽입 정렬의 시간 복잡도

 

- 두 번째 값으로 시작 시 첫 번째 값과 비교 -- 1번

- 세 번째 값은 첫 번째, 두 번째랑 비교 -- 2번

- n-1 번째 값은 1, 2, 3,... , n-2 번째 비교 -- (n-2)번

- n 번째 값은 -- (n-1)번

 

즉, 1 + 2 + 3 + ... + n-2 + n-1 = n(n-1) /2 가 돼서, 시간 복잡도가 최악의 경우 O(n^2)가 된다. 최선의 경우는 자료가 다 정렬된 경우이고 이때는 시간 복잡도가 O(n)이 된다. 왜냐하면 각 자리의 값마다 왼쪽의 값 하나만 비교하면 되기 때문이다. 따라서 삽입 정렬은 n값이 커질수록 복잡도가 커져 알고리즘 성능이 떨어진다.

 

 

출처:위키피디아