삽입정렬

삽입 정렬

각 숫자를 적절한 위치에 삽입하는 방법을 사용한다. 왼쪽으로 하나씩 정렬을 시키며 아래와 같은 방법을 오른쪽 끝가지 반복한다.

public static void main(String[] args) {
        int[] arr = {10, 2, 5, 4, 3, 8};
        insertion(arr);
    }

    public static void printArr(int[] arr){
        for (int i=0; i<arr.length; i++){
            System.out.println(arr[i]+ " ");
        }
    }
    public static void insertion(int[] array){
        for(int i =0; i< array.length-1; i++){
            int j = i;
            int temp;
            while( j>= 0 && array[j]> array[j+1]){
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                j--;
            }
        }
        printArr(array);
    }

최선의 상황

이미 정렬이 되어있는 상태에서는 굉장히 빠르다. 반복문을 하나만 사용하게 되므로 최대 O(N) 까지 가능할 것 같다.

시간복잡도

반복문 두개를 동시에 돌리므로 O(N^2) 의 복잡도를 가진다.