Quicksort (C Plus Plus)

From LiteratePrograms

Other implementations: AWK | C | C++ | Eiffel | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Mercury | Oz | Python | Python, arrays | Scala | Sed | Standard ML | Visual Basic .NET | XProc

An implementation of quick sort in c++.

<<quicksort.cpp>>=
includes
partition
pivot_functions
quick_sort
test_driver

<<includes>>=
#include <iostream>
#include <algorithm>	// std::swap()
#include <vector>

Contents 1 Overview 2 Partition 3 Pivot functions 3.1 Median of first, middle and last 3.2 Random 4 Quick sort 5 Testing

Overview

Quick sort works like this:

• Select a pivot value in the list
• Move all smaller elements to the beginning of the array
• Repeat recursively for both smaller and bigger values

This implementation uses the template-functionality in c++ so that it can work on different containers and data types.
The IT template parameter can be any random-access iterator type (including raw pointers).
A complete generic implementation would also include a comparison function parameter, so that the user could choose the sort order.

Partition

The partition function moves all elements that are less than the pivot value to the beginning of the array.

<<partition>>=
template<typename IT> 
IT partition(IT begin, IT end, IT pivot)
{
	typename std::iterator_traits<IT>::value_type piv(*pivot);
	std::swap(*pivot, *(end-1));
	IT store=begin;
	for(IT it=begin; it!=end-1; ++it) {
		if(*it<=piv) {
			std::swap(*store, *it);
			++store;
		}
	}
	std::swap(*(end-1), *store);
	return store;
}

Pivot functions

quick_sort() takes a functor describing the pivot-selection algorithm. We provide two alternatives:

Median of first, middle and last

<<pivot_functions>>=
template<typename IT>
IT pivot_median(IT begin, IT end)
{
	IT pivot(begin+(end-begin)/2);
	if(*begin<=*pivot && *(end-1)<=*begin) pivot=begin;
	else if(*(end-1)<=*pivot && *begin<=*(end-1)) pivot=end-1;
	return pivot;
}

Random

<<pivot_functions>>=
template<typename IT>
struct pivot_random {
	pivot_random() {
		srand(time(NULL));
	}
	IT operator()(IT begin, IT end) {
		return begin+(rand()%(end-begin));
	}
};

Quick sort

<<quick_sort>>=
template<typename IT, typename PF> 
void quick_sort(IT begin, IT end, PF pf)
{
	if((end-begin)>1) {
		IT pivot=pf(begin, end);
		pivot=partition(begin, end, pivot);
		quick_sort(begin, pivot, pf);
		quick_sort(pivot+1, end, pf);
	}
}

We provide an overloaded version of quick_sort() that uses pivot_random.

<<quick_sort>>=
template<typename IT>
void quick_sort(IT begin, IT end)
{
	quick_sort(begin, end, pivot_random<IT>());
}

Testing

This test program will first run quick_sort() on a vector of strings, and then do the same on an array of integers.
Note that sorting of strings (and other classes) implies calling copy-constructor and destructor many times, which might lead to bad performance.

<<test_driver>>=
template<typename T> void print(const T &data)
{
	std::cout<<" "<<data;
}
int main()
{
	std::vector<std::string> v(10);
	v[0]="Paris";
	v[1]="London";
	v[2]="Stockholm";
	v[3]="Berlin";
	v[4]="Oslo";
	v[5]="Rome";
	v[6]="Madrid";
	v[7]="Tallinn";
	v[8]="Amsterdam";
	v[9]="Dublin";
	std::cout<<"v before qsort: ";
	std::for_each(v.begin(), v.end(), print<std::string>);
	std::cout<<'\n';
	quick_sort(v.begin(), v.end());
	std::cout<<"v after qsort: ";
	std::for_each(v.begin(), v.end(), print<std::string>);
	std::cout<<'\n';
	int a[]={3,8,0,6,7,4,2,1,9,3,1,8,3,9,2,0,9};
	int *a_end=a+sizeof a/sizeof(int);
	std::cout<<"a before qsort: ";
	std::for_each(a, a_end, print<int>);
	std::cout<<'\n';
	quick_sort(a, a_end, pivot_random<int*>());
	std::cout<<"a after qsort: ";
	std::for_each(a, a_end, print<int>);
	std::cout<<'\n';
	return 0;
}

Download code