c++ selection sort with separate minimum index function

Question

Hi I'm doing a problem for my c++ class where we are to create a generic selection sort function for all types with separate function that finds minimum index. I tried to modify selection sort function that uses two for loops by separating the two for loops into two separate functions. I tried different ways to approach this problem but I just don't get what I am doing wrong. Please help.

#include <vector>
#include <random>
#include <iostream>
#include<stdexcept>
#include<time.h>
#include <valarray>

using namespace std;

template <typename T>
unsigned min_index(const vector<T> &vals, unsigned index){
    auto min = index;
    for(auto i = index +1; i != vals.end();i++){
        if(*i < *min)
            min = i;
    }
    return min;
}

template <typename T>
void selection_sort(vector<T> &vals){
    for(auto i=vals.begin(); i!=vals.end(); i++){
        auto min = min_index(vals, i);
        swap(*i, *min);
    }
}

Answer 1

You're trying to develop a positional-index based min_index (which is dreadfully broken itself), then use it within an iterator-based selection sort.

template <typename T>
unsigned min_index(const vector<T> &vals, unsigned index)
{
    auto min = index; // min is 'unsigned' like 'index'

    // this loop is nonsense.
    //  'i' is unsigned (because 'index' is unsigned)
    //  'vals.end()' is an iterator, not an unsigned, therefore...
    //  'i != vals.end()` is nonsense.
    //  'min' is also unsigned, therefore...
    //  both *i and *min are nonsense.
    for(auto i = index +1; i != vals.end();i++)
    { 
        if(*i < *min)
            min = i;
    }
    return min;
}

Later on, in your selection-sort...

template <typename T>
void selection_sort(vector<T> &vals){
    // here 'i' is an iterator
    for(auto i=vals.begin(); i!=vals.end(); i++)
    {
        // here you're trying to pass an iterator to a function
        // expecting an unsigned. 
        auto min = min_index(vals, i);

        // and the above function is returning an unsigned
        // therefore *min is nonsense.
        swap(*i, *min);
    }
}

In short, neither of those functions can possibly compile, much less work.

---

You need to choose one or the other and stick with it. This is C++, so the easiest to implement is likely an iterator version. As a bonus, it also ends up being the most generic (there are iterators literally everywhere in modern C++). For example, the min_index, rewritten as min_iter, could look like this:

template<class Iter>
Iter min_iter(Iter beg, Iter end)
{
    auto min = beg;
    for (; beg != end; ++beg)
    {
        if (*beg < *min)
            min = beg;
    }
    return min;
}

Now you can use that in an iterator-based selection-sort as well:

template <class Iter>
void selection_sort(Iter beg, Iter end)
{
    for (; beg != end; ++beg)
        std::iter_swap(beg, min_iter(beg, end));
}

And finally, you can front this with a generic sequence abstraction by utilizing the general std::begin and std::end functions from the standard library:

template<class Seq>
void selection_sort(Seq& seq)
{
    selection_sort(std::begin(seq), std::end(seq));
}

Now you can pass a vector, a deque, an array, etc. Pretty much any sequence container instance will work, so long as the underlying element type supports operator < either natively or by overload.

---

Position Based

A similar solution specific to your container type (a vector) and ordinal position rather than iterators would be something like this:

template <typename T>
unsigned min_index(const std::vector<T> &vals, unsigned index)
{
    unsigned min = index;
    for (unsigned i = index + 1; i < vals.size(); i++)
    {
        if (vals[i] < vals[min])
            min = i;
    }
    return min;
}

template <typename T>
void selection_sort(std::vector<T> &vals)
{
    for (unsigned i = 0; i < vals.size(); i++)
        std::swap(vals[i], vals[min_index(vals, i)]);
}