삽입 정렬(Insertion Sort)

이전 포스팅에서는 선택 정렬에 대해 알아보았다.
https://ayaan-dev.tistory.com/6

선택 정렬(Selection Sort)

 

이번 포스팅에서는 선택 정렬보다 구현하기 좀 더 복잡하지만 시간복잡도가 더 빠른 삽입 정렬에 대해 알아보겠다.

 

마찬가지로 아래 사이트에서 삽입 정렬 알고리즘을 시각화한 영상을 확인할 수 있다.

https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

삽입 정렬(Insertion Sort)

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

for i in range(1,len(array)):
    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

print(array)

 

인덱스 1부터 시작하여 왼쪽 요소들과 비교하면서 본인자리를 찾아가는 알고리즘이다.

 

STEP 0: i=1, j=1

array[1]<array[0] 이므로 SWAP(array[1],array[0])을 수행한다.

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

 

STEP 1: i=2, j=2~1

array[2]>array[1] 이므로 swap을 진행하지 않고 끝낸다.

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

 

STEP 2: i=3, j=3~1

array[3]<array[0] 이므로 0을 맨 앞으로 옮긴다.

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

 

STEP 3: i=4,j=4~1

array[4]>array[0] and array[4]<array[1]이므로 array[4]를 0과 5 사이로 옮긴다.

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

 

이와 같은 방식으로 마지막 인덱스 까지 첫 번째 반복문을 돌면서 숫자가 낑겨 들어갈 자리를 찾아 넣는 정렬방법이다.

 

포스팅과 첨부한 링크를 보고도 이해가 잘 되지 않는다면 아래 유튜브 링크를 참고하길 바란다.

 

시간 복잡도

시간 복잡도의 경우 이중 for문 임으로 O(N2)이다.

다만, 삽입 정렬의 시간복잡도는 큰 특징이 있다. 최선의 경우 O(N)이라는 것이다.

최선의 경우란 배열이 모두 이미 정렬되어 있는 경우다. 

이미 정렬이 되어 있는 경우 이중 for문의 안쪽 for문에서(for j in range(i,0,-1)) if array[j]<array[j-1]이 매번 false가 나오기 때문이다.

따라서 삽입 정렬의 경우에는 주어지는 배열이 거의 정렬이 되어있는 상태로 주어져서 몇가지 인덱스에 대해서만 위치수정이 행해지면 될 경우 매우 효율적인 알고리즘이 될 수 있다.

일반적으로 빠르다고 알려진 퀵 정렬보다도 더 빠를 수 있다.(퀵정렬의 경우 O(NlogN))