This is a simple sorting algorithm that we teach in our introductory CS programming class.
procedure SortScoreArray (ScoreArray : IN OUT TestScoreArrayType,
Size: IN integer) is
-- Sort the elements in the array.
IndexOfMin : Natural;
begin
For PositionToFill in 1..Size-1 loop
IndexOfMin := PositionToFill;
For ItemToCompare in PositionToFill+1..Size loop
If ScoreArray(ItemToCompare) < ScoreArray(IndexOfMin) then
IndexOfMin := ItemToCompare;
end if;
end loop;
If IndexOfMin /= PositionToFill then
Swap(ScoreArray(IndexOfMin),ScoreArray(PositionToFill));
end if;
end loop;
end SortScoreArray;
Mergesort is a fairly simple recursive algorithm. Recursive algorithms are defined in terms of themselves, meaning that they solve a big problem by breaking it into smaller problems that they solve using the same method. The solutions to the smaller problems are then somehow combined to form a solution to the larger problem.
/**
* Mergesort algorithm (driver).
*/
template
void mergeSort( vector & a )
{
vector tmpArray( a.size( ) );
mergeSort( a, tmpArray, 0, a.size( ) - 1 );
}
/**
* Internal method that makes recursive calls.
* a is an array of Comparable items.
* tmpArray is an array to place the merged result.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template
void mergeSort( vector & a,
vector & tmpArray, int left, int right )
{
if( left < right )
{
int center = ( left + right ) / 2;
mergeSort( a, tmpArray, left, center );
mergeSort( a, tmpArray, center + 1, right );
merge( a, tmpArray, left, center + 1, right );
}
}
/**
* Internal method that merges two sorted halves of a subarray.
* a is an array of Comparable items.
* tmpArray is an array to place the merged result.
* leftPos is the left-most index of the subarray.
* rightPos is the index of the start of the second half.
* rightEnd is the right-most index of the subarray.
*/
template
void merge( vector & a, vector & tmpArray,
int leftPos, int rightPos, int rightEnd )
{
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;
// Main loop
while( leftPos <= leftEnd && rightPos <= rightEnd )
if( a[ leftPos ] <= a[ rightPos ] )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
while( leftPos <= leftEnd ) // Copy rest of first half
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
while( rightPos <= rightEnd ) // Copy rest of right half
tmpArray[ tmpPos++ ] = a[ rightPos++ ];
// Copy tmpArray back
for( int i = 0; i < numElements; i++, rightEnd-- )
a[ rightEnd ] = tmpArray[ rightEnd ];
}
For most purposes Quicksort is considered to be the fastest sorting algorithm available. As with Mergesort it is also recursive.
/**
* Quicksort algorithm (driver).
*/
template
void quicksort( vector & a )
{
quicksort( a, 0, a.size( ) - 1 );
}
/**
* Standard swap
*/
template
inline void swap( Comparable & obj1, Comparable & obj2 )
{
Comparable tmp = obj1;
obj1 = obj2;
obj2 = tmp;
}
/**
* Return median of left, center, and right.
* Order these and hide the pivot.
*/
template
const Comparable & median3( vector & a, int left, int right )
{
int center = ( left + right ) / 2;
if( a[ center ] < a[ left ] )
swap( a[ left ], a[ center ] );
if( a[ right ] < a[ left ] )
swap( a[ left ], a[ right ] );
if( a[ right ] < a[ center ] )
swap( a[ center ], a[ right ] );
// Place pivot at position right - 1
swap( a[ center ], a[ right - 1 ] );
return a[ right - 1 ];
}
/**
* Internal quicksort method that makes recursive calls.
* Uses median-of-three partitioning and a cutoff of 10.
* a is an array of Comparable items.
* left is the left-most index of the subarray.
* right is the right-most index of the subarray.
*/
template
void quicksort( vector & a, int left, int right )
{
if( left + 10 <= right )
{
Comparable pivot = median3( a, left, right );
// Begin partitioning
int i = left, j = right - 1;
for( ; ; )
{
while( a[ ++i ] < pivot ) { }
while( pivot < a[ --j ] ) { }
if( i < j )
swap( a[ i ], a[ j ] );
else
break;
}
swap( a[ i ], a[ right - 1 ] ); // Restore pivot
quicksort( a, left, i - 1 ); // Sort small elements
quicksort( a, i + 1, right ); // Sort large elements
}
else // Do an insertion sort on the subarray
insertionSort( a, left, right );
}