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

public class Insertion_Sort {
 
	public static void insertion_sort(int[] a) {
		insertion_sort(a, a.length);
	}
	
	private static void insertion_sort(int[] a, int size) {
		
		
		for(int i = 1; i < size; i++) {
			
			int target = a[i];
			
			int j = i - 1;
			
			while(j >= 0 && target < a[j]) {
				a[j + 1] = a[j];
				j--;
			}
			
			a[j + 1] = target;	
		}
	}
}

 

삽입정렬은 시간복잡도가 최선일 때 O(n) 최악일 때 O(n^2)을 가지는 알고리즘이다.

 

https://en.wikipedia.org/wiki/Insertion_sort

 

본인 생각을 풀어서 정리한 노트를 첨부하겠으니 참고해도 좋다.