GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — C-Plus-Plus/sorting/quick_sort_iterative.cpp at master · https-hari/C-Plus-Plus Expand file tree/ Copy pathquick_sort_iterative.cppMore file actions 132 lines (118 loc) · 3.25 KB / Copy pathquick_sort_iterative.cppFile metadata and controls132 lines (118 loc) · 3.25 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 /** * @file * @brief Quick Sort without recursion. This method uses the stack instead. * Both recursive and iterative implementations have O(n log n) best case * and O(n^2) worst case. * @details * https://stackoverflow.com/questions/12553238/quicksort-iterative-or-recursive * https://en.wikipedia.org/wiki/Quicksort * https://www.geeksforgeeks.org/iterative-quick-sort/ * @author [Sebe324](https://github.com/sebe324) */ #include <iostream> /// for std::cout #include <vector> /// for std::vector #include <stack> /// for std::stack #include <algorithm> /// for std::is_sorted #include <cassert> /// for assert /** * @namespace sorting * @brief Sorting algorithms */ namespace sorting { /** * @brief The partition function sorts the array from * start to end and uses the last element as the pivot. * @param arr the array to be sorted * @param start starting index * @param end ending index * @return int next index of the pivot */ int partition(std::vector<int> &arr, int start, int end) { int pivot = arr[end]; int index = start - 1; for (int j = start; j < end; j++) { if (arr[j] <= pivot) { std::swap(arr[++index], arr[j]); } } std::swap(arr[index + 1], arr[end]); return index + 1; } /** * @brief The main sorting function * @details The iterative quick sort uses * the stack instead of recursion for saving * and restoring the environment between calls. * It does not need the end and start params, because * it is not recursive. * @param arr array to be sorted * @return void */ void iterativeQuickSort(std::vector<int> &arr) { std::stack<int> stack; int start = 0; int end = arr.size()-1; stack.push(start); stack.push(end); while(!stack.empty()) { end = stack.top(); stack.pop(); start = stack.top(); stack.pop(); int pivotIndex = partition(arr,start,end); if(pivotIndex -1 > start) { stack.push(start); stack.push(pivotIndex-1); } if(pivotIndex+1<end) { stack.push(pivotIndex+1); stack.push(end); } } } } // namespace sorting /** * @brief Self-test implementations * @returns void */ void tests() { //TEST 1 - Positive numbers std::vector<int> case1={100,534,1000000,553,10,61,2000,238,2756,9,12,56,30}; std::cout<<"TEST 1\n"; std::cout<<"Before: \n"; for(auto x : case1) std::cout<<x<<","; std::cout<<"\n"; sorting::iterativeQuickSort(case1); assert(std::is_sorted(std::begin(case1),std::end(case1))); std::cout<<"Test 1 succesful!\n"; std::cout<<"After: \n"; for(auto x : case1) std::cout<<x<<","; std::cout<<"\n"; //TEST 2 - Negative numbers std::vector<int> case2={-10,-2,-5,-2,-3746,-785,-123, -452, -32456}; std::cout<<"TEST 2\n"; std::cout<<"Before: \n"; for(auto x : case2) std::cout<<x<<","; std::cout<<"\n"; sorting::iterativeQuickSort(case2); assert(std::is_sorted(std::begin(case2),std::end(case2))); std::cout<<"Test 2 succesful!\n"; std::cout<<"After: \n"; for(auto x : case2) std::cout<<x<<","; std::cout<<"\n"; } /** * @brief Main function * @returns 0 on exit */ int main() { tests(); // run self test implementation return 0; } |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |