삽입정렬(Insertion Sort)

각 숫자를 적절한 위치에 삽입하는 방법이다.

다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면(무조건 연산을 수행하는 것.), 삽입 정렬은 필요할 때만 위치를 빠구게 된다.

예시 문제:
1 10 5 4 3 2 9 6 7 8
해당 숫자를 오름차순으로 정렬하시오.

앞에 있는 것들이 모두 정렬이 되어 있다고 가정한다.

1번째 수행:
1 10 5 4 3 2 9 6 7 8
1은 이동할 곳이 없으므로 그대로.

2번째 수행:
1 10 5 4 3 2 9 6 7 8
v 1 v
10은 1의 앞으로 들어가거나, 뒤로 들어가거나 이다. 여기서 10은 1의 뒤로 들어가므로, 변화가 없다.

3번째 수행:
v 1 v 10 v
숫자 5는 다음과 같이 1의 앞, 1 과 10의 사이, 10의 뒤 이렇게 3군데 중에 삽입될 수 있다. 5는 1과 10 사이에 삽입 되므로
1 5 10 4 3 2 9 6 7 8 이 된다.

4번째 수행:
v 1 v 5 v 10 v
숫자 4는 다음과 같이 4군데에 삽입될 수 있다.
1과 5 사이에 삽입되어야 하므로 다음과 같이 된다.
1 4 5 10 3 2 9 6 7 8

5번째 수행:
v 1 v 4 v 5 v 10 v
이렇게 5군데 중에 삽입하면된다.

이런 식으로 하나씩 삽입하는데, 왼쪽보다 크고 오른쪽보다 작은 곳에 삽입하면된다.

삽입 정렬은 오른쪽 부분에서 원소를 하나씩 가져와서, 정렬된 왼쪽 부분의 올바른 위치에 삽입하는 과정을 반복한다.

#include <stdio.h>

int main(){
	int i,j, temp;
    int arr[10]={1,10,5,4,3,2,9,6,7,8}
    for(i=0;i<9;i++){
    	j=i;
        while(arr[j]>arr[j+1]){
        	temp = arr[j];
            arr[j]= arr[j+1];
            arr[j+1]=temp;
            j--;
        }
        
    }
  for(i=0;i<10;i++){printf("%d",arr[i]);}
  return 0;
}

파이썬 코드

def Insertion_sort
	n = len(arr)
    for i in range(1,n):
    	key = arr[i] #삽입되는 인덱스
    	j=i-1 #왼쪽 숫자로 j위치 세팅
        while j>=0 and key<arr[j]: #삽입되는 수가 왼쪽으로 이동하면서 현재 수보다 작은 수를 찾아서 그 오른쪽에 삽입.
        	arr[j+1]=arr[j] 
            j -=1
            
        arr[j+1] = key
            
mylist = {1,10,5,4,3,2,9,6,7,8}
Insertion_sort(mylist)

print(mylist)

삽입 정렬도 시간 복잡도 O(N^2)을 가진다.