Quick sort
Quick sort [1] works well for a variety of different kinds of input data. Quick sort is a divide-and-conquer method for sorting. It works by partitioning an array into two parts, then sorting the parts independently. The difficulty of the method is the partitioning process, which rearranges the array to make the following three conditions hold:
The entry a[j] is in its final place in the array, for some j.
No entry in a[lo] through a[j-1] is greater than a[j].
No entry in a[j+1] through a[hi] is less than a[j].
Partitioning: First, we arbitrarily choose a[lo] to be the partitioning item (pivot). Next, we scan the left part of the array until we find an entry that is greater than (or equal to) the partitioning item, and we examine the right part of the array until we find an entry less than (or equal to) the partitioning item, finally we exchange them. When the scan indices cross,the partitioning process is completed by exchange the partitioning item a[lo] with the rightmost entry of the left subarray (a[j]) and return its index j.
The figure demonstrate the quick sort algorithm. The yellow one represents the pivot, the blue one the entries which are smaller and the red one which are larger then the pivot. The transparent node show the actual indexes. We choose pivot in random but our first step is to place it to the first place of the array. It is just an algorithmic trick for remember the pivot.
We choose random pivot for the algorithm. It makes more stable the quick sort.
/// ========== Choosing PIVOT ==========
// random pivot
template<class Iter>
struct random_pivot {
Iter operator()(Iter first, Iter end) {
return first + rand() % (std::distance(first, end));
}
};
The divide function scan the left and the right side of the pivot, swaps the relevant element and finally return back the new border index.
/// ========== Quick sort ==========
// divide function
template<class Iter>
Iter divide(Iter first, Iter end, Iter pivot) {
auto last = end - 1;
std::swap(*pivot, *first); // swap the first element and the pivot
auto left = first;
pivot = left;
auto right = last;
while (left < right) {
while (*left <= *pivot && left < last)
++left;
while (*right >= *pivot && right > first)
--right;
if (left < right)
std::swap(*left, *right);
}
std::swap(*pivot, *right);
return right;
}
The sort algorithm runs recursively and call itself with the new border index.
template<class Iter, class Pivot>
void quick_sort(Iter first, Iter end, Pivot pivot) {
if (first < end) {
auto border = divide(first, end, pivot(first, end)); // divide the range two part
quick_sort(first, border, pivot); // call quick_sort in recursive way for the two independent part
quick_sort(++border, end, pivot);
}
}
// call quick sort with random pivot
// we can define other pivot type like middle pivot
template<class Iter>
void quickSort(Iter first, Iter end) {
quick_sort(first, end, random_pivot<int*>());
}
Main provides us test functions to demonstrate the quick sort.
#include <iostream>
#include <random>
#include <functional>
#include <ctime>
const int n = 10;
////////// Using random generator engine //////////
std::default_random_engine gen((unsigned int)std::time(0));
std::uniform_int_distribution<int> distribution(1, 50);
auto randInt = std::bind(distribution, gen); // using randInt() generate integer number between (1-50)
template<class Iter>
void printArray(Iter begin, Iter end) {
for (auto i = begin; i != end; i++) {
std::cout << *i << ", ";
}
std::cout << std::endl;
}
template<class Iter>
void testSorting(int* testArray, void(*sort)(Iter, Iter)) {
std::cout << "original: ";
printArray(testArray, testArray + n);
sort(testArray, testArray + n);
std::cout << "sorted: ";
printArray(testArray, testArray + n);
}
std::cout << "Testing sort algorithms ...\n\n";
int* test = new int[n];
auto generate = [](decltype(test[0]) i){ i = randInt(); };
std::for_each (test, test + n, generate);
std::cout << "*** Quick sort: ***\n";
testSorting<decltype(test)> (test, quickSort);
std::cout << "\n";
delete[] test;