quick_sort_3.cpp File Reference

Implementation Details. More...

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

Include dependency graph for quick_sort_3.cpp:

Namespaces
namespace	sorting
	for working with vectors

Functions
template<typename T >
void	sorting::quicksort (std::vector< T > *arr, int32_t low, int32_t high)
template<typename T >
std::vector< T >	sorting::quicksort (std::vector< T > arr, int32_t low, int32_t high)
static void	test_int ()
static void	test_double ()
int	main ()

Detailed Description

Implementation 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

Krishna Vedala

Function Documentation

main()

int main

(

void

)

Driver program for above functions

           {
    std::srand(std::time(nullptr));
    test_int();
    test_double();
    return 0;
}

Here is the call graph for this function:

test_double()

static void test_double ( )

static

Test function for double type arrays

                          {
    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, int32_t(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";
    }
}

Here is the call graph for this function:

test_int()

static void test_int ( )

static

Test function for integer type arrays

                       {
    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, int32_t(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";
    }
}

Here is the call graph for this function: