quicksort.cpp

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <list>
#include <vector>

template <typename Type>
static int quicksort_compare(Type a,Type b)
{
	return a-b;
}

template <>
static int quicksort_compare<char *>(char *a,char *b)
{
	return strcmp(a,b);
}

template <typename Type,typename Iterator>
void quicksort(Iterator begin,Iterator end
    ,int (*compare)(Type,Type) = quicksort_compare)
{
	Iterator first2last = begin,last2first = end
	    ,counter = begin,counter_ = begin;
	Type pivot = *begin;
	first2last++;
	counter_++;
	while(first2last != last2first){
		while(0 < compare(pivot,*first2last)){
			first2last++;
		}
		while(0 >= compare(pivot,*last2first) && first2last != last2first){
			last2first--;
		}
		std::iter_swap(first2last,last2first);
	}
	while(counter_ != last2first){
		*counter++ = *counter_++;
	}
	*counter = pivot;
	quicksort(begin,--counter,compare);
	quicksort(first2last,end,compare);
}

template <typename Type,typename Container>
void quicksort(Container &array,int (*compare)(Type,Type) = quicksort_compare)
{
	quicksort(array.begin(),--array.end(),compare);
}

template <typename Container>
void print_container(Container container)
{
	typename Container::iterator iter = container.begin();
	while(iter != container.end()){
		std::cout << *iter;
		iter++;
		if(iter != container.end()){
			std::cout << ",";
		}
	}
	std::cout << std::endl;
}

template <typename Container>
void add_random_elements(Container &container,size_t elements)
{
	while(elements--){
		container.push_back(rand()%64);
	}
}

int compare_integer(int a,int b)
{
	return a-b;
}

int main(void)
{
	std::vector<int> array;
	std::list<int> list;
	srand((unsigned)time(NULL));
	add_random_elements(array,32);
	add_random_elements(list,32);
	std::cout << "Before" << std::endl;
	print_container(array);
	print_container(list);
	quicksort(array,compare_integer);
	quicksort(list,compare_integer);
	std::cout << "After" << std::endl;
	print_container(array);
	print_container(list);
	return 0;
}