삽입 정렬

public class Insert {
	public static void main(String[] args) {
		int[]a=new int[] {5,4,3,2,1};
		System.out.println(Arrays.toString(a));
		System.out.println(Arrays.toString(insertSort(a)));
	}
	public static int[] insertSort(int[]a) {
		int i, j, tmp;
		for(i=1;i<a.length;i++) {
			tmp=a[i];
			for(j=i-1;j>=0&&tmp<a[j];j--) {
				a[j+1]=a[j];
			}
			a[j+1]=tmp;
		}
		return a;
	}
}

삽입 정렬에 포함된 단계는 삭제, 비교, 시프트, 삽입 네 종류

 

삽입 정렬의 효율성을 분석하려면 각 단계별 총합을 계산해야 한다.

 

비교 : 공백 왼쪽에 있는 값과 tmp를 비교할 때마다 일어난다.

 

배열이 역순으로 정렬된 최악의 경우, 각 패스스루마다 tmp 왼쪽에 있는 모든 수를 tmp와 비교해야 한다.

 

따라서 각 패스스루는 공백이 배열의 왼쪽으로 가야만 끝난다.

 

 

첫 번째 패스스루에서는 인덱스 1의 값이 tmp인데 tmp 왼쪽에 값이 하나뿐이므로 최대 1번의 비교가 일어난다.

 

마찬가지로 두 번째 패스스루에서는 tmp를 제외한 배열 내 모든 값을 비교해야 한다. 

 

즉, 배열에 원소가 N개가 있으면 마지막 패스스루에서는 최대 N-1번의 비교가 일어난다.

 

따라서 총 비교 횟수를 다음과 같이 표현할 수 있다.

 

1+2+3+...+N-1번의 비교

 

원소가 열 개의 배열이면 1+2+3+4+5+6+7+8+9=45번의 비교가 있을 것이다

 

이 패턴에 따르면 결국 원소가 N개인 배열일 때 대략 N^2/2번의 비교가 일어나는 것으로 보인다.

 

시프트 : 값을 한 셀 오른쪽으로 옮길 때마다 일어난다.

 

배열이 역순으로 정렬돼 있다면 비교가 일어날 때마다 값을 오른쪽으로 시프트해야 하므로 비교 횟수만큼 시프트가 일어난다.

 

최악의 시나리오일 때 비교와 시프트 횟수를 합쳐보자.

 

N^2/비교 2번

+ N^2/시프트 2번

N^2단계

 

배열로부터 tmp를 꺼내 다시 삽입하는 작업은 패스스루 당 한 번 일어난다. N-1번의 삽입이 이루어 진다.

 

= N^2+N-1

 

빅 오에는 상수를 무시한다는 규칙이 있기 때문에

=N^2+N으로 단순화 시킬 수 있다.

 

빅 오에는 곧 설명할 중요한 규칙이 또 있다.

 

빅 오 표기법은 가장 높은 차수의 N만 고려한다.

 

따라서, O(N^2+N)은 단순히 O(N^2)이다.

 

결론적으로 최악의 시나리오에서 삽입 정렬은 버블 정렬이나 선택 정렬과 시간 복잡도가 같다.

 

셋 모두 O(N^2)이다.

 

버블 정렬과 선택 정렬은 둘 다 O(N^2)이지만 버블 정렬은 N^2단계인데 반해 선택 정렬은 N^2/2단계로 선택정렬이 더 빨랐다. 

 

삽입 정렬 역시 N^2단계가 걸리므로(실제로는 N^2+N-1단계) 언뜻 보기에는 버블 정렬만큼 느리다고 할 수 있다.

 

최악의 시나리오에서는 선택 정렬이 삽입 정렬보다 빠른 게 사실이다. 하지만 평균 시나리오도 중요하게 고려해야 한다.