![]() |
TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
|
Implementation of the Random Pivot Quick Sort algorithm. More...
#include <algorithm>
#include <array>
#include <cassert>
#include <ctime>
#include <iostream>
#include <tuple>
Go to the source code of this file.
Classes | |
class | TestCases |
class encapsulating the necessary test cases More... | |
Namespaces | |
namespace | sorting |
for working with vectors | |
namespace | random_pivot_quick_sort |
Functions for the Random Pivot Quick Sort implementation. | |
Functions | |
template<size_t T> | |
void | sorting::random_pivot_quick_sort::showArray (std::array< int64_t, T > arr) |
Utility function to print the array. | |
int64_t | sorting::random_pivot_quick_sort::getRandomIndex (int64_t start, int64_t end) |
Takes the start and end indices of an array and returns a random int64_teger between the range of those two for selecting pivot element. | |
template<size_t size> | |
std::tuple< int64_t, std::array< int64_t, size > > | sorting::random_pivot_quick_sort::partition (std::array< int64_t, size > arr, int64_t start, int64_t end) |
A partition function which handles the partition logic of quick sort. | |
template<size_t size> | |
std::array< int64_t, size > | sorting::random_pivot_quick_sort::quickSortRP (std::array< int64_t, size > arr, int64_t start, int64_t end) |
Random pivot quick sort function. This function is the starting point of the algorithm. | |
template<size_t size> | |
std::array< int64_t, size > | sorting::random_pivot_quick_sort::generateUnsortedArray (int64_t from, int64_t to) |
A function utility to generate unsorted array of given size and range. | |
static void | test () |
Self-test implementations. | |
int | main (int argc, char *argv[]) |
Main function. | |
Implementation of the Random Pivot Quick Sort algorithm.
### Logic * The logic is pretty simple, the only change is in thepartitioning algorithm, which is selecting the pivot element.
### Partition Logic * Partitions are done such as numbers lower than the "pivot"element is arranged on the left side of the "pivot", and number larger than the "pivot" element are arranged on the right part of the array.
### Algorithm * Select the pivot element randomly using getRandomIndex() functionfrom this namespace.
Initialize the pInd (partition index) from the start of the array.
Definition in file random_pivot_quick_sort.cpp.
std::array< int64_t, size > sorting::random_pivot_quick_sort::generateUnsortedArray | ( | int64_t | from, |
int64_t | to ) |
A function utility to generate unsorted array of given size and range.
size | Size of the output array. |
from | Stating of the range. |
to | Ending of the range. |
Definition at line 160 of file random_pivot_quick_sort.cpp.
int64_t sorting::random_pivot_quick_sort::getRandomIndex | ( | int64_t | start, |
int64_t | end ) |
Takes the start and end indices of an array and returns a random int64_teger between the range of those two for selecting pivot element.
start | The starting index. |
end | The ending index. |
Definition at line 88 of file random_pivot_quick_sort.cpp.
int main | ( | int | argc, |
char * | argv[] ) |
Main function.
argc | commandline argument count (ignored) |
argv | commandline array of arguments (ignored) |
Definition at line 323 of file random_pivot_quick_sort.cpp.
std::tuple< int64_t, std::array< int64_t, size > > sorting::random_pivot_quick_sort::partition | ( | std::array< int64_t, size > | arr, |
int64_t | start, | ||
int64_t | end ) |
A partition function which handles the partition logic of quick sort.
size | size of the array to be passed as argument. |
start | The start index of the passed array |
end | The ending index of the passed array |
Definition at line 103 of file random_pivot_quick_sort.cpp.
std::array< int64_t, size > sorting::random_pivot_quick_sort::quickSortRP | ( | std::array< int64_t, size > | arr, |
int64_t | start, | ||
int64_t | end ) |
Random pivot quick sort function. This function is the starting point of the algorithm.
size | size of the array to be passed as argument. |
start | The start index of the passed array |
end | The ending index of the passed array |
Definition at line 130 of file random_pivot_quick_sort.cpp.
void sorting::random_pivot_quick_sort::showArray | ( | std::array< int64_t, T > | arr | ) |
Utility function to print the array.
T | size of the array |
arr | array used to print its content |
Definition at line 73 of file random_pivot_quick_sort.cpp.
|
static |
Self-test implementations.
Definition at line 312 of file random_pivot_quick_sort.cpp.