CS공부/알고리즘

[정렬 알고리즘] 삽입 정렬

실실쟌 2022. 10. 11. 16:28

와.. 예전에 정리했던 정렬 알고리즘 테마에 뭔가 하나 빠져 있지 않나 했는데 삽입 정렬을 정리하지 않았네요;;

 

정렬 방법

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칸 떨어진 원소들끼리 정렬

 

아이디어

* 삽입정렬은 이미 정렬된 배열에 대해 효율적이다.

-> 배열 일부를 미리 정렬해서 이 효율성을 활용한다.

사진 출처 : 문병로 교수님의 강의노트