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