Insertion sort implementation using iterators and vectors

Question

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? — cigien, Aug 01 '20 at 14:48
Yeah, kind of... So at the moment, I'm trying to work out with sfml for making a visualization for this algorithm. — Daniel, Aug 01 '20 at 14:53
[A much better discussion on sorting algorithms](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). — PaulMcKenzie, Aug 01 '20 at 14:53
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). — cigien, Aug 01 '20 at 14:54
@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. — PaulMcKenzie, Aug 01 '20 at 14:57

score 3 · Accepted Answer · answered Aug 01 '20 at 14:45

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

Evg · Answer 2 · 2020-08-01T15:05:12.263

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.

¹ The same implementation can be found in libstdc++.

Insertion sort implementation using iterators and vectors

2 Answers2