삽입 정렬(Insertion Sort)

"삽입 정렬"

     : 각 숫자를 적절한 위치에 삽입하는 방법

 

• 시간 복잡도 : O(N^2)
• 앞에 있는 원소들이 이미 정렬이 되어 있다고 가정하고 필요할 때만 위치를 바꾸기 때문에, 효율적
• 데이터가 거의 정렬된 상태에 한해서는 가장 빠름

 

class Sort {
	
	public int[] Insertion_Sort(int[] arr) {
		
		for(int i = 0; i < arr.length; i++) {
			
			int j = i;
			
			while(arr[j] > arr[j+1]) {
				
				int temp = arr[j];
				arr[j]= arr[j+1];
				arr[j+1] = temp;
                
				j--;
			}
		}
	}
}