ds-in-cpp/SortMerge.cc at main · sudonam/ds-in-cpp · GitHub

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
#include <algorithm>
#include <format>
#include <iostream>
#include <random>

#include "vector.hh"

template <typename compar>
struct MergeTD {
  static void sort(ns::vector<compar> &a) {
    ns::vector<compar> aux(a.size());
    sort(a, aux, 0, a.size() - 1);
  }

  static void sort(ns::vector<compar> &a, ns::vector<compar> &aux, int lo,
                   int hi) {
    if (hi <= lo) return;
    int mid{lo + (hi - lo) / 2};
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    merge0(a, aux, lo, mid, hi);
  }

  static void merge0(ns::vector<compar> &a, ns::vector<compar> &aux, int lo,
                     int mid, int hi) {
    for (int k = lo; k <= hi; ++k) aux[k] = a[k];

    int i{lo}, j{mid + 1};
    for (int k = lo; k <= hi; ++k)
      if (i > mid)
        a[k] = aux[j++];
      else if (j > hi)
        a[k] = aux[i++];
      else if (aux[j] < aux[i])
        a[k] = aux[j++];
      // aux[j] >= aux[i]
      else
        a[k] = aux[i++];
  }

  static void merge1(ns::vector<compar> &a, ns::vector<compar> &aux, int lo,
                     int mid, int hi) {
    for (int k = lo; k <= hi; ++k) aux[k] = a[k];
    int i{lo}, j{mid + 1}, k{lo};
    while (i <= mid && j <= hi) {
      if (aux[i] <= aux[j])
        a[k] = aux[i++];
      else
        a[k] = aux[j++];
      ++k;
    }
    while (i <= mid) a[k++] = aux[i++];
    /*
    while (j <= hi)
      a[k++] = aux[j++];
    */
  }
};

template <typename compar>
struct MergeBU {
  static void sort(ns::vector<compar> &a) {
    int n = a.size();
    ns::vector<compar> aux(n);
    for (int len = 1; len < n; len = len + len) {
      for (int lo = 0; lo < n - len; lo += len + len) {
        int mid{lo + len - 1};
        int hi{std::min(lo + len + len - 1, n - 1)};

        for (int k = lo; k <= hi; ++k) aux[k] = a[k];

        int i{lo}, j{mid + 1};
        for (int k = lo; k <= hi; ++k) {
          if (i > mid)
            a[k] = aux[j++];
          else if (j > hi)
            a[k] = aux[i++];
          else if (aux[j] < aux[i])
            a[k] = aux[j++];
          // aux[j] >= aux[i]
          else
            a[k] = aux[i++];
        }
      }
    }
  }
};

template <class S, class T>
void printSort(ns::vector<T> A) {
  S::sort(A);
  std::ranges::for_each(A, [](auto x) { std::cout << x << '\t'; });
  std::cout << '\n';
  std::cout << std::format("{}",
                           std::ranges::is_sorted(A) ? "Sorted" : "Unsorted");
  ;
  std::cout << "\n\n";
}

int main() {
  std::mt19937 mt(std::random_device{}());
  std::uniform_int_distribution rand(10, 99);
  ns::vector<int> A(16);

  std::cout << "\033[33mInit\033[0m\n";
  for (auto &e : A) {
    e = rand(mt);
    std::cout << e << '\t';
  }
  std::cout << "\n\n";

  std::cout << "\033[33mMergeTD\033[0m\n";
  printSort<MergeTD<int>, int>(A);
  printSort<MergeTD<int>, int>({4, 4, 4, 4});

  std::cout << "\033[33mMergeBU\033[0m\n";
  printSort<MergeBU<int>, int>(A);
  printSort<MergeBU<int>, int>({4, 4, 4, 4});
}