[알고리즘] 정렬 알고리즘 - 삽입 정렬 Insertion Sort

 

삽입 정렬 (Insertion Sort) 알고리즘 :

선택한 요소를 그보다 더 앞쪽의 정렬된 부분의 알맞은 위치에 삽입하여 정렬하는 알고리즘

트럼프 카드를 한 줄로 늘어놓을 때 사용하는 방법과 유사

 

1. 아직 정렬되지 않은 부분의 첫번째 요소 selection[i]를 선택

2. 정렬된 부분에서 selection[i]의 알맞은 위치를 찾아 삽입

   2-1. 정렬된 부분의 요소를 한칸씩 뒤로 밀어낸다

   2-2. 정렬된 부분의 왼쪽 끝에 도달하거나 selection[i]보다 작거나 같은 수를 만날 때 까지

   2-3. 알맞은 자리에 selection[i] 삽입

 

배열 insertion의 삽입 정렬 과정

 

 

메서드 insertionSort() : 길이가 n인 배열 a를 삽입 정렬

매개변수 : int[] a, int n

 

- 삽입 정렬

void insertionSort(int[] a, int n) {
	for(int i = 1; i < n; i++) {
		int j;
		int tmp = a[i];
		for(j = i; j > 0 && a[j-1] > tmp; j--) {
			a[j] = a[j-1];
		}
		a[j] = tmp;
	}
}

 

 

 

 

삽입 정렬 Insertion Sort :

최선 = O(N) , 평균 = 최악 = O(N^2)

안정한 정렬