배열의 모든 요소를 앞에서부터 차례대로 “이미 정렬된 배열 부분과 비교”하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

Insertion Sort는 손안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다. 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.

⚙ Process

1. 2번째 위치 값을 temp에 저장한다. temp 이전 위치의 값들과 비교를 진행한다.
2. 비교값이 tmep 보다 클 시 위치변경, 아닐 시 반복 종료
3. 1, 2 과정을 반복하여 정렬을 수행한다.

✅ JAVA Code

public int[] InsertionSort(int[] arr){
        for(int i=1; i<arr.length; i++){
            int temp = arr[i];
            int prev;

            for(prev=i-1; prev>=0; prev--){
                if(temp < arr[prev])
                    arr[prev+1] = arr[prev];
                else break;
            }
            arr[prev+1] = temp;
        }
        return arr;
    }

◻시간복잡도

최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 이다.

하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한번씩 밖에 비교를 안하므로 O(n) 의 시간복잡도를 가지게 된다. 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.

최선의 경우는 O(n), 평균과 최악의 경우 O(n^2)

◻공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 **O(n)**이다.

◻장점

알고리즘이 단순하다.

대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.

정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)

안정 정렬(Stable Sort) 이다.

Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

◻단점

평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.

Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적이다.