삽입정렬 알고리즘 (Insertion Sort)

• 배열의 앞 요소 부터 차례대로 이미 정렬된 배열 부분과 비교하여, 맞는 위치를 찾아 삽입
• 맞는 위치에 삽입된 요소는 정렬 되어있다.

[ 5 , 1 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

위와 같은 배열이 존재할때,

1. 요소 1(index 1)을 index 0과 비교하여 작으면, swap 한다.
2. 요소 2(index 2)를 index 1과 비교하여 작으면,swap하고 index 0과 비교하여 작으면 또 swap한다.
3. 매 순서 마다 해당 원소를 삽입할 수 있는 위치를 찾아 삽입한다.

[ 5 , 1 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 5 , 1 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 5 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 5 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 2 , 5 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 2 , 5 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 2 , 5 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 2 , 5 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

...

[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ]

알고리즘 구현

def solution(array):
   answer = []
   
   for index in range(len(array) - 1):
       key = index
       while key >= 0 and array[key] > array[key + 1]:
           array[key], array[key + 1] = array[key + 1], array[key]
           key-=1   

   answer = array  
   return answer

시간 복잡도 O(N^2)

배열의 크기가 10일 경우, 선택정렬도 마찬가지로 최악의 경우 10+9+8+...+1

N일경우 N(N+1)/2 의경우가 되므로 N이 무수히 큰수가 대입되면, 상수는 무시되므로
O(N^2) 의 시간복잡도를 갖는다.

O(N^2)을 갖는 정렬

삽입정렬(Insertion Sort), 선택정렬(Selection Sort), 버블정렬(Buble Sort)가 존재한다.