C++クイックソートテンプレート法
1604 ワード
#include <stdio.h>
#include <string>
using std::string;
#include <iostream>
using namespace std;
template<typename T>
void
mySwap( T & left, T & right )
{
T tmp = left;
left = right;
right = tmp;
}
template<typename T>
int
partion( T array[] ,int begin ,int end )
{
int i = begin;
int j = end + 1;
T x = array[ begin ];
while ( true )
{
while( array[++i] < x );
while( array[--j] > x );
if ( i > j )
{
break;
}
mySwap(array[i], array[j]);
}
mySwap(array[begin],array[j]);
return j;
}
template<typename T>
void
realQuickSort( T array [] , int begin, int end )
{
if ( begin < end )
{
int qValue = partion( array, begin,end );
realQuickSort( array, begin, qValue );
realQuickSort( array, qValue + 1, end );
}
}
template<typename T>
void
quickSort( T array[] ,int len )
{
realQuickSort(array,0,len-1);
}
template<typename T>
void
arrayDump( T array[] , int len )
{
for ( int i = 0 ; i < len ; i ++ )
{
cerr << array[i] << " ";
}
cout << "dump finished
"<< endl;
}
int main(int argc, char const *argv[])
{
int array1[] = {13,2,4,1,98,32};
float array2[] = {190.2, 30.2, 0.54, 12,0.28,0.05 };
quickSort<int>(array1, sizeof(array1)/sizeof(array1[0]));
arrayDump<int>( array1, sizeof(array1)/sizeof(array1[0]) );
quickSort<float>(array2, sizeof(array2)/sizeof(array2[0]));
arrayDump<float>( array2,sizeof(array2)/sizeof(array2[0]));
return 0;
}