삽입정렬 (Insertion Sort)

삽입 정렬(Insertion Sort)

-이미 정렬 돼있는 배열에 추가 요소를 적절한 위치(?)에 

삽입(Insertion) 하여 정렬하는 방식-

평균 시간복잡도, 최악 시간복잡도 모두 O(n^2)인 느린 알고리즘..

다만 구현이 용이하며 인플레이스(in-place) 알고리즘이라 한다.

여기서 "적절한 위치"라는 말은,

오름차순이냐 내림차순이냐에 따라 비교하는 조건이 달라질 것인데,

그 조건에 맞게 비교하고 교환을 하라는 뜻이다.

또한 "이미 정렬 돼있는 배열"이라는 말은 

첫 Loop때 배열의 첫 번째 요소와 두 번째 요소는 무조건 정렬을 시키고

이후 Loop 부터는 그 정렬된 배열과 비교하며 교환을 하는 방식이라서 그렇다.

-Sample Source-