17. 삽입(Insertion) 정렬 알고리즘

1. 개요

 앞 선 버블 정렬과 선택 정렬과 똑같이 O(n^2) 수행 속도를 가지지만 특정 경우에서 효과적인 정렬이 있다. 바로 삽입 정렬

이다. 삽입 정렬의 기본 아이디어는 최소 최대를 찾아 양 끝으로 보내는게 아니라 루프를 돌며 자기 자신의 자리를 찾아가자

이다. 장점은 이렇다. 코드가 간단하다. 안정성이 좋다.(루프 중간에 멈춰도 아직 검사안한 기존 데이터 순서가 보장) 그리고

데이터가 이미 어느 정도 정렬이 되어있을 경우 효과적이다. 위의 장점들로 인해 삽입 정렬은 분할 정복 기법으로 재귀적인

방법을 사용하는 퀵(Quick) 정렬이나 병합(Merge) 정렬의 높은 재귀적 오버헤드에 대한 base case로 사용된다.

2. 코드

2-1) 메인

2-2) 삽입 정렬 알고리즘

2-3) 출력

3. 해설

 드디어 정렬에서 O(n^2)을 가지는 기초 정렬 알고리즘 대표적인 3개를 정리했다. 먼저 위의 출력을 정리하면 이렇다.

미리 정렬된 데이터일 경우 삽입 정렬의 속도는 무척 빠르다. 하지만 미리 정렬되지 않은 데이터라면 삽입 정렬의 속도

가 다른 정렬보다 빠르다고 말하기 어렵다.

이것을 정리하면 이렇다.

 

 1) 버블 정렬은 최악의 경우와 평균적 경우 모두 O(n^2/2)의 반복과 O(n^2/2)의 치환을 수행한다.

 2) 선택 정렬은 O(n^2/2)의 비교와 O(n)의 치환이 일어난다.

 3) 삽입 정렬은 평균적인 경우 O(n^2/4)의 비교와 O(n^2/8)의 치환이 일어나며 최악의 경우 이 2배가 된다.

 *선택 정렬이 제일 좋은 상황은 키는 작고(데이터가 작고) 값들이 큰 요소를 가진 목록을 정리할 때이다.