단순 삽입 정렬

단순 삽입 정렬

배열의 요소를 알맞은 위치에 필요할 때만 삽입

static int[] numbers = {3,4,2,0,1};
	
    static void swap(int a, int b){
        int temp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = temp;
    }
    
    static void insertionSort(){
        
        for(int i = 0; i < numbers.length - 1; i++){
           int j = i;
           while(numbers[j] > numbers[j+1]){
               swap(j, j+1);
               j--;
               if(j < 0)
                    break;
           }
        }
        
        for(int i = 0; i <numbers.length; i++)
            System.out.println(numbers[i]);
    }
    
    public static void main(String args[]) {
        insertionSort();
    }

시간 복잡도 : O(n^2)

거의 정렬이 된 배열(2,3,4,5,1)일 때 정말 효과적이고, 일반적으로도 단순 선택 정렬과 버블 정렬보다 빠르다.

장점

정렬을 마쳤거나 정렬을 거의 마친 상태면 정렬 속도가 매우 빠르다.

단점

삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다.