[알고리즘] 03 삽입 정렬(Insertion Sort)

삽입 정렬

• 배열을 정렬된 부분과 정렬이 안된 부분으로 나눈다.
• 정렬이 안 된 부분의 첫 번째 요소를 정렬된 부분의 적절한 위치에 삽입하여 정렬하는 과정을 반복한다.

수행 방법

• 정렬은 배열의 두번째 인덱스부터 시작한다.
• 현재 위치의 요소값을 저장해놓은 뒤 왼쪽의 요소값과 비교하면서 삽입한다.

 

삽입정렬이 진행되는 과정

 

 

수행 시간: O(n^2)

• Best: 1+1+1+…(n-1): θ(n)
• Average: θ(n^2)
• Worst: 1+2+…+(n-1): θ(n^2)

특징

• 값들이 거의 정렬되어 있을때 빠르게 실행
• 추가 공간 불필요
• 입력 크기가 크지 않고 거의 정렬되어 있을 때 적절

코드 구현

public class Sort {
	public void insertionSort(int[] a) {
		int i, j, temp;
		for (i = 1; i < a.length; i++) {
			temp = a[i];
			j = i;
			while ((j > 0) && (a[j - 1] > temp)) {
				a[j] = a[j - 1];
				j--;
			}
			a[j] = temp;
		}
	}