삽입 정렬(insertion sort)

개념

- 적절한 위치에 삽입하는 알고리즘.

  (선택한 인덱스를 기준으로하여 이전에 존재하는 원소를 보고 적절한 위치에 삽입)

- 기본적으로 선택된 위치를 기준으로 앞에 있는 원소들은 이미 정렬되어있다고 가정한다. 

- 데이터가 거의 정렬되어있다면 빠르다.

- 필요할 때만 위치를 변경한다. (시간복잡도가 선택, 버블 정렬과 같지만 더 빠른 이유)

private void insertionSort(int[] list, ParamMap paramMap) {
	int i, j, temp;
	for(i=0; i<list.length; i++ ){
		j = i;
		// 이전 값이 현재 값보다 큰 경우, 위치 변경 발생
		// 현재 값보다 값이 큰 이전 요소가 없을때까지 탐색
		while(j>0 && list[j-1] > list[j]) {				
			temp = list[j-1];
			list[j-1] = list[j];
			list[j] = temp;
			j--;
		}
	}
}

// j >=0 이면 j--에서 에러
// j > 0 && list[j] > list[j+1]은 list[0]이 삽입정렬에서 제외되서 사용못함
// j > 0 && list[j-1] > list[j]는 list[0]도 비교가능

 

※ 시간복잡도는 O(n^2)