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/dnf_sort.cpp at master · https-hari/C-Plus-Plus Expand file tree/ Copy pathdnf_sort.cppMore file actions 112 lines (105 loc) · 3.2 KB / Copy pathdnf_sort.cppFile metadata and controls112 lines (105 loc) · 3.2 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 /** * @file * @brief Implementation of the [DNF * sort](https://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/) * implementation * @details * C++ program to sort an array with 0, 1 and 2 in a single pass(DNF sort). * Since one traversal of the array is there hence it works in O(n) time * complexity. * @author [Sujal Gupta](https://github.com/heysujal) */ #include <algorithm> /// for std::is_sorted #include <cassert> /// for assert #include <cstdint> #include <iostream> /// for std::swap and io operations #include <vector> /// for std::vector /** * @namespace sorting * @breif Sorting algorithms */ namespace sorting { /** * @namespace dnf_sort * @brief Functions for the [DNF * sort](https://en.wikipedia.org/wiki/Dutch_national_flag_problem) * implementation */ namespace dnf_sort { /** * @brief The main function implements DNF sort * @tparam T type of array * @param a array to be sorted, * @param arr_size size of array * @returns void */ template <typename T> std::vector<T> dnfSort(const std::vector<T> &in_arr) { std::vector<T> arr(in_arr); uint64_t lo = 0; uint64_t hi = arr.size() - 1; uint64_t mid = 0; // Iterate till all the elements // are sorted while (mid <= hi) { switch (arr[mid]) { // If the element is 0 case 0: std::swap(arr[lo++], arr[mid++]); break; // If the element is 1 . case 1: mid++; break; // If the element is 2 case 2: std::swap(arr[mid], arr[hi--]); break; } } return arr; } } // namespace dnf_sort } // namespace sorting /** * @brief Self-test implementations * @returns void */ static void test() { // 1st test // [1, 0, 2, 1] return [0, 1, 1, 2] std::vector<uint64_t> array1 = {0, 1, 1, 2}; std::cout << "Test 1... "; std::vector<uint64_t> arr1 = sorting::dnf_sort::dnfSort(array1); assert(std::is_sorted(std::begin(arr1), std::end(arr1))); std::cout << "passed" << std::endl; // 2nd test // [1, 0, 0, 1, 1, 0, 2, 1] return [0, 0, 0, 1, 1, 1, 1, 2] std::vector<uint64_t> array2 = {1, 0, 0, 1, 1, 0, 2, 1}; std::cout << "Test 2... "; std::vector<uint64_t> arr2 = sorting::dnf_sort::dnfSort(array2); assert(std::is_sorted(std::begin(arr2), std::end(arr2))); std::cout << "passed" << std::endl; // 3rd test // [1, 1, 0, 0, 1, 2, 2, 0, 2, 1] return [0, 0, 0, 1, 1, 1, 1, 2, 2, 2] std::vector<uint64_t> array3 = {1, 1, 0, 0, 1, 2, 2, 0, 2, 1}; std::cout << "Test 3... "; std::vector<uint64_t> arr3 = sorting::dnf_sort::dnfSort(array3); assert(std::is_sorted(std::begin(arr3), std::end(arr3))); std::cout << "passed" << std::endl; // 4th test // [2, 2, 2, 0, 0, 1, 1] return [0, 0, 1, 1, 2, 2, 2] std::vector<uint64_t> array4 = {2, 2, 2, 0, 0, 1, 1}; std::cout << "Test 4... "; std::vector<uint64_t> arr4 = sorting::dnf_sort::dnfSort(array4); assert(std::is_sorted(std::begin(arr4), std::end(arr4))); std::cout << "passed" << std::endl; } /** * @brief Main function * @returns 0 on exit */ int main() { test(); // execute the test 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. |