Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
quick_sort.cpp File Reference

Quick sort implementation in C++ More...

#include <algorithm>
#include <cassert>
#include <ctime>
#include <iostream>
#include <vector>
Include dependency graph for quick_sort.cpp:

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

Function Documentation

◆ main()

int main ( void )

Main function.

Returns
0 on exit
201 {
202 int choice = 0;
203
204 std::cout << "\tAvailable modes\t\n\n";
205 std::cout << "1. Self-tests mode\n2. Interactive mode";
206
207 std::cout << "\nChoose a mode: ";
208 std::cin >> choice;
209 std::cout << "\n";
210
211 while ((choice != 1) && (choice != 2)) {
212 std::cout << "Invalid option. Choose between the valid modes: ";
213 std::cin >> choice;
214 }
215
216 if (choice == 1) {
217 std::srand(std::time(nullptr));
218 tests(); // run self-test implementations
219 } else if (choice == 2) {
220 int size = 0;
221 std::cout << "\nEnter the number of elements: ";
222
223 std::cin >> size;
224 std::vector<float> arr(size);
225
227 << "\nEnter the unsorted elements (can be negative/decimal): ";
228
229 for (int i = 0; i < size; ++i) {
230 std::cout << "\n";
231 std::cin >> arr[i];
232 }
233 sorting::quick_sort::quick_sort(&arr, 0, size - 1);
234 std::cout << "\nSorted array: \n";
235 sorting::quick_sort::show(arr, size);
236 }
237 return 0;
238}
static void tests()
Self-test implementations.
Definition quick_sort.cpp:135
void quick_sort(std::vector< T > *arr, const int &low, const int &high)
the main function that implements Quick Sort.
Definition quick_sort.cpp:86
void show(const std::vector< T > &arr, const int &size)
Utility function to print the array contents.
Definition quick_sort.cpp:123
T srand(T... args)
T time(T... args)
Here is the call graph for this function:

◆ 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
Tarray type
Parameters
arrthe array with contents given by the user
lowfirst point of the array (starting index)
highlast point of the array (ending index)
Returns
index of the smaller element
58 {
59 T pivot = (*arr)[high]; // taking the last element as pivot
60 int i = (low - 1); // Index of smaller element
61
62 for (int j = low; j < high; j++) {
63 // If current element is smaller than or
64 // equal to pivot
65 if ((*arr)[j] <= pivot) {
66 i++; // increment index of smaller element
67 std::swap((*arr)[i], (*arr)[j]);
68 }
69 }
70
71 std::swap((*arr)[i + 1], (*arr)[high]);
72 return (i + 1);
73}
T swap(T... args)
Here is the call graph for this function:

◆ 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
Tarray type
Parameters
arrarray to be sorted
lowstarting index
highending index
86 {
87 if (low < high) {
88 int p = partition(arr, low, high);
89
90 quick_sort(arr, low, p - 1);
91 quick_sort(arr, p + 1, high);
92 }
93}
Functions for the Quick sort implementation in C++.
T partition(T... args)

◆ 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
Tarray type
Parameters
arrarray to be sorted
lowstarting index
highending index
106 {
107 if (low < high) {
108 int p = partition(&arr, low, high);
109
110 quick_sort(&arr, low, p - 1);
111 quick_sort(&arr, p + 1, high);
112 }
113 return arr;
114}

◆ 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
arrthe array to be printed
sizesize of the given array
Returns
void
123 {
124 for (int i = 0; i < size; i++) std::cout << arr[i] << " ";
125 std::cout << "\n";
126}

◆ tests()

static void tests ( )
static

Self-test implementations.

Returns
void
135 {
136 // 1st test (normal numbers)
137 std::vector<uint64_t> arr = {5, 3, 8, 12, 14, 16, 28, 96, 2, 5977};
139 arr, 0, int(std::end(arr) - std::begin(arr)) - 1);
140
141 assert(std::is_sorted(std::begin(arr_sorted), std::end(arr_sorted)));
142 std::cout << "\n1st test: passed!\n";
143
144 // 2nd test (normal and negative numbers)
145 std::vector<int64_t> arr2 = {9, 15, 28, 96, 500, -4, -58,
146 -977, -238, -800, -21, -53, -55};
148 arr2, 0, std::end(arr2) - std::begin(arr2));
149
150 assert(std::is_sorted(std::begin(arr_sorted2), std::end(arr_sorted2)));
151 std::cout << "2nd test: passed!\n";
152
153 // 3rd test (decimal and normal numbers)
154 std::vector<double> arr3 = {29, 36, 1100, 0, 77, 1,
155 6.7, 8.97, 1.74, 950.10, -329.65};
157 arr3, 0, int(std::end(arr3) - std::begin(arr3)) - 1);
158
159 assert(std::is_sorted(std::begin(arr_sorted3), std::end(arr_sorted3)));
160 std::cout << "3rd test: passed!\n";
161
162 // 4th test (random decimal and negative numbers)
163 size_t size = std::rand() % 750 + 100;
164
165 std::vector<float> arr4(size);
166 for (uint64_t i = 0; i < size; i++) {
167 arr4[i] = static_cast<float>(std::rand()) /
168 static_cast<float>(RAND_MAX / 999.99 - 0.99) -
169 250;
170 }
171
173 arr4, 0, int(std::end(arr4) - std::begin(arr4)) - 1);
174 assert(std::is_sorted(std::begin(arr4_sorted), std::end(arr4_sorted)));
175
176 std::cout << "4th test: passed!\n";
177
178 // Printing all sorted arrays
179 std::cout << "\n\tPrinting all sorted arrays:\t\n";
180
181 std::cout << "1st array:\n";
182 sorting::quick_sort::show(arr_sorted, std::end(arr) - std::begin(arr));
184 std::cout << "2nd array:\n";
185 sorting::quick_sort::show(arr_sorted2, std::end(arr2) - std::begin(arr2));
187 std::cout << "3rd array:\n";
188 sorting::quick_sort::show(arr_sorted3,
189 int(std::end(arr3) - std::begin(arr3)) - 1);
191 std::cout << "Start: 4th array:\n\n";
193 arr4_sorted, int(std::end(arr4_sorted) - std::begin(arr4_sorted)) - 1);
194 std::cout << "\nEnd: 4th array.\n";
195}
T begin(T... args)
T end(T... args)
T endl(T... args)
T is_sorted(T... args)
T rand(T... args)
Here is the call graph for this function: