Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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

 sorting
 Sorting algorithms.
 

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

183  {
184  std::srand(std::time(nullptr));
185  test_int();
186  test_double();
187  return 0;
188 }
Here is the call graph for this function:

◆ test_double()

static void test_double ( )
static

Test function for double type arrays

160  {
161  std::cout << "\nTesting Double type arrays\n";
162  for (int num_tests = 1; num_tests < 21; num_tests++) {
163  size_t size = std::rand() % 500;
164  std::vector<double> arr(size);
165  for (auto &a : arr) {
166  a = double(std::rand() % 500) -
167  250.f; // random numbers between -250, 249
168  a /= 100.f; // convert to -2.5 to 2.49
169  }
170 
171  std::cout << "Test " << num_tests << "\t Array size:" << size << "\t ";
172  std::vector<double> sorted = sorting::quicksort(arr, 0, size - 1);
173  if (size < 20) {
174  std::cout << "\t Sorted Array is:\n\t";
175  std::cout << sorted << "\n";
176  }
177  assert(std::is_sorted(std::begin(sorted), std::end(sorted)));
178  std::cout << "\t Passed\n";
179  }
180 }

◆ test_int()

static void test_int ( )
static

Test function for integer type arrays

138  {
139  std::cout << "\nTesting integer type arrays\n";
140 
141  for (int num_tests = 1; num_tests < 21; num_tests++) {
142  size_t size = std::rand() % 500;
143  std::vector<int> arr(size);
144  for (auto &a : arr) {
145  a = std::rand() % 500 - 250; // random numbers between -250, 249
146  }
147 
148  std::cout << "Test " << num_tests << "\t Array size:" << size << "\t ";
149  std::vector<int> sorted = sorting::quicksort(arr, 0, size - 1);
150  if (size < 20) {
151  std::cout << "\t Sorted Array is:\n\t";
152  std::cout << sorted << "\n";
153  }
154  assert(std::is_sorted(std::begin(sorted), std::end(sorted)));
155  std::cout << "\t Passed\n";
156  }
157 }
std::srand
T srand(T... args)
std::vector< double >
test_double
static void test_double()
Definition: quick_sort_3.cpp:160
std::is_sorted
T is_sorted(T... args)
sorting::quicksort
void quicksort(std::vector< T > *arr, int32_t low, int32_t high)
Definition: quick_sort_3.cpp:94
std::cout
test_int
static void test_int()
Definition: quick_sort_3.cpp:138
std::rand
T rand(T... args)
std::begin
T begin(T... args)
std::time
T time(T... args)
std::end
T end(T... args)