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

Popular Posts

C++: Selection sort using STL

Top 10 Web Sites Every Programmer Should Visit Daily