[알고리즘] 삽입 정렬 (insertion sort)

설명

배열의 모든 요소를 앞에서부터 비교하며, 자신이 들어갈 위치를 찾아 삽입하여 정렬한다.

이미지 출처

시간복잡도

O(n^2)

코드

#include <iostream>
#include <vector>
using namespace std;
void insertion_sort(vector<int> &nums) {
    int i, j ,data;
    for (i = 1; i < nums.size(); i++) {
        data = nums[i];
        for(j = i-1; j>=0; j--) {
            if (nums[j] > data) {
                nums[j+1] = nums[j]; // 한칸씩 이동.
            } else {
                break;
            }
        }
        nums[j+1] = data;
    }
}
int main() {
    vector<int> nums = {5,4,1,3,2};
    insertion_sort(nums);

    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
}