Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2020
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4.  
  5. template <typename T>
  6. std::ostream& operator << (std::ostream& out, const std::vector<T>& vec) {
  7.     if (vec.empty()) {
  8.         return out << "[]";
  9.     }
  10.  
  11.     out << '[';
  12.  
  13.     auto begin = vec.cbegin();
  14.     auto end   = vec.cend() - 1;
  15.  
  16.     while (begin != end) {
  17.         out << *begin << ", ";
  18.         ++begin;
  19.     }
  20.  
  21.     return out << *end << ']';
  22. }
  23.  
  24. void bubble_sort(std::vector<int>& vec) {
  25.     bool was_sorted = false;
  26.     for (int i = 0; i < vec.size() && !was_sorted; i++) {
  27.         was_sorted = true;
  28.         for (int j = 0; j < vec.size() - 1 - i; j++) {
  29.             if (vec[j + 1] < vec[j]) {
  30.                 std::swap(vec[j], vec[j + 1]);
  31.                 was_sorted = false;
  32.             }
  33.         }
  34.     }
  35. }
  36.  
  37. void selection_sort(std::vector<int>& vec) {
  38.     for (int i = 0; i < vec.size(); i++) {
  39.         auto min_pos = std::min_element(vec.begin() + i, vec.end());
  40.         if (*min_pos < vec[i]) {
  41.             std::swap(vec[i], *min_pos);
  42.         }
  43.     }
  44. }
  45.  
  46. void insertion_sort(std::vector<int>& vec) {
  47.     if (vec.size() <= 1) return;
  48.  
  49.     for (int i = 1; i < vec.size(); i++) {
  50.         for (int j = i; j > 0 && vec[j - 1] > vec[j]; j--) {
  51.             std::swap(vec[j - 1], vec[j]);
  52.         }
  53.     }
  54. }
  55.  
  56. int main() {
  57.     /**
  58.      *  QuickSort, MergeSort, BucketSort, IntroSort, BubbleSort,
  59.      *  HeapSort, SelectionSort, InsertionSort, CountingSort, RadixSort
  60.      *  TimSort, ShakerSort, ...
  61.      */
  62.  
  63.     /**
  64.      *  BubbleSort      [x] [x]
  65.      *  SelectionSort   [x] [x]
  66.      *  InsertionSort   [x] [x]
  67.      *  MergeSort       [ ] [ ]
  68.      *  HeapSort        [ ] [ ]
  69.      *  QuickSort       [x] [ ]
  70.      */
  71.  
  72.     /**
  73.      *  O(n^2):
  74.      *      SelectionSort
  75.      *      BubbleSort
  76.      *      InsertionSort
  77.      *  O(n*log_n):
  78.      *      QuickSort
  79.      */
  80.  
  81.     std::vector<int> sample = {5, 0, 19, 9, 22, 18, 3, 1, 7};
  82.     std::vector<int> to_sort = sample;
  83.  
  84.     std::cout << to_sort << '\n';
  85.     bubble_sort(to_sort);
  86.     std::cout << to_sort << '\n';
  87.     to_sort = sample;
  88.     std::cout << '\n';
  89.  
  90.     std::cout << to_sort << '\n';
  91.     selection_sort(to_sort);
  92.     std::cout << to_sort << '\n';
  93.     to_sort = sample;
  94.     std::cout << '\n';
  95.  
  96.     std::cout << to_sort << '\n';
  97.     insertion_sort(to_sort);
  98.     std::cout << to_sort << '\n';
  99.     to_sort = sample;
  100.     std::cout << '\n';
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement