Insert Sort

Textbook

Description:

Example:

Note

Idea:

• Stable
• In place
• Time: O(n2)

Code:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void insertSort(vector<int> & nums){
    int n=nums.size();

    for(int i=1; i<n; ++i){
        int tmp=nums[i];
        int j=i-1;
        while(j>=0 && nums[j]>tmp){
            nums[j+1] = nums[j];
            j--;
        }
        nums[j+1]=tmp;
    }

}

int main(){
    vector<int> input={3,4,2,5,6,7,2,3,3,8,9,23,43,22,1,23};

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

    insertSort(input);

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

}