삽입정렬 Insertion Sort JAVA

---

Insertion Sort

- 정렬되어야 하는 원소의 인덱스가 K라 하면, K-1번째까지의 정렬된 배열에 K번째 인덱스가 있어야 할 위치에 적절히 삽입하여 정렬하는 방법.

- 시간복잡도 최선(이미 정렬되어 있을 경우)은 O(N) , 최악은 O(N^2)

public class InsertionSort implements Sort {
 
    @Override
    public void sort(int[] arr) {
 
        int temp;
        
        for(int i = 1; i < arr.length;  i++) {
            
            for(int j = i;  j > 0;  j--) {
                if(arr[j-1] > arr[j]) {
                    temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                } else 
                    break;
            }
            
        }
 
    }
}
 

* i번째 인덱스부터 반대로 버블정렬 한다는 느낌

* i번째까지는 정렬되어 있으므로 스왑하지 않아도 된다면 바로 break로 나가버리기.