삽입 정렬(Insert Sort)

삽입 정렬이란?

전체 리스트를 왼쪽 리스트와 오른쪽 리스트로 구분한 뒤, 오른쪽 리스트에서 임의의 레코드를 꺼내어 왼쪽 리스트의 적합한 위치에 삽입하는 방법.

이때, 왼쪽의 리스트는 정렬된 리스트이고 오른쪽 리스트는 정렬할 리스트로 가정한다.

 

(7, 3, 9, 4, 1, 6)을 삽입 정렬로 정렬한 순서

왼쪽 리스트	오른쪽 리스트	설명
(7)	(3, 9, 4, 1, 6)	초기 상태
(3, 7)	(9, 4, 1, 6)	3 삽입
(3, 7, 9)	(4, 1, 6)	9 삽입
(3, 4, 7, 9)	(1, 6)	4 삽입
(1, 3, 4, 7, 9)	(6)	1 삽입
(1, 3, 4, 6, 7, 9)	()	6 삽입 후, 정렬 완료

삽입 정렬의 단점

삽입 정렬은 배열로 이루어진 리스트들의 중간에 새로운 레코드를 삽입하려면 삽입될 위치의 오른쪽에 있는 레코드들은 한 칸씩 오른쪽으로 밀어야 한다. 그러므로 레코드의 크기가 크다면 얼마나 많은 시간을 레코드의 이동에 소모해야하는지 상상해보자.

따라서 삽입 정렬은 레코드 양이 많고 레코드 크기가 클 경우에 적합하지 않다. 반면에 대부분의 레코드가 이미 정렬되어 있는 경우에 효율적이다.

 

삽입 정렬의 비교횟수

삽입 정렬은 레코드의 수가 n일 경우 (n-1)번의 삽입을 필요로 하며, 매ㅓㄴ 삽입할 때마다 정렬된 리스트의 레코드를 비교해서 삽입될 위치를 찾아야 한다.

이때 필요한 평균 비교횟수는 이미 정렬된 왼쪽 리스트의 크기의 반으로 가정할 수 있으며, 그 크기는 1, 2, 3, ..., (n-2), (n-1)과 같이 증가한다.

 

 

삽입정렬의 이동횟수

레코드의 이동횟수는 비교횟수와 같으므로 삽입정렬은 비교 및 이동 측면에서 번의 연산이 필요하므로이다.

 

시간복잡도

 

삽입정렬 코드 (Java)

public int[] sort() {
	int temp = 0;
		
	for(int i = 1; i < array.length; i++) {
		temp = array[i];
		for(int j = i - 1; j >= 0 && array[j] > temp; j--) {
			array[j + 1] = array[j];
			array[j] = temp;
		}
	}
		
	return array;
}