quick_sort.cpp File Reference

Quick sort implementation in C++ More...

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <ctime>
#include <iostream>
#include <vector>

Include dependency graph for quick_sort.cpp:

Go to the source code of this file.

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.

Detailed Description

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

Author

David Leal

popoapp

Definition in file quick_sort.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 213 of file quick_sort.cpp.

           {
    int choice = 0;
 
    std::cout << "\tAvailable modes\t\n\n";
    std::cout << "1. Self-tests mode\n2. Interactive mode";
 
    std::cout << "\nChoose a mode: ";
    std::cin >> choice;
    std::cout << "\n";
 
    while ((choice != 1) && (choice != 2)) {
        std::cout << "Invalid option. Choose between the valid modes: ";
        std::cin >> choice;
    }
 
    if (choice == 1) {
        std::srand(std::time(nullptr));
        tests();  // run self-test implementations
    } else if (choice == 2) {
        int size = 0;
        std::cout << "\nEnter the number of elements: ";
 
        std::cin >> size;
        std::vector<float> arr(size);
 
        std::cout
            << "\nEnter the unsorted elements (can be negative/decimal): ";
 
        for (int i = 0; i < size; ++i) {
            std::cout << "\n";
            std::cin >> arr[i];
        }
        sorting::quick_sort::quick_sort(&arr, 0, size - 1);
        std::cout << "\nSorted array: \n";
        sorting::quick_sort::show(arr, size);
    }
    return 0;
}

partition()

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.

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

Template Parameters

T	array type

Parameters

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)

Returns

index of the smaller element

Time Complexity

best case, average Case: O(nlog(n)) Worst Case: O(n^2) (Worst case occur when the partition is consistently unbalanced.)

Space Complexity

average Case: O(log(n)) Worst Case: O(n)
It's space complexity is due to the recursive function calls and partitioning process.

Definition at line 70 of file quick_sort.cpp.

                                                                  {
    T pivot = (*arr)[high];  // taking the last element as pivot
    int i = (low - 1);       // Index of smaller element
 
    for (int j = low; j < high; j++) {
        // If current element is smaller than or
        // equal to pivot
        if ((*arr)[j] <= pivot) {
            i++;  // increment index of smaller element
            std::swap((*arr)[i], (*arr)[j]);
        }
    }
 
    std::swap((*arr)[i + 1], (*arr)[high]);
    return (i + 1);
}

quick_sort() [1/2]

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.

Void function used in T (array type) function, which then can be used as self-tests or other functionalities.

Template Parameters

T	array type

Parameters

arr	array to be sorted
low	starting index
high	ending index

Definition at line 98 of file quick_sort.cpp.

                                                                    {
    if (low < high) {
        int p = partition(arr, low, high);
 
        quick_sort(arr, low, p - 1);
        quick_sort(arr, p + 1, high);
    }
}

quick_sort() [2/2]

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.

T (array type) function which calls the void function. Can be used for self-tests and other functionalities.

Template Parameters

T	array type

Parameters

arr	array to be sorted
low	starting index
high	ending index

Definition at line 118 of file quick_sort.cpp.

                                                                           {
    if (low < high) {
        int p = partition(&arr, low, high);
 
        quick_sort(&arr, low, p - 1);
        quick_sort(&arr, p + 1, high);
    }
    return arr;
}

show()

template<typename T>

void sorting::quick_sort::show	(	const std::vector< T > &	arr,
		const int &	size )

Utility function to print the array contents.

Parameters

arr	the array to be printed
size	size of the given array

Returns

void

Definition at line 135 of file quick_sort.cpp.

                                                    {
    for (int i = 0; i < size; i++) std::cout << arr[i] << " ";
    std::cout << "\n";
}

tests()

static void tests ( )

static

Self-test implementations.

Returns

void

Definition at line 147 of file quick_sort.cpp.

                    {
    // 1st test (normal numbers)
    std::vector<uint64_t> arr = {5, 3, 8, 12, 14, 16, 28, 96, 2, 5977};
    std::vector<uint64_t> arr_sorted = sorting::quick_sort::quick_sort(
        arr, 0, int(std::end(arr) - std::begin(arr)) - 1);
 
    assert(std::is_sorted(std::begin(arr_sorted), std::end(arr_sorted)));
    std::cout << "\n1st test: passed!\n";
 
    // 2nd test (normal and negative numbers)
    std::vector<int64_t> arr2 = {9,    15,   28,   96,  500, -4, -58,
                                 -977, -238, -800, -21, -53, -55};
    std::vector<int64_t> arr_sorted2 = sorting::quick_sort::quick_sort(
        arr2, 0, std::end(arr2) - std::begin(arr2));
 
    assert(std::is_sorted(std::begin(arr_sorted2), std::end(arr_sorted2)));
    std::cout << "2nd test: passed!\n";
 
    // 3rd test (decimal and normal numbers)
    std::vector<double> arr3 = {29,  36,   1100, 0,      77,     1,
                                6.7, 8.97, 1.74, 950.10, -329.65};
    std::vector<double> arr_sorted3 = sorting::quick_sort::quick_sort(
        arr3, 0, int(std::end(arr3) - std::begin(arr3)) - 1);
 
    assert(std::is_sorted(std::begin(arr_sorted3), std::end(arr_sorted3)));
    std::cout << "3rd test: passed!\n";
 
    // 4th test (random decimal and negative numbers)
    size_t size = std::rand() % 750 + 100;
 
    std::vector<float> arr4(size);
    for (uint64_t i = 0; i < size; i++) {
        arr4[i] = static_cast<float>(std::rand()) /
                      static_cast<float>(RAND_MAX / 999.99 - 0.99) -
                  250;
    }
 
    std::vector<float> arr4_sorted = sorting::quick_sort::quick_sort(
        arr4, 0, int(std::end(arr4) - std::begin(arr4)) - 1);
    assert(std::is_sorted(std::begin(arr4_sorted), std::end(arr4_sorted)));
 
    std::cout << "4th test: passed!\n";
 
    // Printing all sorted arrays
    std::cout << "\n\tPrinting all sorted arrays:\t\n";
 
    std::cout << "1st array:\n";
    sorting::quick_sort::show(arr_sorted, std::end(arr) - std::begin(arr));
    std::cout << std::endl;
    std::cout << "2nd array:\n";
    sorting::quick_sort::show(arr_sorted2, std::end(arr2) - std::begin(arr2));
    std::cout << std::endl;
    std::cout << "3rd array:\n";
    sorting::quick_sort::show(arr_sorted3,
                              int(std::end(arr3) - std::begin(arr3)) - 1);
    std::cout << std::endl;
    std::cout << "Start: 4th array:\n\n";
    sorting::quick_sort::show(
        arr4_sorted, int(std::end(arr4_sorted) - std::begin(arr4_sorted)) - 1);
    std::cout << "\nEnd: 4th array.\n";
}