삽입 정렬 (Insertion Sort)

삽입 정렬은 이미 정렬된 부분 배열에 현재 정렬하고자 하는 수를 삽입하여 정렬하는 알고리즘 입니다.

---

 

위의 그림과 같이 1~5번째 배열은 이미 배열이 된 상태고 6번째 수 4를 오름차순 정렬하는 경우를 살펴봅시다.

정렬하고자 하는 수 즉, 현재 단계에서 삽입하고자 하는 수는 4이므로 이를 5번째 배열 수부터 비교해갑니다.
5번째 수 7은 4보다 크니까 (7 > 4) 4는 7보다 앞으로 가야 합니다. 따라서 7을 뒤로 한 칸 옮겨줍니다.
4번째 수 6도 4보다 크니까 (6 > 4) 4는 6보다 앞으로 가야 합니다. 따라서 6을 뒤로 한 칸 옮겨줍니다.3번째 수 5도 마찬가지로 4보다 크니까 (5 > 4) 5를 뒤로 한 칸 옮겨줍니다.
2번째 수 3은 4보다 작습니다.(3 < 4) 따라서 4는 3 바로 뒤인 3번째 위치에 삽입시켜줍니다.
수를 뒤로 한 칸씩 옮겨주는 이유는 삽입하여야 하는 수가 들어갈 위치 확보를 위해서입니다.

현재 삽입하고자 하는 수 4를 이미 배열된 배열에서 적절한 위치에 삽입을 하면 위 그림과 같은 상태가 됩니다. 
그러면 6번째 인덱스까지 정렬이 완료가 되고 다음으로 그 다음 수인 7번째 수 1을 정렬하면 됩니다.

---

 

"2 5 3 6 7 4 1"인 배열을 선택 정렬로 오름차순 정렬한 결과는 단계별로 위와 같습니다.
빨간색 부분은 정렬이 완료된 부분 배열입니다.

---

 

최악의 경우 시간복잡도는 O(N^2)이 됩니다.

선택 정렬(참고)의 경우 최소 값이나 최대 값을 구하기 위해서 반드시 정해진 부분 배열을 한 번씩 훑어야 합니다. 그러나 삽입 정렬의 경우 적절한 위치만 찾으면 해당 부분 배열을 모두 훑지 않아도 됩니다.
따라서, 선택 정렬과 삽입 정렬의 시간 복잡도는 O(N^2)으로 같지만 보통 삽입 정렬이 더 빠릅니다.

이처럼 삽입 정렬의 경우 이미 어느정도 정렬이 되어 있는 상태라면 시간 복잡도가 줄어듭니다. (적절한 위치를 찾는데 비교하는 횟수가 줄어들므로)
이를 응용해서 나온 정렬 방법이 바로 셸 정렬입니다. 이는 또 다른 포스팅에서 설명하도록 하겠습니다.

---

 소스코드 : https://gist.github.com/fpdjsns/deaa97a92b2a76cb486f3dfc95350310

삽입 정렬. 입력 : 숫자 개수(n), n개의 숫자. 출력 : 오름차순으로 정렬된 배열