알고리즘 이론 4강. 삽입 정렬(Insertion Sort)

 

[삽입 정렬]

: 자료 배열의 2~n번째 요소를 해당 요소 앞의 정렬되있는 부분 배열을 보고 자신의 적절한 위치를 찾아 삽입한다.

삽입 정렬 예시 (위키백과)

- Incremental Approach(증가적 도달)

: 삽입정렬과 같이 가장 작은 subarray(요소 1개)를 정렬하는걸로 시작해, 해당 subarray에 요소를 한개씩 더해가는 구조

 

 

[삽입 정렬의 의사코드]

INSERTION-SORT(A)   for j <- 2 to length[A]       key <- A[j]       i <- j-1                          // A[j]를 A[1: j-1] 부분배열의 알맞은 위치 탐색후 삽입       while i>0 and A[i]>key:           do A[i+1] = A[i]           i = i-1       A[i+1] = key

 

[삽입 정렬의 시간 복잡도]

- 최고 시간복잡도 : O(n) 

- 평균 시간복잡도 : O(n^2)

- 최악 시간복잡도 : O(n^2)

: 정렬해야할 데이터가 거의 정렬되어있는 상태이거나 데이터의 양이 적을때 사용하는 알고리즘(입력에 따라 수행시간 결정)

=> 점근적 분석

 

[점근적 분석(Asymptotic Analysis)]

: 알고리즘의 수행시간이 입력의 크기에 따라 증가함을 의미(기계 종속 상수 무시)