06-4 단순 삽입 정렬

단순 삽입 정렬 알아보기

다음은 단순 삽입 정렬 알고리즘을 적용합니다. 두 번째 요소부터 정렬합니다.

start	6	4	1	7	3	9	8
2차	4	6	1	7	3	9	8
3차	1	4	6	7	3	9	8
4차	1	4	6	7	3	9	8

아직 정렬하지 않은 부분의 첫 번째 요소를 정렬한 부분의 알맞은 위치에 삽입합니다.

알맞은 위치에 삽입

자바에서는 배열의 알맞는 위치에 삽입이라는 명령어가 없으므로, 현재 정렬중인 값을 임시로 저장한 뒤 알맞은 위치가 나타날 때 까지 값을 오른쪽으로 한칸씩 옮기며, 임시저장값(정렬중인 값)이 들어갈 위치가 나타나면 요소값을 수정하는 식으로 접근해야합니다.

다음은 위 내용을 바탕으로 작성한 단순 선택 정렬 프로그램입니다:

//--- 단순 삽입 정렬 ---//
static 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;
	}
}

단순 정렬의 시간 복잡도

버블, 선택, 삽입의 모두 $O(n^2)$ 입니다.