### 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

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