삽입정렬

정렬의 종류

버블 정렬(Bubble Sort)
선택 정렬(Selection Sort)
카운팅 정렬(Counting Sort)
삽입 정렬(Insertion Sort)
힙정렬
병합 정렬
퀵정렬

삽입 정렬이란

자료 배열의 모든 원소들을 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아냄으로써 정렬을 완성한다.

정렬 과정

1. 정렬할 자료를 두 개의 부분집합 S와 U로 가정

• 부분집합 S: 정렬된 앞부분의 원소들
• 부분집합 U: 아직 정렬되지 않은 나머지 원소들

2. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.
3. 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 부분집합 U가 공집합이 되면 삽입정렬이 완성된다.
4. 실제론 S와 U에 대한 처리는 없지만 이러한 개념을 염두해두고 삽입 정렬을 생각해야 한다.
   
   

구현

public class 삽입정렬 {

	public static void main(String[] args) {

		int[] arr = {69, 10, 30, 2, 16, 8, 31, 22};
		
		for(int i=1; i<arr.length; i++) {
			int key = arr[i];  	//이번에 정렬할 값
			int j; 				//정렬할 위치
			
			for(j=i-1; j>=0; j--) {
				if(arr[j] < key) {
					break;
				} else {
					arr[j+1] = arr[j];
				}
			}
			arr[j+1] = key;
		}

	} //main

}