4강. 삽입정렬

[ 목차 ]

1. 삽입정렬 알고리즘

2. 삽입정렬 방법

3. 삽입정렬 수행시간 분석

4. 삽입정렬의의 공간복잡도

5. 삽입정렬의 시간복잡도

 

1. 삽입정렬 알고리즘

1) 3강의 정렬 문제 중 하나

2) key값을 정렬된 배열에 알맞은 위치에 삽입하여 정렬문제를 푸는 알고리즘

  ex, <1, 2, 4, 5, 6>  배열에  key값 3을 오름차순에 맞게 알맞게 삽입

 

2. 삽입정렬 방법

1) 주어진 배열  A[1...n]에 원소를 하나씩 추가하면서 배열 속 값과 비교하여 정렬

2) 첫 번째는 A[2]를 정렬된 배열 A[1]에 삽입

3) 두 번째는 A[3]를 정렬된 배열 A[1...2]에 삽입

4) N-1 번째는 A[n]를 정렬된 배열 A[1...n-1]에 삽입

 

3. 삽입정렬 수행시간 분석

1) 최선의 경우

  1] 배열  A[1...n]가 이미 정렬이 제대로 되어있는 경우

  2] N에 대한 선형함수로, an + b로 표현 가능

2) 최악의 경우

  1] 배열  A[1...n]가 이미 반대로 정렬되어 있는 경우

  2] N에 대한 2차 함수로, an제곱 + bn + c로 표현 가능

3) 평균의 경우

  1] n제곱

 

4. 삽입정렬의 공간복잡도

1) 제자리 정렬로 추가 공간을 사용하지 않음

2) 별도의 공간 없이 자기 자리에서 앞뒤로 움직이며 복사

 

5. 삽입정렬의 시간복잡도