/****************************************************************************** * This program demonstrates the Quicksort. * * Copyright © 2021 Richard Lesh. All rights reserved. *****************************************************************************/ #include "Utils.hpp" #include #include #include #include #include using namespace std; int partition(vector &list, int low, int high) noexcept { int const pivot = list[(high + low) / 2]; int i = low - 1; int j = high + 1; while (true) { do { ++i; } while (list[i] < pivot); do { --j; } while (list[j] > pivot); if (i >= j) { return j; } int const temp = list[j]; list[j] = list[i]; list[i] = temp; } } void quicksort0(vector &list, int low, int high) noexcept { if (low < high) { int const p = partition(list, low, high); quicksort0(list, low, p); quicksort0(list, p + 1, high); } } void quicksort(vector &list) noexcept { quicksort0(list, 0, list.size() - 1); } int main(int argc, char **argv) { if (argc != 3) { cout << "Syntax: " << argv[0] << " list_size max_int" << endl; exit(1); } int const listSize = Utils::stoiWithDefault(string(argv[1]), 10); int const maxInt = Utils::stoiWithDefault(string(argv[2]), 100); vector listToSort = {}; srand(time(0)); cout << "Random List" << endl; for (int i = 0; i < listSize; ++i) { Utils::push(listToSort, int(maxInt * (rand()/(RAND_MAX + 1.0)))); } cout << Utils::to_string(listToSort) << endl; quicksort(listToSort); cout << "Sorted List" << endl; cout << Utils::to_string(listToSort) << endl; return 0; }