장삼의 착한코딩

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

알고리즘

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

wkdgusdn3 2015. 10. 27. 00:27

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







'알고리즘' 카테고리의 다른 글

[알고리즘]MergeSort(병합정렬)  (0) 2015.10.27
[알고리즘]Insertion Sort(삽입정렬)  (0) 2015.10.27
0 Comments
댓글쓰기 폼