[Algorithm] 정렬 - Insertion Sort (삽입 정렬)

Insertion Sort

• k번째 원소를 k-1번째 원소부터 첫번째 원소까지 비교하며 위치를 찾아 끼워넣는 방식
• O(n^2)인 정렬중에 빠른편에 속한다.

동작

Step1

 

Step2

 

Step3

 

Step4

 

Step5

 

Step6

 

코드 (Java)

public class Sort {

	public void insertionSort(int[] arr) {
    	for(int i = 1; i < arr.length; i++) {
            int target = arr[i];
            for(int j = i - 1; j >= 0 && arr[j] > target; j--) {
            	arr[j+1] = arr[j];
            }
            arr[j+1] = target;
        }
    }
}