[알고리즘] Insert Sort

Insert Sort

개념

• 이미 순서화된 데이터에 새로운 하나의 데이터를 순서에 맞게 삽입시켜 정렬하는 방식이다.
• 가장 간단한 정렬방식이다.
• 평균과 최악의 시간복잡도는 O($n^2$)이다.

예시

Java 구현 코드

public class InsertSort {
	public static void main(String[] args) {
		int[] arr = {3,8,43,20,9,15,61,54,13,94,2,10};
		
		int temp = 0;
		for (int i = 1; i<arr.length ; i++) {
			for (int j = i; j > 0; j--) {
				if (arr[j] < arr[j-1]) {
					temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
				}
				else break; 
	// j이전에는 모두 정렬된 상태라 arr[j]가 arr[j+1]보다 작지 않다면 앞쪽의 수는 비교할 필요가 없다.
			}
		}
		
		for (int i = 0; i<arr.length ; i++) {
			System.out.println(arr[i]);
		}	
	}
}