Insertion Sort ใช้ C++ STL

คำอธิบาย

Implementation ของ Insertion Sort โดยใช้ std::upper_bound หาตำแหน่งที่ควรวาง และ std::rotate ย้าย element

วิธีทำ

1. วน i จาก begin() ถึง end()
2. หา insertion_point = upper_bound(begin, i, *i)
3. rotate(insertion_point, i, i+1) ย้าย element ไปตำแหน่งที่ถูกต้อง

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

void insertionSort(vector<int>& vec) {
    for(auto it = vec.begin(); it != vec.end(); ++it) {
        auto insertion_point = upper_bound(vec.begin(), it, *it);
        rotate(insertion_point, it, it + 1);
    }
}

void print(const vector<int>& vec) {
    for(int x : vec) cout << x << " ";
    cout << '\n';
}

int main() {
    vector<int> arr = {2, 1, 5, 3, 7, 5, 4, 6};
    insertionSort(arr);
    print(arr);
    return 0;
}

เอาต์พุต

1 2 3 4 5 5 6 7