기본 Sort 알고리즘 InsertionSort

출처 : 쉽게 배우는 알고리즘 (문병로 저)

 

1. 기본

  - Select, Bubble Sort 와는 달리, 1개짜리 Array 에서 시작한다.

    또한 iteration 이 수행될 때마다 Array에는 값이 정렬되어 있다.

    그리고 새로운 값을 넣을 때마다 Array에서 크기를 비교하여 적절한 곳에 삽입한다.

   (삽입이 발생하므로 삽입된 위치부터 값이 뒤로 밀리는 작업이 필요하다.)

 

2. 구현

public void InsertionSort(int[] A) {
		
		/*
		 * for i=1 to N-1
		 * 	newItem = A[i];
		 * 	for j=i-1 to 0 
		 * 		if(newItem>=A[j])
		 * 			break;
		 * 		A[j+1] = A[j]
		 * 	A[j+1] = newItem;  
		 * 
		 */
		
		for (int i=1 ; i < A.length  ; i++)		{
			int newItem = A[i];
			int j;
			for (j=i-1 ; j >= 0 ; j--){
				if(newItem >= A[j]) {
					break;
				}
				A[j+1] = A[j];
			}
			
			A[j+1] = newItem;
		}
		
	}
}