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

Insertion sort는 앞부분에 이미 정렬된 배열과 비교를 하여 자신의 위치를 찾아 삽입 함으로서 앞부분부터 정렬을 하는 알고리즘이다. Key 값을 기준으로 key의 앞부분은 항상 정렬이 되어있다는 특징이 있다. 

- Insertion Sort의 원리

1.      key 값을 기준으로 key의 앞은 정렬이 된 상태이다. i번째 요소를 정렬을 하기 위해서 i번째 배열의 값을 key로 저장을 한다.

2.     key값을 기준으로 i-1부터 검사를 하며 key 값보다 값이 클 경우 값을 한 칸씩 오른쪽으로 이동 시킨다.

3.      그림과 같이 key 값보다 작거나 같은 값이 나올 때까지 2번 과정을 반복한다.

4.      3번 과정에서 key값이 들어갈 위치를 찾으면 key값을 위치에 삽입한다.

- Insertion Sort의 동작 방식

Insertion Sort의 동작을 좀 더 자세히 보면 아래와 같다.

8, 2, 5, 9, 1, 7의 input이 들어왔을 때 insertion sort의 동작 순서이다.

1. 2번째 숫자인 2를 key 값으로 설정한다.

2. 8과 2를 비교하여 8이 더 크기 때문에 8을 2번째 배열위치로 자리를 옮긴다.

3. 2를 1번째 배열 위치로 삽입한다.

4. 3번째 배열인 5의 값을 key로 설정한다.

5. 5와 8을 비교하여 8이 더 크므로 8을 3번째 배열로 이동시킨다.

6. 5를 2번째 배열 위치로 삽입한다.

7. 4번째 배열인 9를 key 값으로 설정한다.

8. 3번째 배열인 8과 비교하여 key 값이 더 크므로, 9는 자리를 유지한다.

9. 5번째 배열인 1을 key 값으로 설정한다.

10. 배교를 한 결과 제일 작은 숫자이기 때문에  1번째 배열까지 오른쪽으로 한 칸씩 이동시킨다.

11. 1을 1번째 배열에 삽입한다.

12. 마지막 숫자 7을 key로 설정한다.

13. 8과 9를 비교하여 key값이 더 작기 때문에 8과 9를 오른쪽으로 한 칸씩 이동시킨다.

14. 7을 삽입한 후 정렬이 완료된 것을 확인할 수 있다.

- Insertion Sort의 시간 복잡도

Insertion Sort의 시간 복잡도를 계산해보자. 시간 복잡도는 보통 worst-cast를 생각하기 때문에 빅o를 계산해 보도록 한다. n개의 데이터가 있을 때, 최악의 경우는 

0 + 1 + 2 + 3 + ... + (n-1) = 이 된다. 결국 시간복잡도는 O(n^2)가 된다. 모든 sort와 마찬가지로 input이 많을 수록 시간이 오래 걸리게 된다. 또한 input이 이미 어느 정도 정렬되어 있으면 시간이 적게 걸린다.

- Input size에 따른 running time

Input size에 따른 running time을 측정하기 위해 항상 같은 조건을 유지해주기 위해 worst-case로 측정을 하였다. 대문에 input number를 내림차순으로 넣어주었다.

worst-case최대 연산 횟수는 이므로

Input size = 1 일 경우는 1

Input size = 20000 일 경우는 199,990,000

Input size = 40000 일 경우는 799,980,000

Input size = 60000일 경우는 1,799,970,000

Input size = 80000일 경우는 9,199,960,000

Input size = 100000 일 경우는 4,999,950,000이다.

Running time을 예측해 보면 y=x^2 그래프와 같이 늘어날 것을 예측할 수 있었다.

아래의 표는 input size를 바꿔가면서 running time을 측정한 결과 표이다.

Input size	Input number	Running time (milli seconds)
1	1	1
20000	20000 19999 … 2 1	743
40000	40000 39999 … 2 1	2952
60000	60000 59999 … 2 1	6493
80000	80000 60000 …  2 1	11441
100000	100000 99999 …  2 1	17508

Worst-case를 확인하기 위해 수열을 내림차순으로 값을 넣어주었다.

Input size를 20000부터 확인을 하였는데, 20000보다 낮은 값에서는 running time이 너무 낮은 값이 나와 비교를 하기 힘들었기 때문에 20000부터 측정을 하였다.

Input size가 늘어날수록 running time이 비례해서 늘어나는 것을 확인 할 수 있다.

input size가 늘어날수록 y = x^2 함수 그래프와 유사하게 증가하는 것을 볼 수 있다. 이를 그래프로 표현하면 아래와 같다. 

- 정렬 정도에 따른 running time 결과

정렬 단계를 1단계(내림차순) 부터3단계(오름차순)까지 실험을 하였다.

아래의 표에서 볼 수 있듯이 내림차순의 숫자를 넣었을 경우에는 17627 milli seconds가 걸렸다. 오름차순으로 숫자를 넣었을 경우에는 419 milli seconds가 걸렸음을 볼 수 있다. 이와 같이 insertion sort는 정렬 정도에 따라 running time이 확연히 차이가 나는 것을 확인 할 수 있었다.

 또한 input number가 내림차순으로 입력 됬을 경우는 worst-case이고, input number가 오름차순으로 입력 됬을 경우는 best-case이므로, input number를 random으로 넣었을 경우는 worst-case와 best-case의 사이의 시간이 걸리는 것을 확인 할 수 있다.

정렬 단계	Input number	Running time (milli seconds)
내림차순	100000 99999 … 2 1	17627
Random	Random	13076
Random	Random	12895
Random	Random	12898
오름차순	1 2 … 99999 100000	419

 

- 소스코드

https://github.com/wkdgusdn3/InsertionSort