sorts.cpp (3189B)
1 #include <array> 2 #include <vector> 3 #include <cstdlib> 4 #include <iostream> 5 #include <iomanip> 6 #include <span> 7 #include <numeric> 8 #include <string_view> 9 #include <algorithm> 10 11 template <typename T> 12 void bubble_sort(std::span<T> const& elements) 13 { 14 bool unsorted = true; 15 16 for (auto end = elements.end(); unsorted && end != elements.begin(); --end) 17 { 18 unsorted = false; 19 20 for (auto cur = elements.begin(); cur != end; ++cur) 21 if (auto next = cur + 1; *cur > *next) 22 { 23 std::swap(*cur, *next); 24 unsorted = true; 25 } 26 } 27 } 28 29 template <typename T> 30 void insertion_sort(std::span<T> const& elements) 31 { 32 for (auto it = elements.begin(); it != elements.end(); ++it) 33 for (auto cur = it; cur != elements.begin(); --cur) 34 if (auto next = cur - 1; *cur < *next) 35 std::swap(*cur, *next); 36 else 37 break; 38 } 39 40 template <typename T> 41 void selection_sort(std::span<T> const& elements) 42 { 43 for (auto it = elements.begin(); it != elements.end(); ++it) 44 if (auto next = std::min_element(it, elements.end()); it != next) 45 std::swap(*it, *next); 46 } 47 48 template <typename T> 49 struct reverse_wrapper 50 { 51 T& c_; 52 reverse_wrapper(T& c) : c_(c) {} 53 54 typename T::reverse_iterator begin() {return c_.rbegin();} 55 typename T::reverse_iterator end() {return c_.rend(); } 56 }; 57 58 template <typename T> 59 void radix_sort(std::span<T> const& elements) 60 { 61 std::vector<T> storage(elements.size()); 62 std::span<T> in = elements, out = storage; 63 64 constexpr unsigned z = 3; 65 constexpr unsigned radix = 1 << (1 << z); 66 constexpr unsigned mask = radix - 1; 67 unsigned passes = std::numeric_limits<T>::digits >> z; 68 unsigned shift = 0; 69 std::array<unsigned, radix> buckets = {}; 70 71 if (passes % 2) 72 { 73 std::copy(in.begin(), in.end(), out.begin()); 74 std::swap(in, out); 75 } 76 77 while (passes--) 78 { 79 for (unsigned i = 0; i < radix; ++i) 80 buckets[i] = std::count_if(in.begin(), in.end(), [i, shift](auto n) 81 { 82 return (n >> shift & mask) == i; 83 }); 84 85 std::partial_sum(buckets.begin(), buckets.end(), buckets.begin()); 86 87 for (auto n : reverse_wrapper(in)) 88 out[--buckets[n >> shift & mask]] = n; 89 90 std::swap(in, out); 91 shift += 1 << z; 92 } 93 } 94 95 using base_type = unsigned char; 96 using sort_fn_t = void (*)(std::span<base_type> const&); 97 using namespace std::literals; 98 99 struct 100 { 101 char option(void) const 102 { 103 return std::tolower(name[0]); 104 } 105 106 sort_fn_t fn; 107 char name[12]; 108 } const menu[] = 109 { 110 {bubble_sort, "Bubble"}, 111 {insertion_sort, "Insertion"}, 112 {radix_sort, "Radix"}, 113 {selection_sort, "Selection"}, 114 }; 115 116 [[ noreturn ]] 117 void usage(void) 118 { 119 std::cerr << "Usage:\n\tsorts OPTION\n\n"; 120 121 for (auto const& e : menu) 122 std::cerr << "\t-" << e.option() << '\t' << e.name << " sort\n"; 123 124 std::exit(1); 125 } 126 127 sort_fn_t get_sort_fn(std::string_view arg) 128 { 129 if (arg.size() != 2 || arg[0] != '-') 130 usage(); 131 132 for (auto const& e : menu) 133 if (arg[1] == e.option()) 134 return e.fn; 135 136 usage(); 137 } 138 139 int main(int argc, char* argv[]) 140 { 141 if (argc != 2) 142 usage(); 143 144 auto sort_fn = get_sort_fn(argv[1]); 145 146 std::array<base_type, 100> ints; 147 std::generate(ints.begin(), ints.end(), rand); 148 149 sort_fn(ints); 150 151 for (auto const& n : ints) 152 std::cout << std::setw(10) << +n << '\n'; 153 154 return !std::is_sorted(ints.begin(), ints.end()); 155 }