# Insertion sort implementation using iterators and vectors

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 << " ";
}
}
```

Yeah, kind of... So at the moment, I'm trying to work out with sfml for making a visualization for this 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.

### 2 Answers

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).

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.

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?