삽입정렬(InsertionSort)

• 자료 배열의 모든 원소들을 앞에서부터 차례대로 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아내서 정렬하는 방식

• 정렬 과정 -정렬할 자료를 두 개의 부분집합 S,U로 가정

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

• 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.

• 삽입정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. 부분집합 U가 공집합이 되면 삽입정렬이 완성된다.

• 시간복잡도 O(n²)

구현코드

package array2;

import java.util.Arrays;

public class InsertionSort {

	public static void main(String[] args) {
		int[] a = {69,10,30,2,16,8,31,22};
		
		System.out.println(Arrays.toString(a));
		for (int i = 1; i < a.length; i++) {
			int k = i;
			for (int j = 1-1; j >= 0; j--) {
				if(a[j] > a[k]) {
					int T = a[j]; a[j] = a[k]; a[k] = T;
					k=j;
				}
				
			}
			System.out.println(Arrays.toString(a));
		}
	}
}