Sorting does not work

2

I had to implement my own sort using the sort sort. However, the simple code (I analyzed several times, and for me 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?

    
asked by anonymous 02.05.2014 / 16:56

2 answers

1

There are a number of factors involved here.

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

Correcting your code would look like this (already adapting to 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 fixed here:

  • else return; is useless
  • selection sort could be done without recursion, in fact, would spend less memory doing with two for , instead of with recursion
  • Using the subtraction result of the vectors to get an integer (in this case, the vector size) is not very advisable ... I would replace the parameter T* end with int count , since end does not is used for nothing, even
  • The parameter unsigned pos should be replaced with int pos , to make the type match (you are using int to i , but unsigned to pos )

To illustrate how I would get these changes 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]);
        }
    }
}
    
02.05.2014 / 17:36
1

The error is at startup of i , where pos+1 is only 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 do not need to reset swap() , you can use std::swap() instead.

Code I tested

Or you can quit using the pos variable 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);
    }
}
    
02.05.2014 / 17:33