-
Quicksort question
i have been working on an implimentation of quicksort for the past few minutes, and i have what appears to be a correct implimentation of the algorithm, and yet it doesnt quite sort 100%... it works like a dream for a large number of items, but small numbers tend to get sorted with a slight bit of inaccuracy ( the smaller the number of items, the less accurate ). here is the code i have, any ideas what my problem might be?
Code:
template <typename Type>
void Swap( Type &a, Type &b )
{
Type temp = a;
a = b;
b = temp;
}
template <typename Type>
void qSort( Type * array, int size )
{
if ( size <= 1 )
return;
int middle = size / 2;
if ( array[middle] < array[0] )
Swap( array[middle], array[0] );
if ( array[size - 1] < array[0] )
Swap( array[size - 1], array[0] );
if ( array[size - 1] < array[middle] )
Swap( array[size - 1], array[middle] );
Type pivot = array[middle];
Swap( array[middle], array[size - 1] );
int i, j;
for ( i = 0, j = size - 1 ;; )
{
while ( array[++i] < pivot );
while ( pivot < array[--j] );
if ( i < j )
Swap( array[i], array[j] );
else break;
}
Swap( array[i], array[size - 1] );
qSort( &array[0], i - 1 );
qSort( &array[i + 1], ( size - (i + 1) ) );
}
-
It's a little late for me to throw my brain into it, so I'll just show you what I use.
Code:
template <class number>
unsigned partition(number section[], unsigned start, unsigned finish, bool (*compare)(number, number) = greater)
{
unsigned pivot = start;
number value = section[pivot];
for( unsigned index = start + 1; index < finish ; ++index )
if( !compare( section[index], value ) )
swap(section[index], section[++pivot]);
swap(section[start], section[pivot]);
return pivot;
}
template <class number>
void quicksort(number section[], unsigned start, unsigned finish, bool (*compare)(number, number) = greater)
{
if(start < finish)
{
unsigned pivot = partition(section, start, finish, compare);
quicksort(section, start, pivot, compare);
quicksort(section, pivot + 1, finish, compare);
}
return;
}
template <class number>
void quicksort(number section[], unsigned length, bool (*compare)(number, number) = greater)
{
quicksort(section, 0, length, compare);
}