알고리즘 3 [삽입정렬, insertion sort]

3. 삽입 정렬(insertion sort)

 

이미지 출처 :
By Nuno Nogueira (Nmnogueira) - Self-made using Matlab (Originally from English Wikipedia; description page is/was here.), CC BY-SA 2.5, https://commons.wikimedia.org/w/index.php?curid=1780641

삽입 정렬이란?
 배열의 모든 요소를 앞에서부터 정렬된 배열 부분과 비교하며, 자신의 위치를 찾아 삽입하는 정렬방법

 

 

e.g.) 손안에 들고 있는 카드 정렬

---

e.g.) 오름차순 삽입정렬

[8, 5, 6, 2, 4]의 배열이 있을때

1. 두번째 값(5)와 첫번째 값(8) 비교 -> 값이 더 큰 8을 뒤로 보냄. [5, 8, 6, 2, 4]
2. 세번째 값(6)과 두번째 값(8) 비교 -> 값이 더 큰 8을 뒤로 보냄 [5, 6, 8, 2, 4]
   -> 첫번째 값(5)과 비교 -> 5가 더 작으니 변화없음 [5, 6, 8, 2, 4]

... 반복

---

[ 장점 ]

• 안정적인 정렬 형태
• 이미 정렬되어 있거나 자료의 수가 적을 때 유리함

[ 단점 ]

• 비교적 자료의 이동이 많음 -> 수행시간이 길어짐
• 자료의 수가 많을수록 불리함

시간 복잡도 : O(n^2)
공간 복잡도 : O(n)