[정렬] 삽입 정렬

1. 설명

• 현재 요소를 앞쪽 정렬된 부분과 비교하여 적절한 위치에 삽입.
• O(n²)의 시간복잡도이지만, 거의 정렬된 경우 매우 빠름 (O(n)).
• 데이터가 적거나 정렬이 거의 완료된 경우에 적합.

 

2. 코드

#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;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    insertionSort(arr);

    for (int num : arr) cout << num << " ";
}