삽입정렬 Insert Sort

삽입정렬 역시 기본이 되는 알고리즘 중 하나이다.

* 삽입정렬 알고리즘이란? *

1회전

2회전

보통의 예시로는 숫자 카드게임할 때 카드를 순서대로 옮기는 경우를 생각하면 좋다.

자신이 옮길 카드와 앞 쪽에 있는 카드들과 크기를 비교해서 사이에 쏘옥! 넣으면 되는 것과 같은 원리다.

1회전을 보면 5가 좌측의 7과 비교를 한다. 5가 더 작음으로 7과 옆에는 아무것도 없는 벽 사이에 쏘옥 들어간다.

다음 2회전을 살펴보면 1이 7보다 작기 때문에 비교가 진행되고 1과 5를 비교했을 때

 1이 5보다 작기 때문에 벽과 5사이로 쏘옥 들어가게 된다. 

이런식으로 쭈욱~ 비교하면 정렬이 완료된다.

이렇듯 삽입정렬은 필요할 때만 삽입을 진행한다.

삽입정렬의 경우 좌측에 있는 정렬은 미리 정렬된 상태를 가정하기 때문에

좌측의 숫자와 비교하여 크기가 크거나 같은 경우 정렬을 시행하지 않는다.

이는 삽입될 때 내부에 있는 숫자들과 비교 시에도 적용된다.

만약 작은 경우 자신이 들어갈 위치만 찾으면 되기 때문에

정렬된 숫자들과 비교하여 자신의 위치를 찾아들어가면 되므로 나름 효율적이라고 할 수 있다.

만약 거의 다 정렬된 상태의 숫자들을 정렬한다면 버블이나 선택보다 훨씬 효율적이라고 할 수 있다.

-> 이미 정렬이 거의 완료된 상태에서의 삽입정렬은 어떠한 알고리즘보다도 빠르다고 한다.

역시나 시간 복잡도는 O ( N^2)이지만 최적의 경우 O ( N )까지 갈 수도 있다!!