// // In this example we sort template arrays // See pages 347--353 of Budd's book #ifndef QUICKSORT_H #define QUICKSORT_H // This function is already defined in STL. Comment out // if stl_algobase.h or somesuch is included template< class T > void swap( T& x, T& y ){ T z = x; x = y; y = z; } template< class T > int pivot( T a[], int start, int stop, int pos ){ swap( a[start], a[pos] ); int low = start + 1; int high = stop; while( low <= high ){ if( a[low] < a[start] ) low++; else { if ( a[high] < a[start] ) swap( a[low], a[high] ); else high--; } } swap( a[start], a[--low] ); // swap the pivot elt back into place return low; } template< class T > void quicksort( T a[], int low, int high ){ if( low >= high ) return; int pivotIndex = pivot( a, low, high, (low+high)/2 ); if( low < pivotIndex ) quicksort( a, low, pivotIndex ); if( pivotIndex < high ) quicksort( a, pivotIndex + 1, high ); } //---------------------------------------------------------------------- // the following is a somewhat ugly method of sorting two arrays, // the first sorted, and the second being swapped in sync with the // first one. template< class T, class S > void swap_two( T& x, T& y, S& a, S& b ){ T z = x; x = y; y = z; S c = a; a = b; b = c; } template< class T, class S > int pivot_two( T a[], int start, int stop, int pos, S z[]){ swap_two( a[start], a[pos], z[start], z[pos] ); int low = start + 1; int high = stop; while( low <= high ){ if( a[low] < a[start] ) low++; else { if ( a[high] < a[start] ) swap_two( a[low], a[high], z[low], z[high] ); else high--; } } low--; swap_two( a[start], a[low], z[start], z[low] ); // swap the pivot elt back into place return low; } template< class T, class S > void quicksort_two( T a[], int low, int high, S z[] ){ if( low >= high ) return; int pivotIndex = pivot_two( a, low, high, (low+high)/2, z ); if( low < pivotIndex ) quicksort_two( a, low, pivotIndex, z ); if( pivotIndex < high ) quicksort_two( a, pivotIndex + 1, high, z ); } #endif // QUICKSORT_H