정렬 알고리즘 - 삽입 정렬 [Insertion sort]

정렬 알고리즘 삽입 정렬 [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

이런 식으로 계속 정렬하면 됩니다.

추가 코멘트

원래는 다 써보려고 했는데 너무 길어서 여기까지만.. ㅎㅎ

Designed by JB FACTORY