[알고리즘] 삽입 정렬 (Insertion Sort)

삽입 정렬 (Insertion Sort)

앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식

시간복잡도 : (n-1) + (n-2) + (n-3) + ... + 2 + 1 -> n(n-1)/2 즉, O(n^2)

하지만, 모두 정렬되어 있는 경우 한 번씩 밖에 비교를 안하므로 O(n)의 시간복잡도를 가진다.

공간복잡도 : O(n)

장점

• 구현이 간단하고 이해하기 쉽다.
  • 원소를 적절한 위치에 삽입하는 과정을 반복하는 간단한 알고리즘으로 구현하기가 비교적 간단하고, 알고리즘의 동작 방식도 직관적이다.
    
    
• 작은 규모의 배열에서 효율적이다.
  
  • 삽입 정렬은 이미 정렬된 부분 배열에 새로운 원소를 삽입하는 방식으로 정렬을 수행한다. 따라서 입력 배열이 거의 정렬되어 있는 경우, 다른 알고리즘보다 효율적일 수 있다.
    
    
• 안정적인 정렬 알고리즘이다. (Stable Sort)
  
  • 삽입 정렬은 동일한 값에 대해서도 상대적인 순서를 보존하면서 정렬을 수행한다. 즉, 입력 배열 내에서 값이 같은 요소들의 순서는 정렬 전후에도 동일하게 유지된다.
    
    

단점

• 성능이 비효율적이다.
  • 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적이다.
    
    
• 버블 정렬과 선택 정렬과 마찬가지로 배열의 길이가 길어질수록 비효율적이다.
  
  

삽입 정렬 구현

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // key보다 큰 원소를 오른쪽으로 한 칸씩 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // key를 올바른 위치에 삽입
        arr[j + 1] = key;
    }
}