Algorithm: Insertion sort

Insertion sort:

Insert the current data into a proper position of the sorted array.

Running time is around O(n^2).

/////////////////////////

#include "stdafx.h"

# include <cstdlib>

#include <iostream>     // std::cout

#include <algorithm>    // std::sort

#include <vector>       // std::vector

# include <map>         // std::map

# include <unordered_map>

# include <string>

#include <bitset>

#include <ctype.h>

using namespace std;

class Solution {

public:

       vector<int> InsersionSort(vector<int> s)

       {

           //implement the insersion sort

              int i, j, tmp,sLen=s.size();

              for (i = 1; i < sLen; i++){

                     tmp = s[i];

                     j = i;

                     while (j>0 && tmp < s[j - 1]){

                           s[j] = s[j - 1];

                           j--;

                     }

                     s[j] = tmp;

              }

              return s;

       }

};

int main(int argc, char *argv[])

{

       vector<int> inp = { 3, 4, 1};

       Solution s;

       vector<int> l = s.InsersionSort(inp);

}