# Insertion sort implementation using iterators and vectors

7237 views
2

I'm trying to implement insertion sort algorithm using iterators and it doesn't seem to work as I thought... Do you have any ideas of how to implement it?

Also, I can't use code like this one: https://www.geeksforgeeks.org/insertion-sort-using-c-stl/ because I'm intending to make an animation and it will get more complicated.

This is my source code so far:

``````#include <iostream>
#include <vector>
#include <algorithm>

int main()
{

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

std::vector<int>::iterator itj;
std::vector<int>::iterator leftmost;

// insertion sort
for (std::vector<int>::iterator iti = seq.begin() + 1; iti != seq.end(); iti = std::next(iti))
{
itj = std::prev(iti);
leftmost = iti;

while (std::distance(seq.begin(), itj) >= 0 && *itj > *leftmost)
{
std::next(itj) = itj;
itj = prev(itj);
}
std::next(itj) = leftmost;
}

// printing
for (std::vector<int>::iterator iti = seq.begin(); iti != seq.end(); iti = std::next(iti))
{
std::cout << *iti << " ";
}

}
``````

Oops, I just realized that the link you shared has an implementation using `rotate`. Can you explain why that doesn't work for your case. Do you want an algorithm that extends insertion sort in some way?

Yeah, kind of... So at the moment, I'm trying to work out with sfml for making a visualization for this algorithm.

You'll need to be specific about what your algorithm is supposed to do. That being said, you should separate the logic of sorting from other logic if possible (unless it's part of the sorting algorithm).

@DanielCalota If you go to the stackoverflow link I have in the comments, the bottom line is to get rid of this test: `*itj > *leftmost`, and instead call a function that returns `true` or `false` depending on whether the left-hand value is placed before the right-hand value. Inside that function, you can do anything else besides returning the value. Also, that geeksforgeeks site -- don't take code examples from there, since most of them are poor.

3

Here's a very elegant implementation of insertion sort using iterators lifted directly from the reference page on rotate:

``````// insertion sort
for (auto i = v.begin(); i != v.end(); ++i) {
std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);
}
``````

All you have to do is understand how `std::rotate` works, and this becomes easy to understand. (`rotate` is anyway a really powerful algorithm that you should be comfortable with).

posted this
10

Here is an implementation taken from SGI STL:

``````template<class Random_it, class T>
void unguarded_linear_insert(Random_it last, T val) {
auto next = last;
--next;
while (val < *next) {
*last = *next;
last = next;
--next;
}
*last = val;
}

template<class Random_it>
void linear_insert(Random_it first, Random_it last) {
auto val = *last;
if (val < *first) {
std::copy_backward(first, last, last + 1);
*first = val;
}
else
unguarded_linear_insert(last, val);
}

template<class Random_it>
void insertion_sort(Random_it first, Random_it last) {
if (first == last)
return;
for (auto i = first + 1; i != last; ++i)
linear_insert(first, i);
}
``````

Note how the `val < *first` condition and `std::copy_backward` are used to simplify the loop inside `unguarded_linear_insert`: only one condition, namely `val < *next` can be checked in that loop.

posted this