Quicksort (C Plus Plus)

From LiteratePrograms
Jump to: navigation, search
Other implementations: AWK | C | C++ | Erlang | Forth | Haskell | Java | JavaScript | Mathematica | Oz | Python | Python, arrays | Sed | Visual Basic .NET

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

[edit] 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.

[edit] Partition

The partition function moves all elements that are less than the pivot value to the beginnig 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::iter_swap(pivot, end-1);
	IT store=begin;
	for(IT it=begin, e=end-1; it!=e; ++it) {
		if(*it<=piv) {
			std::iter_swap(store, it);
			++store;
		}
	}
	std::iter_swap(end-1, store);
	return store;
}

[edit] Pivot functions

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

[edit] 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;
}

[edit] 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));
	}
};

[edit] Quick sort

<<quick_sort>>=

template<typename IT, typename PF> 
void quick_sort(IT begin, IT end, PF pf)
{
	if(end-1>begin) {
		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>());
}

[edit] 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
hijacker
hijacker
hijacker
hijacker