[정렬 알고리즘] 삽입 정렬
와.. 예전에 정리했던 정렬 알고리즘 테마에 뭔가 하나 빠져 있지 않나 했는데 삽입 정렬을 정리하지 않았네요;;
정렬 방법
1. 모든 i번째 원소에 대해, 0...i-1 번 원소들과 크기를 비교하여 알맞은 자리에 원소를 삽입한다.
수도코드
for i<- 1 to n
//A[0...i-1] 중 적절한 자리에 A[i]를 삽입
j<- i-1
item <- A[i]
while j >= 0 and item >= A[j]
A[j+1] <- A[j]
j--
A[j+1] <- item
복잡도
1. 공간복잡도 O(n) : 제자리 정렬
2. 시간복잡도 O(n^2)
- 선택, 버블정렬과는 반대로 정렬된 배열의 크기가 1 증가하는 방식으로 구현된다.
- 따라서 i가 증가할수록 삽입 부담이 증가 -> max(비교횟수, shift 횟수)에 의해 결정
- 삽입 위치를 결정하는 것을 i-1 부터 한다고 하면,
- 최악의 경우에는 역순 정렬되어 있는 경우로, 항상 i만큼의 비교와 shift.
: (1+2+...+n-1) = theata(n^2)
- 평균적인 경우에는 중간쯤에 삽입하는 경우로, 항상 i/2만큼의 비교와 shift.
: (1/2+2/2+...+(n-1)/2) = theta(n^2)
- 최선의 경우에는 이미 정렬되어 있는 경우로, 1번의 비교와 shift 없음.
: (1+1+...+1) = theta(n)
장단점
1) 장점
- 이미 정렬된 경우에 효율적이다.
- 구현이 쉽고 간단하다.
2) 단점
- 역순으로 정렬된 경우에는 비효율적이다.
- 시간복잡도가 O(n^2)으로 비효율적이다.
수정된 삽입정렬 - Shell sort
구현
1. 7칸 떨어진 원소들끼리 정렬
2. 3칸 떨어진 원소들끼리 정렬
3. 1칸 떨어진 원소들끼리 정렬
아이디어
* 삽입정렬은 이미 정렬된 배열에 대해 효율적이다.
-> 배열 일부를 미리 정렬해서 이 효율성을 활용한다.
