#include #include #include #include #include using namespace std; /* Code By: Zeke Williams Date: June 23, 2018 Description: A sorting method I haven't tried before. It takes 'partitions' of an array and sorts them by swapping. On average, a quicksort will take O(nlog n) comparisons to sort an array. For worst case, it is O(n^2) comparisons, but is very rare. I used the algorithm here: https://en.wikipedia.org/wiki/Quicksort to create it for C++. */ int partition(vector& A, int lo, int hi) { // The pivot is how other elements will be compared. // It is set to the elements at high index, which // will be the last element for the first call int pivot = A[hi]; // i is set to one spot below the low index. which // will be -1 for the first call int i = lo - 1; // For all of the numbers between the low and hight index, // lo included, high not included. // The first call, this is 0 to (A.size() - 2), // or the second to last element: for (int j = lo; j <= hi - 1; ++j) { // If the element at j in A is less than the pivot element: if (A[j] < pivot) { // increment i. For first call, -1 to 0 ++i; // Then swap the element at j with element at i if // i isn't equal to j (element swaps with itself) if (i != j) { int temp = A[j]; A[j] = A[i]; A[i] = temp; } } // basically i is counting the times A[j] is less than the pivot // while j increments for every element. // This can lead to i and j being equal, if the first element // is less than the pivot element, and the next elements // continue to be less than the pivot (if so, high index element is the // greatest element in the array) } // When done looping through the range of lo to hi - 1, // swap the element at i + 1 with the element at high index. // i incremented depending on how many elements within the range // were higher than the pivot. // if high index element was the greatest element, i would be // hi - 1, i + 1 would be the high index, which means A[i + 1] would // be equal to the pivot if (i + 1 != hi) { int temp2 = A[i + 1]; A[i + 1] = A[hi]; A[hi] = temp2; } // return i. If pivot was greatest element, it returns what hi was // for first call, this is the last element index (size - 1) return i + 1; } void quickSort(vector& A, int lo, int hi) { // only if the low index is, in fact, lower: if (lo < hi) { // p is set to the index of the partition. // It will be set depending on how many elements between lo and hi // were greater than the element at the hi index. // If the element at hi was the greatest, p is set to the the value // of hi. int p = partition(A, lo, hi); // call itself with new partition index for both the lo and hi // indeces. A new partition is only sorted when the lo argument // is in fact less than the high, so quicksort will only call // partition() when this is true quickSort(A, lo, p - 1); quickSort(A, p + 1, hi); } } int main() { srand(static_cast(time(nullptr))); vector store; int i; for (i = 0; i < 25; ++i) { int r = rand() % 100; store.push_back(r); } cout << "Vector before quicksort: " << endl; for (i = 0; i < store.size(); ++i) { cout << store[i] << " "; } cout << endl << endl; quickSort(store, 0, store.size() - 1); cout << "Vector after quicksort: " << endl; for (i = 0; i < store.size(); ++i) { cout << store[i] << " "; } cout << endl; return 0; }

Quicksort Attempt [C++]