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);
    }
}

CodePudding user response：

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.

CodePudding user response：

so this is what I have right now and the code is compiling. But when I ran a vector with {5, 3, 2, 1, 4} I just get 3.

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