Yesterday I tried to implement the quick sort algorithm in C++. I think everyone knows the algorithm, and it seems very easy-to-do stuff, but it took me about 1.5 hours to complete and polish it. So I thought it might be useful for some people and decided to share my implementation. I put in very descriptive comments, so I don't think I need to add anything else, the code follows:
// <iterator> header contains the
definitions of
// std::advance, std::distance and
std::iterator_traits
#include <iterator>
// SelectPivot is used to select the
pivot element in
// the sequence which will serve as a
partition point.
// Returns an iterator pointing to the
pivot element.
template <typename
Iter>
Iter SelectPivot(Iter begin, Iter end)
{
// Current implementation just returns the middle element,
// but we are free to choose the pivot in any other way.
std::advance(begin,
std::distance(begin, end) / 2);
return begin;
}
// Implements the quick sort algorithm.
template <typename Iter,
typename Cmp>
void QuickSort(Iter begin, Iter end, Cmp less)
{
// No need to sort an empty or a single-element sequence.
if (std::distance(begin, end) < 2)
{
return;
}
// Select the pivot element and store
// its value in 'val' variable.
Iter
pivot = SelectPivot(begin, end);
std::iterator_traits<Iter>::value_type
val = *pivot;
// Introduce new iterators to operate on,
// begin and end will be needed for recursive
// calls, so we do not modify them.
Iter
left = begin;
Iter
right = end;
// Like all the similar algorithms in STL, our function
accepts
// a pair of iterators, pointing to the first and one
beyond
// the last elements respectively. That's why we should not
// consider the value pointed to by 'end'.
std::advance(right,
-1);
// Move the pivot element to the end of the sequence.
std::swap(*pivot,
*right);
// The following piece of code partitions the whole into
// two sub-sequences so that all the elemets less than the
// pivot appear to the left from pivot and all the greater
// elements appear to the right. This means that the chosen
// pivot element will be in its final place.
Iter
pivot_position = left;
while (left != right)
{
if (less(*left, val))
{
std::swap(*left,
*pivot_position);
std::advance(pivot_position,
1);
}
std::advance(left,
1);
}
// The pivot_position now points to the first
// element which is not 'less' than the pivot. So we
// need to swap the pivot stored in the rightmost
// element with that stored in pivot_position.
std::swap(*pivot_position,
*right);
// Calling the function recursively to
// sort the sub-sequences to the left
// and right from the pivot. The latter
// is already in its final position.
right =
pivot_position;
std::advance(right,
1);
QuickSort(begin,
pivot_position, less);
QuickSort(right,
end, less);
}
