[정렬] 삽입정렬 (Insertion Sort)

* 삽입정렬 (Insertion Sort)

- 정렬 대상을 두 부분으로 나누어 정렬되지 않은 부분에 있는 데이터를 정렬된 부분의 

특정 부분에 삽입해 가면서 정렬을 진행(key 값 을 선택하여 이미 정렬된 숫자 사이에 삽입)

[시간복잡도]

- 최선의 경우  O(n)  [1, 2, 3, 4] 5, 6, 7, 8

정렬된 요소들과 정렬되지 않은 요소가 전체적으로 오름차순 정렬을 이루고 있는 경우

- 최악의 경우  O(n^2)   [5, 6, 7, 8] 4, 3, 2, 1     

정렬된 요소의 맨 앞에 있는 값이 정렬되지 않은 요소들의 값보다 항상 크고,

정렬되지 않은 요소들의 값이 내림차순인 경우

※ 오름차순 정렬에 대한 설명.

input = [47, 15, 36, 26, 27, 2]

자~ 이제 정렬을 시작합니다!

전체 요소들 중 제일 첫번째 요소를 선택합니다!

이제 선택된 요소를 기준으로 정렬된 부분과, 정렬되지 않은 부분을 구분합니다.

정렬되지 않은 부분의 제일 첫번째 요소(15)를 선택합니다.

선택된 요소(15)를 정렬된 부분의 숫자들과 비교하면서 알맞은 위치에 삽입합니다.

정렬된 부분의 47 보다 작기 때문에 47의 앞에 15가 삽입되었습니다.

삽입이 완료되면 정렬되지 않은 부분의 첫번째 요소(36)를 선택합니다.

위에서 처럼 36 역시정렬된 부분과 비교하면서 가장 알맞은 위치에 삽입합니다.

15보다 크고 47보다 작기 때문에 그 사이에 삽입되었습니다.

.

.

.

이렇게 반복된 작업이 전체 요소들에게서 반복되고 나면 아래처럼 정렬된 부분만 남게 됩니다.