삽입정렬

삽입정렬

한 번에 한 원소씩 이미 정렬된 다른 원소들과 비교하여 새 원소를 제 위치에 삽입하는 식으로 정렬된 배열을 

만든다.

삽입정렬의 효율

삽입 정렬은 최선의 경우, 즉 리스트가 이미 정렬돼 있을 때, O(n)이다.

이미 정렬된 리스트에 새 원소를 추가할 때는 삽입 정렬이 매우 효율적이다. 

그러나 평균 및 최악의 경우에는 O(n^2)이기 때문에 무작위로 정렬된 많은 데이터를 처리하기에는 좋은 알고리즘은 아니다.

    private static int[] insertion_sort(int[] arr){
        for(int i = 1;i<arr.length;i++){
            for(int j = 0;j<i;j++){
                if(arr[i] < arr[j]){
                    arr = swap(arr, i, j);
                }
            }
        }
        return arr;
    }