Insertion Sort(삽입 정렬)

간단하지만 느린 기본 정렬 알고리즘

n-1번의 round가 진행

매 round마다 하나는 sort(비교+교환) 한다. 

---

삽입정렬 코드

insertion sort의 코드

 

---

삽입정렬 구현 방법

i까지 정렬되어 있다. 그리고 그 다음 i+1이 정렬된 부분에서 자신에게 맞는 자리를 찾아 간다.

아래는 insertion sort의 과정을 나타낸다. 

노란 부분은 이미 정렬된 부분으로 핑크 선이 그어진 숫자가 노란 부분에서 자기에게 맞는 자리를 찾는다.

 

초기상태: 정렬이 필요한 상태

1. 8이 정렬되어있는 부분이고, 그 다음 5가 노란 부분 안에서 자신에게 맞는 위치를 찾는다.

• 1-1. 5와 8을 비교해보았을때, 5 <8 이므로 둘의 자리를 바꾼다.
• 1-2. 비교를 멈추고,  잘 정렬되었다

2. 노란 부분은 정렬되어 있고, 그 다음 핑크 선 부분이 자신의 위치를 잧으려 한다.

• 2-1. 6와 8을 비교해보았을때, 6 <8 이므로 둘의 자리를 바꾼다.
• 2-2. 5와 6을 비교해보았을때, 5 <6 이므로 둘의 자리 바꾸지 않는다.
• 2-3. 비교를 멈추고, 잘 정렬되었다.

3. 노란 부분은 정렬되어 있고, 그 다음 핑크 선 부분이 자신의 위치를 잧으려 한다.

• 3-1. 2와 8을 비교해보았을때, 2 <8 이므로 둘의 자리를 바꾼다.
• 3-2. 2와 6을 비교해보았을때, 2 <6 이므로 둘의 자리 바꾼다.
• 3-3. 2와 5을 비교해보았을때, 2 <5 이므로 둘의 자리 바꾼다.
• 3-4. 더이상 비교할 것이 없다.  잘 정렬되었다.

---

시간 복잡도

Best Case

상황: 대부분이 정렬되어 있을 경우
비교 횟수: 1번의 비교

이동 횟수: 없다

비교&이동 세트를 총 (n-1)번 반복

T(n) = O(n)

 

Worst Case

상황:입력 자료가 역순일 경우
비교 횟수: (n-1)+(n-2)+....+2+1 = n(n-1)/2
교환 횟수: (n-1)+(n-2)+....+2+1 = n(n-1)/2
T(n) = O(n^2)

---

특징

장점

• 안정한 정렬 방법
• 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
• 대부분위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

단점

• 비교적 많은 레코드들의 이동을 포함한다.
• 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

---

출처

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

https://www.youtube.com/watch?v=Du-EHAUE0kM&list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl&index=16