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/random_pivot_quick_sort.cpp at master · https-hari/C-Plus-Plus Expand file tree/ Copy pathrandom_pivot_quick_sort.cppMore file actions 337 lines (303 loc) · 11.6 KB / Copy pathrandom_pivot_quick_sort.cppFile metadata and controls337 lines (303 loc) · 11.6 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 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 /** * @file * @brief Implementation of the [Random Pivot Quick * Sort](https://www.sanfoundry.com/cpp-program-implement-quick-sort-using-randomisation) * algorithm. * @details * * A random pivot quick sort algorithm is pretty much same as quick * sort with a difference of having a logic of selecting next pivot element from * the input array. * * Where in quick sort is fast, but still can give you the time * complexity of O(n^2) in worst case. * * To avoid hitting the time complexity of O(n^2), we use the logic * of randomize the selection process of pivot element. * * ### Logic * * The logic is pretty simple, the only change is in the * partitioning algorithm, which is selecting the pivot element. * * Instead of selecting the last or the first element from array * for pivot we use a random index to select pivot element. * * This avoids hitting the O(n^2) time complexity in practical * use cases. * * ### Partition Logic * * Partitions are done such as numbers lower than the "pivot" * element is arranged on the left side of the "pivot", and number larger than * the "pivot" element are arranged on the right part of the array. * * ### Algorithm * * Select the pivot element randomly using getRandomIndex() function * from this namespace. * * Initialize the pInd (partition index) from the start of the * array. * * Loop through the array from start to less than end. (from start * to < end). (Inside the loop) :- * * Check if the current element (arr[i]) is less than the * pivot element in each iteration. * * If current element in the iteration is less than the * pivot element, then swap the elements at current index (i) and partition * index (pInd) and increment the partition index by one. * * At the end of the loop, swap the pivot element with partition * index element. * * Return the partition index from the function. * * @author [Nitin Sharma](https://github.com/foo290) */ #include <algorithm> /// for std::is_sorted(), std::swap() #include <array> /// for std::array #include <cassert> /// for assert #include <ctime> /// for initializing random number generator #include <iostream> /// for IO operations #include <tuple> /// for returning multiple values form a function at once /** * @namespace sorting * @brief Sorting algorithms */ namespace sorting { /** * @brief Functions for the [Random Pivot Quick * Sort](https://www.sanfoundry.com/cpp-program-implement-quick-sort-using-randomisation) * implementation * @namespace random_pivot_quick_sort */ namespace random_pivot_quick_sort { /** * @brief Utility function to print the array * @tparam T size of the array * @param arr array used to print its content * @returns void * */ template <size_t T> void showArray(std::array<int64_t, T> arr) { for (int64_t i = 0; i < arr.size(); i++) { std::cout << arr[i] << " "; } std::cout << std::endl; } /** * @brief Takes the start and end indices of an array and returns a random * int64_teger between the range of those two for selecting pivot element. * * @param start The starting index. * @param end The ending index. * @returns int64_t A random number between start and end index. * */ int64_t getRandomIndex(int64_t start, int64_t end) { srand(time(nullptr)); // Initialize random number generator. int64_t randomPivotIndex = start + rand() % (end - start + 1); return randomPivotIndex; } /** * @brief A partition function which handles the partition logic of quick sort. * @tparam size size of the array to be passed as argument. * @param start The start index of the passed array * @param end The ending index of the passed array * @returns std::tuple<int64_t , std::array<int64_t , size>> A tuple of pivot * index and pivot sorted array. */ template <size_t size> std::tuple<int64_t, std::array<int64_t, size>> partition( std::array<int64_t, size> arr, int64_t start, int64_t end) { int64_t pivot = arr[end]; // Randomly selected element will be here from // caller function (quickSortRP()). int64_t pInd = start; for (int64_t i = start; i < end; i++) { if (arr[i] <= pivot) { std::swap(arr[i], arr[pInd]); // swapping the elements from current // index to pInd. pInd++; } } std::swap(arr[pInd], arr[end]); // swapping the pivot element to its sorted position return std::make_tuple(pInd, arr); } /** * @brief Random pivot quick sort function. This function is the starting point * of the algorithm. * @tparam size size of the array to be passed as argument. * @param start The start index of the passed array * @param end The ending index of the passed array * @returns std::array<int64_t , size> A fully sorted array in ascending order. */ template <size_t size> std::array<int64_t, size> quickSortRP(std::array<int64_t, size> arr, int64_t start, int64_t end) { if (start < end) { int64_t randomIndex = getRandomIndex(start, end); // switching the pivot with right most bound. std::swap(arr[end], arr[randomIndex]); int64_t pivotIndex = 0; // getting pivot index and pivot sorted array. std::tie(pivotIndex, arr) = partition(arr, start, end); // Recursively calling std::array<int64_t, arr.size()> rightSortingLeft = quickSortRP(arr, start, pivotIndex - 1); std::array<int64_t, arr.size()> full_sorted = quickSortRP(rightSortingLeft, pivotIndex + 1, end); arr = full_sorted; } return arr; } /** * @brief A function utility to generate unsorted array of given size and range. * @tparam size Size of the output array. * @param from Stating of the range. * @param to Ending of the range. * @returns std::array<int64_t , size> Unsorted array of specified size. * */ template <size_t size> std::array<int64_t, size> generateUnsortedArray(int64_t from, int64_t to) { srand(time(nullptr)); std::array<int64_t, size> unsortedArray{}; assert(from < to); int64_t i = 0; while (i < size) { int64_t randomNum = from + rand() % (to - from + 1); if (randomNum) { unsortedArray[i] = randomNum; i++; } } return unsortedArray; } } // namespace random_pivot_quick_sort } // namespace sorting /** * @brief a class containing the necessary test cases */ class TestCases { private: /** * @brief A function to print64_t given message on console. * @tparam T Type of the given message. * @returns void * */ template <typename T> void log(T msg) { // It's just to avoid writing cout and endl std::cout << "[TESTS] : ---> " << msg << std::endl; } public: /** * @brief Executes test cases * @returns void * */ void runTests() { log("Running Tests..."); testCase_1(); testCase_2(); testCase_3(); log("Test Cases over!"); std::cout << std::endl; } /** * @brief A test case with single input * @returns void * */ void testCase_1() { const int64_t inputSize = 1; log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" "~"); log("This is test case 1 for Random Pivot Quick Sort Algorithm : "); log("Description:"); log(" EDGE CASE : Only contains one element"); std::array<int64_t, inputSize> unsorted_arr{2}; int64_t start = 0; int64_t end = unsorted_arr.size() - 1; // length - 1 log("Running algorithm of data of length 50 ..."); std::array<int64_t, unsorted_arr.size()> sorted_arr = sorting::random_pivot_quick_sort::quickSortRP(unsorted_arr, start, end); log("Algorithm finished!"); log("Checking assert expression..."); assert(std::is_sorted(sorted_arr.begin(), sorted_arr.end())); log("Assertion check passed!"); log("[PASS] : TEST CASE 1 PASS!"); log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" "~"); } /** * @brief A test case with input array of length 500 * @returns void * */ void testCase_2() { const int64_t inputSize = 500; log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" "~"); log("Description:"); log(" BIG INPUT : Contains 500 elements and repeated elements"); log("This is test case 2 for Random Pivot Quick Sort Algorithm : "); std::array<int64_t, inputSize> unsorted_arr = sorting::random_pivot_quick_sort::generateUnsortedArray<inputSize>( 1, 10000); int64_t start = 0; int64_t end = unsorted_arr.size() - 1; // length - 1 log("Running algorithm of data of length 500 ..."); std::array<int64_t, unsorted_arr.size()> sorted_arr = sorting::random_pivot_quick_sort::quickSortRP(unsorted_arr, start, end); log("Algorithm finished!"); log("Checking assert expression..."); assert(std::is_sorted(sorted_arr.begin(), sorted_arr.end())); log("Assertion check passed!"); log("[PASS] : TEST CASE 2 PASS!"); log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" "~"); } /** * @brief A test case with array of length 1000. * @returns void * */ void testCase_3() { const int64_t inputSize = 1000; log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" "~"); log("This is test case 3 for Random Pivot Quick Sort Algorithm : "); log("Description:"); log(" LARGE INPUT : Contains 1000 elements and repeated elements"); std::array<int64_t, inputSize> unsorted_arr = sorting::random_pivot_quick_sort::generateUnsortedArray<inputSize>( 1, 10000); int64_t start = 0; int64_t end = unsorted_arr.size() - 1; // length - 1 log("Running algorithm..."); std::array<int64_t, unsorted_arr.size()> sorted_arr = sorting::random_pivot_quick_sort::quickSortRP(unsorted_arr, start, end); log("Algorithm finished!"); log("Checking assert expression..."); assert(std::is_sorted(sorted_arr.begin(), sorted_arr.end())); log("Assertion check passed!"); log("[PASS] : TEST CASE 3 PASS!"); log("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" "~"); } }; /** * @brief Self-test implementations * @returns void */ static void test() { TestCases tc = TestCases(); tc.runTests(); } /** * @brief Main function * @returns 0 on exit */ int main() { test(); // Executes various test cases. const int64_t inputSize = 10; std::array<int64_t, inputSize> unsorted_array = sorting::random_pivot_quick_sort::generateUnsortedArray<inputSize>( 50, 1000); std::cout << "Unsorted array is : " << std::endl; sorting::random_pivot_quick_sort::showArray(unsorted_array); std::array<int64_t, inputSize> sorted_array = sorting::random_pivot_quick_sort::quickSortRP( unsorted_array, 0, unsorted_array.size() - 1); std::cout << "Sorted array is : " << std::endl; sorting::random_pivot_quick_sort::showArray(sorted_array); 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. |