JustAnotherCatgirl

Slow sort

May 31st, 2023
167
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #ifndef SLOW_SORT_JUSTANOTHERCATGIRL
  2. #define SLOW_SORT_JUSTANOTHERCATGIRL
  3.  
  4. #include <concepts>
  5. #include <iostream>
  6. #include <iterator>
  7. #include <vector>
  8. #include <utility>
  9.  
  10. namespace slow_sort
  11. {
  12.  
  13. //for print function
  14. template <typename container>
  15. concept iterable = requires(container c)
  16. {
  17.     c.begin();
  18.     c.end();
  19. };
  20.  
  21. //checks whether comp function passed to sorting is valid
  22. template <typename func, typename iter>
  23. concept suiting_compare =
  24. std::invocable<func,
  25.     typename std::iterator_traits<iter>::value_type,
  26.     typename std::iterator_traits<iter>::value_type>;
  27.  
  28. //print with range-based loop
  29. template <iterable cont>
  30. void print(const cont& c)
  31. {
  32.     for (const auto& x : c) std::cout << x << '\n';
  33.     std::cout.put('\n');
  34. }
  35.  
  36. //print with iterators
  37. template <typename iter_type>
  38. void print(iter_type b, iter_type e)
  39. {
  40.     for (; b <= e; ++b) std::cout << *b << '\n';
  41.     std::cout.put('\n');
  42. }
  43.  
  44. //the slow sort algorithm
  45. template <std::random_access_iterator RAIter, typename lambda>
  46. void slow_sort(RAIter begin, RAIter end, lambda comp)
  47.     requires suiting_compare<lambda, RAIter>
  48. {
  49.     if (begin >= end) return;
  50.  
  51.     auto middle = begin + (std::distance(begin, end) / 2);
  52.     slow_sort(begin, middle, comp);
  53.     slow_sort(middle + 1, end, comp);
  54.  
  55.     if (comp(*end, *middle))
  56.         std::iter_swap(middle, end);
  57.  
  58.     slow_sort(begin, end - 1, comp);
  59.  
  60. }
  61.  
  62. //sorting algorithm with default comparison
  63. template <std::random_access_iterator RAIter>
  64. void slow_sort(RAIter begin, RAIter end)
  65. {
  66.     using value_type = typename std::iterator_traits<RAIter>::value_type;
  67.     slow_sort(begin, end, [](value_type a, value_type b) -> bool {return a < b; });
  68. }
  69.  
  70. } //slow_sort
  71.  
  72. #endif //SLOW_SORT_JUSTANOTHERCATGIRL
Advertisement
Add Comment
Please, Sign In to add comment