[정렬] 삽입 정렬(Insertion Sort)

삽입 정렬이란

현재 요소를 이전의 정렬된 부분 배열에 삽입해 정렬하는 알고리즘

삽입 정렬의 특징

• 간단한 구현
  • 삽입 정렬은 다른 정렬 알고리즘에 비해 구현이 단순하고 이해하기 쉽다.
• 적은 메모리 사용
  • 제자리 정렬 알고리즘이기 때문에 추가적인 메모리가 거의 필요하지 않다.
• 정렬된 배열에 대해 효율적
  • 이미 정렬된 배열에 대해서는 O(n)의 시간 복잡도로 작동하여 매우 효율적이다.
• 시간 복잡도
  • 최악의 경우 시간 복잡도는 O(n^2)이다. (배열이 역순으로 정렬된 경우)
• 안정적인 정렬
  • 동일한 키를 가진 요소들의 상대적인 순서를 유지하므로 안정적인 정렬 알고리즘이다.
• 적은 데이터 이동
  • 적은 수의 요소를 정렬할 때나 데이터가 대부분 정렬되어 있을 때 효율적이다.

삽입 정렬의 단점

• 최악의 시간 복잡도
  • 최악의 경우 시간 복잡도가 O(n^2)로, 큰 데이터셋을 처리할 때 비효율적이다. 
    예를 들어, 배열이 역순으로 정렬된 경우 각 요소를 삽입하기 위해 계속해서 비교와 이동을 수행해야 한다.
• 상대적으로 느림
  • 데이터가 크고 무작위일 경우 다른 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)에 비해 상대적으로 느리다.
• 부분적으로 정렬되지 않은 배열
  • 데이터가 이미 정렬된 상태가 아니라면, 특히 정렬 순서가 무작위일 경우 성능이 저하된다.
• 외부 데이터에 비효율적
  • 메모리 내부의 데이터를 정렬하는 데 적합하지만, 외부 데이터나 매우 큰 데이터를 다루는 데는 비효율적일 수 있다.
• 병렬 처리가 어려움
  • 삽입 정렬은 순차적으로 실행되므로 병렬 처리가 어렵다. 따라서 멀티 코어 프로세싱을 효과적으로 활용하기 어렵다.

구현 코드(C++)

#include <iostream>
#include <vector>

using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        // 현재 요소를 정렬된 부분 배열에 삽입하는 과정
        cout << "Step " << i << ": " << "key = " << key << endl;
        
        // 정렬된 부분 배열에서 현재 요소를 삽입할 위치를 찾는다
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
            // 현재 상태 출력
            for (int x = 0; x < n; x++) {
                cout << arr[x] << " ";
            }
            cout << endl;
        }
        arr[j + 1] = key;
        
        // 삽입 후 배열 상태 출력
        cout << "Inserted " << key << " at position " << (j + 1) << endl;
        for (int x = 0; x < n; x++) {
            cout << arr[x] << " ";
        }
        cout << endl;
        cout << "-----------------------" << endl;
    }
}

int main() {
    vector<int> arr = {12, 11, 17, 5, 2, 50, 25, 13};
    cout << "Initial array: ";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl << "-----------------------" << endl;

    insertionSort(arr);

    cout << "Sorted array: ";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}