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