Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Quick sort implementation in C++ More...
#include <algorithm>
#include <cassert>
#include <ctime>
#include <iostream>
#include <vector>
Namespaces | |
namespace | sorting |
for working with vectors | |
namespace | quick_sort |
Functions for the Quick sort implementation in C++. | |
Functions | |
template<typename T > | |
int | sorting::quick_sort::partition (std::vector< T > *arr, const int &low, const int &high) |
Sorts the array taking the last element as pivot. | |
template<typename T > | |
void | sorting::quick_sort::quick_sort (std::vector< T > *arr, const int &low, const int &high) |
the main function that implements Quick Sort. | |
template<typename T > | |
std::vector< T > | sorting::quick_sort::quick_sort (std::vector< T > arr, const int &low, const int &high) |
the main function that implements Quick Sort. | |
template<typename T > | |
void | sorting::quick_sort::show (const std::vector< T > &arr, const int &size) |
Utility function to print the array contents. | |
static void | tests () |
Self-test implementations. | |
int | main () |
Main function. | |
Quick sort implementation in C++
Quick Sort is a divide and conquer algorithm. It picks an element as pivot and partition the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
1. Always pick the first element as pivot 2. Always pick the last element as pivot (implemented below) 3. Pick a random element as pivot 4. Pick median as pivot The key process in quickSort is partition(). Target of partition is, given an array and an element x(say) of array as pivot, put x at it's correct position in sorted array and put all smaller elements (samller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time
int main | ( | void | ) |
Main function.
int sorting::quick_sort::partition | ( | std::vector< T > * | arr, |
const int & | low, | ||
const int & | high ) |
Sorts the array taking the last element as pivot.
This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot
T | array type |
arr | the array with contents given by the user |
low | first point of the array (starting index) |
high | last point of the array (ending index) |
void sorting::quick_sort::quick_sort | ( | std::vector< T > * | arr, |
const int & | low, | ||
const int & | high ) |
the main function that implements Quick Sort.
Void function used in T (array type) function, which then can be used as self-tests or other functionalities.
T | array type |
arr | array to be sorted |
low | starting index |
high | ending index |
std::vector< T > sorting::quick_sort::quick_sort | ( | std::vector< T > | arr, |
const int & | low, | ||
const int & | high ) |
the main function that implements Quick Sort.
T (array type) function which calls the void function. Can be used for self-tests and other functionalities.
T | array type |
arr | array to be sorted |
low | starting index |
high | ending index |
void sorting::quick_sort::show | ( | const std::vector< T > & | arr, |
const int & | size ) |
|
static |
Self-test implementations.