삽입 정렬(Insertion sort)

▶삽입 정렬 (Insertion sort)

---

앞에서부터 정렬될 하나의 데이터를 왼쪽으로 비교하며 swap해서 제 자리를 찾아가도록 정렬시키는 방법이다.

정렬될 데이터가 처음부터 제 위치에 있다면 바로 다음 데이터를 확인하게 되므로, 배열에 데이터가 대부분 정렬되어 있는 경우라면 삽입 정렬이 유리하다.

하지만 데이터가 정렬되어 있어야 하고 삽입/삭제가 빈번한 경우 처음부터 set/map에 데이터를 저장하여 사용하는 게 더 효율적이다. 

int arr[7] = {5,2,7,4,3,6,1};

이런 배열이 선언되어있고, 이 배열의 원소들을 정렬한다고 해보자.

이해를 돕기 위해 표를 그려보았다.

N개의 원소를 순서대로 확인하면서 바로 앞에 자신보다 큰 원소가 있다면 자리를 바꾸는데,

자신의 앞에 자신과 같거나 작은 원소가 위치해 있게 되면 멈추도록 구현한다. 

주황색으로 색칠된 부분이 정렬이 이러한 방식으로 정렬을 완료한 영역이고,

각 단계에서 swap이 일어난 횟수를 정리한 표이다.

▶시간 복잡도

---

최악의 경우 O(N^2)의 시간이 걸리고 최선의 경우 모두 정렬되어 있어 Ω(N)의 시간이 걸린다.

데이터가 역순으로 정렬되어있는 상태라고 가정해보자. N개의 데이터를 정렬해야 하므로 기본적으로 O(N)이고 각 데이터를 왼쪽으로 비교하면서 제 자리를 찾아가도록 하므로 O(N)이다. 따라서, 전체적으로 시간 복잡도는 O(N^2)이 된다.

▶소스 코드

---

[소스 코드 보기]