삽입정렬

간단하면서도 효과적인 비교 정렬이다. 이 알고리즘은 매 반복마다 뒤쪽의 정렬되지 않은 요소들의 목록에서 요소를 삭제하고 삭제한 요소를 앞쪽의 이미 정렬된 목록 내 알맞은 자리에 삽입한다. 입력 데이터에서 삭제될 요소는 정렬되지 않은 목록에서 무작위로 선택하고(일반적으로 앞에서 차례로 선택) 입력 데이터 내 모든 요소를 처리할 때까지 반복

장점
간단하다
적은 데이터 양에 효과적이다.
적용성: 입력 목록이 완전하지는 않더라도 사전 정렬이 되어있다면 삽입 정렬은 d가 swap 횟수 일떄 O(n+d)의 복잡도를 가진다.
실제로 선택 정렬과 삽입 정렬은 최악의 경우 복잡도가 O(n2)인 다른 모든 알고리즘보다 효과적이지는 않다.
안정성 : 키가 동일할 경우 입력 데이터의 순서가 보존된다.
제자리 정렬: 추가적인 고정적인 메모리 공간으로 O(1)만을 소요한다.
온라인: 입력 인자로 받은 목록을 정렬한다.

알고리즘

삽입 정렬은 매 반복마다 정렬되지 않은 목록에서 하나의 요소를 선택(일반적으로 배열의 앞부터 차례대로 선택)하여 선택한 요소를 삭제하고 삭제한 요소를 앞 쪽의 정렬된 목록과 비교하여 정렬된 목록 내 알맞은 자리에 삽입하는 절차를 배열의 모든 요소에 대해 수행한다. 일반적으로 제자리 정렬을 수행한다. K번 반복 후 배열은 첫 번째 요소에서 k+1번째 요소까지는 정렬된 상태를 가지게 되는 특성이 있다.

import java.util.Arrays;

public class InsertionSort {
    public static void insertionSort(int[] arr){

        int count = 0;

        System.out.println("Before insertionSort");
        Arrays.stream(arr).forEach(value -> System.out.print(value + " "));
        System.out.println();

        for(int i=1; i<arr.length; i++){
            int temp = arr[i];
            int prevIndex = i-1;

            while( (prevIndex>=0) && (arr[prevIndex] > temp)){
                count++;
                arr[prevIndex+1] = arr[prevIndex];
                prevIndex--;
            }
            arr[prevIndex+1] = temp;
        }


        System.out.println("After insertionSort");
        System.out.println("The number of count : " + count);
        Arrays.stream(arr).forEach(value -> System.out.print(value + " "));
        System.out.println();

    }
}

Before insertionSort
5 3 67 58 69 69 34 52 69 17 
After insertionSort
The number of count : 17
3 5 17 34 52 58 67 69 69 69 

최악의 경우는 매 반복(i번째)에서 이미 정렬된 모든 요소들을 모두 이동시켜야할 경우에 발생한다. (이 경우는 A[i]의 키가 앞의 다른 모든 요소보다 작을 떄 발생한다.

성능

최악의 경우 복잡도: O(n2)
최선의 경우 복잡도: O(n2)
평균 복잡도: O(n2)
최악의 경우 공간 복잡도: 보조 공간: O(1), 전체 O(n2)

다른 정렬 알고리즘 과의 비교
삽입 정렬은 최악의 경우 O(n2)의 복잡도를 가지는 기본적인 정렬 알고리즘이다. 삽입 정렬은 (삽입 정렬이 가진 적용성 때문에) 미리 데이터가 어느 정도 정렬이 되어있는 상태거나 입력 데이터의 양이 적을 때 사용된다. 이러한 이유와 안정성 때문에 삽입 정렬은 병합 정렬 또는 퀵 정렬 같은 분할 정복 알고리즘의 높은 오버헤드에 대한 재귀적 base case(문제의 크기가 작은 경우)로 사용된다.

이러한 삽입 정렬의 안정성 떄문에 병합 정렬 또는 퀵 정렬 같이 높은 오버헤드를 분할 정복하는 정렬 알고리즘에서 반복 기반으로 사용된다.