Data Structures - Insertion Sort

Basic programming - Insertion Sort

Approach:

Need to use two for-loop. One is unsorted data in the range [i:n] and the other is sorted data in the range [0:i].

Take one element from unsorted data to compare with sorted data.
Step 1: use temp variable to store this element
Step 2: search value from sorted data which is bigger than temp , if true, move the bigger value to current position vector[j] = vector[j - 1]
Step 3: Until if-statement returns false, it means the value of j - 1 is smaller than temp, so insert temp to current position vector[j] = temp.

Time complexity:

Best Case：Ο(1)

Worst Case：Ο(n²)

Average Case：Ο(n²)

P.S. If input is sorted, just compare every elements once!

Space complexity: O(1)

Stable/Unstable: Stable

Source code

Version 1

#include <iostream>
#include <vector>

using namespace std;

void insertSort(vector<int>& v){
  int i, j, temp;
  for(i = 0; i < v.size(); ++i){
      temp = v[i];
      for(j = i; j > 0 && temp < v[j - 1]; --j){
          v[j] = v[j - 1];
      }
      v[j] = temp;
  }  
};

int main()
{
    vector<int> input = {39,63,89,66,42,21,80,22,81,47};
    insertSort(input);
    
    for(int i = 0; i < input.size(); ++i){
        cout << input[i] << " ";
    }
    return 0;
}