## C++, sort, quick_sort_3.cpp

``````/**
* @file
* @brief Implementation Details
* @details Quick sort 3 works on Dutch National Flag Algorithm
* The major difference between simple quicksort and quick sort 3 comes in the
* function partition3 In quick_sort_partition3 we divide the vector/array into
* 3 parts. quick sort 3 works faster in some cases as compared to simple
* quicksort.
* @author immortal-j
* @author [Krishna Vedala](https://github/kvedala)
*/
#include <algorithm>
#include <cassert>
#include <ctime>
#include <iostream>
#include <vector>

namespace {
/**
* Operator to print the array.
* @param out std::ostream object to write to
* @param arr array to write
*/
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &arr) {
for (size_t i = 0; i < arr.size(); ++i) {
out << arr[i];
if (i < arr.size() - 1) {
out << ", ";
}
}
return out;
}

}  // namespace

/**
* @namespace sorting
* @brief Sorting Algorithms
*/
namespace sorting {
namespace {  // using un-named namespace here to prevent partition function
// being visible to end-users
/** This function partitions `arr[]` in three parts
* 1. \f\$arr[l\ldots i]\f\$ contains all elements smaller than pivot
* 2. \f\$arr[(i+1)\ldots (j-1)]\f\$ contains all occurrences of pivot
* 3. \f\$arr[j\ldots r]\f\$ contains all elements greater than pivot
* @tparam T type of data in the vector array
* @param [in,out] arr vector array being partitioned
* @param [in] low lower limit of window to partition
* @param [in] high upper limit of window to partition
* @param [out] i updated lower limit of partition
* @param [out] j updated upper limit of partition
*/
template <typename T>
void partition3(std::vector<T> *arr, int32_t low, int32_t high, int32_t *i,
int32_t *j) {
// To handle 2 elements
if (high - low <= 1) {
if ((*arr)[high] < (*arr)[low]) {
std::swap((*arr)[high], (*arr)[low]);
}
*i = low;
*j = high;
return;
}

int32_t mid = low;
T pivot = (*arr)[high];
while (mid <= high) {
if ((*arr)[mid] < pivot) {
std::swap((*arr)[low++], (*arr)[mid++]);
} else if ((*arr)[mid] == pivot) {
mid++;
} else if ((*arr)[mid] > pivot) {
std::swap((*arr)[mid], (*arr)[high--]);
}
}

// update i and j
*i = low - 1;
*j = mid;  // or high-1
}
}  // namespace

/** 3-way partition based quick sort. This function accepts array pointer and
* modified the input array.
* @tparam T type of data in the vector array
* @param [in,out] arr vector array to sort
* @param [in] low lower limit of window to partition
* @param [in] high upper limit of window to partition
*/
template <typename T>
void quicksort(std::vector<T> *arr, int32_t low, int32_t high) {
if (low >= high) {  // 1 or 0 elements
return;
}

int32_t i = 0, j = 0;

// i and j are passed as reference
partition3(arr, low, high, &i, &j);

// Recur two halves
quicksort(arr, low, i);
quicksort(arr, j, high);
}

/** 3-way partition based quick sort. This function accepts array by value and
* creates a copy of it. The array copy gets sorted and returned by the
* function.
* @tparam T type of data in the vector array
* @param [in] arr vector array to sort
* @param [in] low lower limit of window to partition
* @param [in] high upper limit of window to partition
* @returns sorted array vector
*/
template <typename T>
std::vector<T> quicksort(std::vector<T> arr, int32_t low, int32_t high) {
if (low >= high) {  // 1 or 0 elements
return arr;
}

int32_t i = 0, j = 0;

// i and j are passed as reference
partition3(&arr, low, high, &i, &j);

// Recur two halves
quicksort(&arr, low, i);
quicksort(&arr, j, high);

return arr;
}
}  // namespace sorting

/** Test function for integer type arrays */
static void test_int() {
std::cout << "\nTesting integer type arrays\n";

for (int num_tests = 1; num_tests < 21; num_tests++) {
size_t size = std::rand() % 500;
std::vector<int> arr(size);
for (auto &a : arr) {
a = std::rand() % 500 - 250;  // random numbers between -250, 249
}

std::cout << "Test " << num_tests << "\t Array size:" << size << "\t ";
std::vector<int> sorted = sorting::quicksort(arr, 0, size - 1);
if (size < 20) {
std::cout << "\t Sorted Array is:\n\t";
std::cout << sorted << "\n";
}
assert(std::is_sorted(std::begin(sorted), std::end(sorted)));
std::cout << "\t Passed\n";
}
}

/** Test function for double type arrays */
static void test_double() {
std::cout << "\nTesting Double type arrays\n";
for (int num_tests = 1; num_tests < 21; num_tests++) {
size_t size = std::rand() % 500;
std::vector<double> arr(size);
for (auto &a : arr) {
a = double(std::rand() % 500) -
250.f;   // random numbers between -250, 249
a /= 100.f;  // convert to -2.5 to 2.49
}

std::cout << "Test " << num_tests << "\t Array size:" << size << "\t ";
std::vector<double> sorted = sorting::quicksort(arr, 0, size - 1);
if (size < 20) {
std::cout << "\t Sorted Array is:\n\t";
std::cout << sorted << "\n";
}
assert(std::is_sorted(std::begin(sorted), std::end(sorted)));
std::cout << "\t Passed\n";
}
}

/** Driver program for above functions */
int main() {
std::srand(std::time(nullptr));
test_int();
test_double();
return 0;
}
``````