삽입 정렬

[삽입 정렬에 대한 개요]

삽입 정렬은 0번째 배열부터 마지막 배열까지 이동하면서 작은 값을 앞으로 보낸다.

이때 작은 값의 기준은 사실 '정렬되었는가 정렬되지 않았는가'이며 보내는 방법은 다음과 같다.

자신의 앞 값(My neighbor)과 비교한다. 만약 자신이 더 작다면 다시 비교했던 값의 앞의 값(My neighbor's neighbor)과 비교한다.

위 과정을 반복하다가 만약 자신이 더 크다면, 나보다 더 작았던 값의 오른쪽에 삽입(insert)된다. 내가 삽입되면서 그 옆에 있던 값들은 한 칸씩 오른쪽으로 밀려난다.

삽입 정렬의 시간 복잡도를 계산하려면 최선일 때와 최악일 때의 경우가 어떤 때인지 알아야 한다.

삽입 정렬은 내가 정렬하려는 레코드가 최대한 많이 정렬되어 있을 경우 가장 빠르게 일을 마칠 수 있다.

거의 정렬되어 있다면 앞의 값들을 비교하는 루프가 돌지 않기 때문에 O(n)에 가깝게 일을 처리한다.

하지만 거의 정렬되어 있지 않다면, 모든 반복문이 돌아야 하기 때문에 O(n^2)의 시간 복잡도를 갖게 된다.

버블이나 선택과 달리 시간 복잡도가 조금 달라질 수 있단 점이 특징이다.