정렬 알고리즘 - 삽입 정렬 [Insertion sort]
- 프로그래밍/알고리즘
- 2019. 4. 13.
정렬 알고리즘 삽입 정렬 [Insertion sort]
오늘은 정렬 알고리즘 중 하나인 삽입 정렬에 관한 내용입니다.
삽입 정렬이란?
기초 정렬 알고리즘.
이미 정리된 데이터들 사이에 새로운 데이터를 적절한 자리에 삽입해주는 알고리즘
성능=O(n^2)
알고리즘 코드
- main함수와 insert_sort함수로 이루어져 있는 코드입니다.
- insert_sort를 확인하기 위한 불필요한 코드가 있습니다.
- 코드의 파일은 제 깃허브에서 보실 수 있습니다.
https://github.com/ykarr/C/blob/master/algorithm/insertion_sort.c
main함수
insert_sort함수
Insertion sort(삽입 정렬) 실행 결과
실행 결과에서 0-{}부분은 실행 전 배열의 상태입니다.
그 후 1,2,3,4는 for문을 몇 번 돌았는지 확인하는 것이라고 생각하면 되겠습니다.
코드 분석
- for문과 while문으로 이루어짐.
- 코드 분석에 원활한 동작을 확인하기 위해 첨가한 printf문은 고려하지 않음.
- while문 내용은 빨간색 while문 바깥의 for문은 파란색으로 표시
보시면 알겠지만 삽입 정렬을 하기 위한 코드는 for문과 while문 하나가 끝입니다.
코드가 작동하는 내용을 전부 작성하면 너무 글이 길어집니다.
그러니몇 개만 정렬해보겠습니다.
*코드 설명에는 printf문은 들어가지 않습니다.
| 987[loc] | 546[newitem] | 24 | 56 | 87 | 98 |
1. 코드가 잘 동작하는지 확인하기 위해서 a[]라는 배열을 main 함수에 정의하고 insert_sort함수에 넘겨줍니다.
2. for(i=1;i<n;i++)문으로 들어갑니다.
3. loc에 i-1을 넣어줍니다.(즉 배열의 처음을 가르켜줍니다.)
4. newitem에 처음 배열의 다음 값 즉 i를 넣어줍니다.(아직 처음이니까 a[1]이 됩니다.)
5. while(loc>=0&&newitem<a[loc])를 비교합니다.(현재newitem=546, a[loc]=987)
6. 참이므로 while문을 실행하고 a[loc+1]에 a[loc]의 값, 즉 987을 저장합니다. 그 후 loc--;를 해줍니다.
| 987 | 987 | 24 | 56 | 87 | 98 |
7. 현재 loc이 0이었고 loc--는 -1이므로 while을 벗어납니다.
8. a[loc+1]에 newitem을 넣습니다. (즉 a[0]에 546의 값을 넣습니다.) //이렇게 for문 한번 끝
| 546 | 987 | 24 | 56 | 87 | 98 |
9. 이제 i를 2로 바꿔주고 loc의 값은 [i-1]즉 1이 됩니다.
| 546 | 987[loc] | 24[newitem] | 56 | 87 | 98 |
10. newitem은 a[2]가 됩니다. newitem=24
11. while--> newitem과 a[loc] 즉 24<987을 비교하고 참이기 때문에 while문에 들어갑니다.
12. a[loc+1]에 a[loc]를 넣어줍니다. 즉 a[2]=a[1] 그 후 loc--;
| 546[loc] | 987 | 987 | 56 | 87 |
13. 아직 while문의 조건을 만족하므로 다시 while문을 실행합니다.
14. 현재 a[loc]을 a[loc+1]에 넣어줍니다. (현재 배열의 상태가 546 987 987인데 546 546 987이 됩니다.)
| 546[loc] | 546 | 987 | 56 | 87 |
15. loc이 -1이되어 while문을 벗어나고 newitem을 a[0]에 넣어줍니다.(24 546 987이 됩니다.)
| 24 | 546 | 987 | 56 | 87 | 98 |
16. 이제 i를 3으로 바꿔주고 loc의 값은 2가 됩니다.
| 24 | 546 | 987[loc] | 56[newitem] | 87 | 98 |
17. newitem은 a[3]이 됩니다. newitem=56
18. 또 while문 비교를 합니다. (56<987이므로 참) 참이므로 while문을 들어갑니다.
19. a[loc+1]=a[loc] -->즉 56이 있던 자리에 987을 넣고 loc--; (loc은 1이 됩니다.)
| 24 | 546[loc] | 987 | 987 | 87 | 98 |
20. 아직 while문을 만족하므로 a[loc+1]에 a[loc]을 넣어줍니다. loc--;
| 24 | 546[loc] | 546 | 987 | 87 | 98 |
21. newitem<a[loc]이 만족하지 않으므로 while문을 빠져나옵니다.
22. a[loc+1]=newitem을 해줍니다.
| 24 | 56 | 546 | 987 | 87 | 98 |
이런 식으로 계속 정렬하면 됩니다.
추가 코멘트
원래는 다 써보려고 했는데 너무 길어서 여기까지만.. ㅎㅎ