3. 삽입 정렬(Insertion Sort) - O(n2)

이번에는 삽입 정렬을 배워보겠다.

간단히 정의하자면 현재 비교하고자 하는 target과 그 이전의 원소들과 비교하며 자리를 교환하는 정렬이다.

삽입정렬 역시 "안정 정렬"이다.

 

 

삽입 정렬의 과정

1. 현재 타깃이 되는 숫자와 이전 위치에 있는 원소들을 비교한다.
   (첫 번째 원소는 두 번째부터 비교한다.)
2. 타깃이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.
3. 그다음 타깃을 찾아 위와 같은 방법으로 반복한다.

짧게 얘기하면 배열을 쭈욱 나열하고 앞뒤로 서로 비교하며 오름차순으로 정렬하는 것이다.

 

이번에도 손글씨 입니다..죄송합니당..

첫번째 원소는 타겟이 되어도 비교할 전 원소가 없어서 2번째 원소부터 타겟으로 잡고 시작한다.

구현은 나의 깃허브에 해놓았다 시간이 된다면 보는것을 적극 추천한다

https://github.com/ProblemSolveStudy/Tae_sik/tree/master/Sorts

GitHub - ProblemSolveStudy/Tae_sik

 

삽입 정렬의 장단점

 

◐ 장점 =

 = 메모리 소비가 작다.

제자리정렬이라고 불릴 정도로 많은 공간이 필요하지 않다.

 

 = 최선의 경우 O(N)의 빠른 시간 복잡도가 나온다.
O(N)이 되는 경우는 모든 타깃이 이전 숫자보다 큰 것이다. = 이미 배열되어 있는 숫자들

 

 = 안정 정렬이다.

 

 

◑ 단점

 = 비효율적이다. 최악의 경우 O(N2)이란 느린 시간복잡도가 걸린다.

O(N2)이 되는 건 모든 수가 다 따로 놀아 일일이 다 찾아다님

 

 = 데이터의 상태에 따라 성능 편차가 매우 크다.

 

정리 

삽입 정렬은 최악(상한선)을 기준으로 하는 우리들에게 O(N2)라는 느린 시간이 걸리지만 이미 정렬이 되어있다면 O(n)의 시간 복잡도를 가지는 정렬이다. 때문에 비슷한 분류의 정렬 알고리즘(버블정렬, 선택정렬)중에서는 빠른 편에 속하는 알고리즘이다.

심지어 성능만 놓고 보자면 굉장히 우수한 편에 속하기 때문에 자주 볼 일이 있을 것이다. 

너무 어렵지 않은 정렬이기 때문에 한번 봐두고 기억해 두는 것이 좋을 것이다.

 

시간 복잡도

	최악	최선	평균
Counting Sort(계수 정렬)			O(n)
Select Sort(선택 정렬)	O(n2)	O(n2)	O(n2)
Insertion Sort(삽입 정렬)	O(n2)	O(n)	O(n2)

 

 

※ 삽입 정렬을 변형하여 만들어진 Shell Sort도 있다