### C++: Insertion Sort using STL (Sorting)

An

**insertion sort**is generally described simply as: read each element in turn, and insert it in the right position among the previous read (and sorted) elements.

It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

However, insertion sort provides several advantages:

➧ Simple implementation

➧ Efficient for (quite) small data sets, much like other quadratic sorting algorithms

Source: Wikipedia

void insertionSort(std::vector<int>& vec){

for(auto it = vec.begin(); it != vec.end(); it++)

{

// Search

auto const insertion_point = std::upper_bound(vec.begin(), it, *it);

//insert

std::rotate(insertion_point, it, it+1);

}

}

Here we have used std::upper_bound and std::rotate

std::upper_bound

Returns an iterator pointing to the first element in the range [first, last) that is greater than value.

std::rotate

It rotates the order of the elements in the range [first,last], in such a way that the element pointed by middle becomes the new first element.

You must also know about Iterators.

#include<iostream>

#include<vector>

#include<algorithm>

void insertionSort(std::vector<int>& vec){

for(auto it = vec.begin(); it != vec.end(); it++)

{

// Search

auto const insertion_point = std::upper_bound(vec.begin(), it, *it);

//insert

std::rotate(insertion_point, it, it+1);

}

}

void print(std::vector<int> const& vec){

for( int x : vec)

std::cout << x << " ";

std::cout << '\n';

}

int main(){

std::vector<int> arr = {2, 1, 5, 3, 7, 5, 4, 6};

insertionSort(arr);

print(arr);

}

You can download this code from here

If you are unable to understand the above then you should study Standard Template Library.

Here is the simple version of Insertion Sort

#include<iostream>

#include<vector>

void insertionSort(std::vector<int>& vec)

{

for(unsigned j = 1; j < vec.size(); j++)

{

int key = vec[j];

int i = j-1;

while(i >= 0 && vec[i] > key)

{

vec[i+1] = vec[i];

i--;

}

vec[i+1] = key;

}

}

void print(std::vector<int> vec){

for(unsigned i = 0; i < vec.size(); i++){

std::cout << vec[i] << " ";

}

}

int main(){

std::vector<int> arr = {2, 1, 5, 3, 7, 5, 4, 6};

insertionSort(arr);

print(arr);

std::cout<<std::endl;

}

You can download this code from here.

Follow us on

Reference:

**You may also like**

**C++: Pointers**

**How do I learn competitive programming as a beginner?**

**How do I learn data structures and algorithms from scratch**

**C++ STL :Implementation of Counting sort (Sorting)**

**What is "namespace" and why do we use it?**

## Comments

## Post a Comment