TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
quick_sort.cpp
Go to the documentation of this file.
1
26
27#include <algorithm>
28#include <cassert>
29#include <cstdint>
30#include <ctime>
31#include <iostream>
32#include <vector>
33
38namespace sorting {
44namespace quick_sort {
68
69template <typename T>
70int partition(std::vector<T> *arr, const int &low, const int &high) {
71 T pivot = (*arr)[high]; // taking the last element as pivot
72 int i = (low - 1); // Index of smaller element
73
74 for (int j = low; j < high; j++) {
75 // If current element is smaller than or
76 // equal to pivot
77 if ((*arr)[j] <= pivot) {
78 i++; // increment index of smaller element
79 std::swap((*arr)[i], (*arr)[j]);
80 }
81 }
82
83 std::swap((*arr)[i + 1], (*arr)[high]);
84 return (i + 1);
85}
86
97template <typename T>
98void quick_sort(std::vector<T> *arr, const int &low, const int &high) {
99 if (low < high) {
100 int p = partition(arr, low, high);
101
102 quick_sort(arr, low, p - 1);
103 quick_sort(arr, p + 1, high);
104 }
105}
106
117template <typename T>
118std::vector<T> quick_sort(std::vector<T> arr, const int &low, const int &high) {
119 if (low < high) {
120 int p = partition(&arr, low, high);
121
122 quick_sort(&arr, low, p - 1);
123 quick_sort(&arr, p + 1, high);
124 }
125 return arr;
126}
127
134template <typename T>
135void show(const std::vector<T> &arr, const int &size) {
136 for (int i = 0; i < size; i++) std::cout << arr[i] << " ";
137 std::cout << "\n";
138}
139
140} // namespace quick_sort
141} // namespace sorting
142
147static void tests() {
148 // 1st test (normal numbers)
149 std::vector<uint64_t> arr = {5, 3, 8, 12, 14, 16, 28, 96, 2, 5977};
150 std::vector<uint64_t> arr_sorted = sorting::quick_sort::quick_sort(
151 arr, 0, int(std::end(arr) - std::begin(arr)) - 1);
152
153 assert(std::is_sorted(std::begin(arr_sorted), std::end(arr_sorted)));
154 std::cout << "\n1st test: passed!\n";
155
156 // 2nd test (normal and negative numbers)
157 std::vector<int64_t> arr2 = {9, 15, 28, 96, 500, -4, -58,
158 -977, -238, -800, -21, -53, -55};
159 std::vector<int64_t> arr_sorted2 = sorting::quick_sort::quick_sort(
160 arr2, 0, std::end(arr2) - std::begin(arr2));
161
162 assert(std::is_sorted(std::begin(arr_sorted2), std::end(arr_sorted2)));
163 std::cout << "2nd test: passed!\n";
164
165 // 3rd test (decimal and normal numbers)
166 std::vector<double> arr3 = {29, 36, 1100, 0, 77, 1,
167 6.7, 8.97, 1.74, 950.10, -329.65};
168 std::vector<double> arr_sorted3 = sorting::quick_sort::quick_sort(
169 arr3, 0, int(std::end(arr3) - std::begin(arr3)) - 1);
170
171 assert(std::is_sorted(std::begin(arr_sorted3), std::end(arr_sorted3)));
172 std::cout << "3rd test: passed!\n";
173
174 // 4th test (random decimal and negative numbers)
175 size_t size = std::rand() % 750 + 100;
176
177 std::vector<float> arr4(size);
178 for (uint64_t i = 0; i < size; i++) {
179 arr4[i] = static_cast<float>(std::rand()) /
180 static_cast<float>(RAND_MAX / 999.99 - 0.99) -
181 250;
182 }
183
184 std::vector<float> arr4_sorted = sorting::quick_sort::quick_sort(
185 arr4, 0, int(std::end(arr4) - std::begin(arr4)) - 1);
186 assert(std::is_sorted(std::begin(arr4_sorted), std::end(arr4_sorted)));
187
188 std::cout << "4th test: passed!\n";
189
190 // Printing all sorted arrays
191 std::cout << "\n\tPrinting all sorted arrays:\t\n";
192
193 std::cout << "1st array:\n";
194 sorting::quick_sort::show(arr_sorted, std::end(arr) - std::begin(arr));
195 std::cout << std::endl;
196 std::cout << "2nd array:\n";
197 sorting::quick_sort::show(arr_sorted2, std::end(arr2) - std::begin(arr2));
198 std::cout << std::endl;
199 std::cout << "3rd array:\n";
200 sorting::quick_sort::show(arr_sorted3,
201 int(std::end(arr3) - std::begin(arr3)) - 1);
202 std::cout << std::endl;
203 std::cout << "Start: 4th array:\n\n";
205 arr4_sorted, int(std::end(arr4_sorted) - std::begin(arr4_sorted)) - 1);
206 std::cout << "\nEnd: 4th array.\n";
207}
208
213int main() {
214 int choice = 0;
215
216 std::cout << "\tAvailable modes\t\n\n";
217 std::cout << "1. Self-tests mode\n2. Interactive mode";
218
219 std::cout << "\nChoose a mode: ";
220 std::cin >> choice;
221 std::cout << "\n";
222
223 while ((choice != 1) && (choice != 2)) {
224 std::cout << "Invalid option. Choose between the valid modes: ";
225 std::cin >> choice;
226 }
227
228 if (choice == 1) {
229 std::srand(std::time(nullptr));
230 tests(); // run self-test implementations
231 } else if (choice == 2) {
232 int size = 0;
233 std::cout << "\nEnter the number of elements: ";
234
235 std::cin >> size;
236 std::vector<float> arr(size);
237
238 std::cout
239 << "\nEnter the unsorted elements (can be negative/decimal): ";
240
241 for (int i = 0; i < size; ++i) {
242 std::cout << "\n";
243 std::cin >> arr[i];
244 }
245 sorting::quick_sort::quick_sort(&arr, 0, size - 1);
246 std::cout << "\nSorted array: \n";
247 sorting::quick_sort::show(arr, size);
248 }
249 return 0;
250}
Functions for the Quick sort implementation in C++.
for working with vectors
int partition(std::vector< T > *arr, const int &low, const int &high)
Sorts the array taking the last element as pivot.
static void tests()
Self-test implementations.
void quick_sort(std::vector< T > *arr, const int &low, const int &high)
the main function that implements Quick Sort.
int main()
Main function.
void show(const std::vector< T > &arr, const int &size)
Utility function to print the array contents.