Sorting does not work

Question

I had to implement my own Sort, using Selection Sort. However, the simple code (I analyzed several times, and for me it is correct) gives strange results.

template <typename T> void swap(T& var, T& var1)
{
    T temp = var;
    var = var1;
    var1 = temp;
}
template <typename T> void selection_sort(T* begin, T* end, unsigned pos = 0) //1 3 5 2 4; tamanho 5
{
    if(begin != end)
    {
        for(int i = pos+1; i < (end - begin) + pos; i++)
        {
            if(begin[pos] > begin[i]) swap(begin[pos], begin[i]);
        }
        selection_sort(begin+1, end, pos+1);
    }
    else return;
}
//resultado 1 3 0 5 0

What’s wrong? What should be done to fix it?

Answer 1

Error is on startup i, where is pos+1 it’s just pos.

template <typename T> void selection_sort(T* begin, T* end, unsigned pos = 0u) 
{
    if(begin != end)
    {
        for(int i = pos; i < (end - begin) + pos; i++)
        {
            if(begin[pos] > begin[i]) std::swap(begin[pos], begin[i]);
        }
        selection_sort(begin + 1, end, pos);
    }
}

Another thing, you don’t need to reset swap(), can use std::swap() instead.

Code I Tested

---

Or you can stop using the variable pos that does not affect the algorithm:

template <typename T> void selection_sort(T* begin, T* end) 
{
    if(begin != end)
    {
        for(int i = 0; i < (end - begin); i++)
        {
            if(begin[0] > begin[i]) std::swap(begin[0], begin[i]);
        }
        selection_sort(begin + 1, end);
    }
}

Answer 2

There are a number of factors involved here.

First, the mistake is in passing begin+1 and pos+1 for the recursive call of selection_sort. By adding 1 to begin, you effectively lose elements, since by adding 1 to the pos, for example, in the second iteration, you will be taking the index 1 of a vector that has already been incremented, so you are taking the element 2.

Fixing your code would look like this (already adapting the new stop condition):

template <typename T> void selection_sort(T* begin, T* end, unsigned pos = 0)
{
    if(pos < ((end - begin) - 1))
    {
        for(int i = pos+1; i < (end - begin); i++)
        {
            if(begin[pos] > begin[i]) swap(begin[pos], begin[i]);
        }
        selection_sort(begin, end, pos+1);
    }
    else return;
}

However, although it works, there are a few more things that could be arranged here:

• the else return; is useless
• Selection Sort could be done without recursion, by the way, it would spend less memory doing with two for, instead of with recursion
• using the subtraction result of the vectors to obtain an integer (in your case, the vector size) is not very advisable... I would replace the parameter T* end for int count, since end is not used for anything, whether or not
• the parameter unsigned pos should be replaced by int pos, to make the type match (you are using int for i, but unsigned for pos)

To illustrate how you would look with these changes that I suggested:

template <typename T> void selection_sort(T* begin, int count)
{
    for (int pos = 0; pos < count - 1; pos++)
    {
        for (int i = pos+1; i < count; i++)
        {
            if (begin[pos] > begin[i]) swap(begin[pos], begin[i]);
        }
    }
}