Insertion sort implementation using iterators and vectors

7237 views c++ iterator stl
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 << " ";
    }
    

}

answered question

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.

2 Answers

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

Have an answer?

JD

Please login first before posting an answer.

Ads

Categories