[정렬] 삽입정렬

삽입정렬 (Insertion Sort)

• i번째 데이터를 이전의 원소부터 0번째까지의 데이터들과 비교하여 자리를 교환하는 정렬방식.
• 예) [1, 3, 5, 2, 4] 배열에서 원소 "2"는 이전의 원소 "5"보다 작으므로 자리교환 -> [1, 3, 2, 5, 4], 그 이전의 원소 "3" 보다 작으므로 자리교환 -> [1, 2, 3, 5, 4] 

출처: 위키백과

• 구현

public static void main(String[] args) {
		int[] array = {2, 4, 1, 5, 3};
		int length = array.length;
		
		for (int i = 1; i < length; i++) {
			int target = array[i];
			int j = i - 1;
			while (j >= 0 && target < array[j]) {
				array[j + 1] = array[j];
				j--;
			}
			array[j + 1] = target;
		}
	}

• 시간복잡도 O(N^2)