From 9e241889fa477f05983d2b6542e183387ef27e47 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Sun, 22 Jan 2023 16:59:30 +0100
Subject: adds

---
 Year_2/Algorithms/coppie-counting.cc | 81 +++++++++++++++++++++++++++++++++++
 Year_2/Algorithms/terne-counting.cc  | 82 ++++++++++++++++++++++++++++++++++++
 2 files changed, 163 insertions(+)
 create mode 100644 Year_2/Algorithms/coppie-counting.cc
 create mode 100644 Year_2/Algorithms/terne-counting.cc

diff --git a/Year_2/Algorithms/coppie-counting.cc b/Year_2/Algorithms/coppie-counting.cc
new file mode 100644
index 0000000..47acb14
--- /dev/null
+++ b/Year_2/Algorithms/coppie-counting.cc
@@ -0,0 +1,81 @@
+#include <fstream>
+#include <iostream>
+
+using namespace std;
+using pii = pair<int, int>;
+
+void
+countingsort(pii* A, int n, ostream& out)
+{
+    int min = A[0].first;
+    int max = A[0].first;
+
+    for (int i = 1; i < n; ++i) {
+        if (A[i].first < min)
+            min = A[i].first;
+        if (A[i].first > max)
+            max = A[i].first;
+    }
+
+    int range = max - min + 1;
+
+    int* freq = new int[range];
+    pii* C = new pii[n];
+
+    for (int i = 0; i < range; ++i)
+        freq[i] = 0;
+
+    for (int i = 0; i < n; ++i) {
+        freq[A[i].first - min]++;
+    }
+    for (int i = 1; i < range; ++i) {
+        freq[i] += freq[i - 1];
+    }
+
+    out << "0 ";
+    for (int i = 0; i < range - 1; ++i)
+        out << freq[i] << ' ';
+
+    for (int i = n - 1; i >= 0; --i) {
+        C[freq[A[i].first - min] - 1] = A[i];
+        freq[A[i].first - min]--;
+    }
+
+    for (int i = 0; i < n; ++i)
+        out << "(" << C[i].first / 10.0 << ' ' << C[i].second / 10.0 << ") ";
+
+    out << endl;
+    delete[] C;
+    delete[] freq;
+}
+
+int
+main(int argc, char** argv)
+{
+    int ts = (argc > 1) ? stoi(argv[1]) : 100;
+    ifstream fin("input.txt");
+    ofstream fout("output.txt");
+    string ch;
+    int n;
+    double x1, x2;
+
+    for (int i = 0; i < ts; ++i) {
+        fin >> n;
+        pii* a = new pii[n];
+        for (int j = 0; j < n; ++j) {
+            fin >> ch;
+            x1 = stod(ch.substr(1, ch.length()));
+            fin >> ch;
+            x2 = stod(ch.substr(0, ch.length() - 1));
+            a[j] = { x1 * 10, x2 * 10 };
+        }
+
+        countingsort(a, n, fout);
+        delete[] a;
+    }
+
+    fin.close();
+    fout.close();
+
+    return 0;
+}
diff --git a/Year_2/Algorithms/terne-counting.cc b/Year_2/Algorithms/terne-counting.cc
new file mode 100644
index 0000000..81a5a57
--- /dev/null
+++ b/Year_2/Algorithms/terne-counting.cc
@@ -0,0 +1,82 @@
+#include <fstream>
+#include <iostream>
+#include <tuple>
+
+using namespace std;
+using tiii = tuple<int, int, int>;
+
+void
+countingsort(tiii* A, int n, ostream& out)
+{
+    int min = get<0>(A[0]);
+    int max = get<0>(A[0]);
+
+    for (int i = 1; i < n; ++i) {
+        if (get<0>(A[i]) < min)
+            min = get<0>(A[i]);
+        if (get<0>(A[i]) > max)
+            max = get<0>(A[i]);
+    }
+
+    int range = max - min + 1;
+
+    int* freq = new int[range];
+    tiii* C = new tiii[n];
+
+    for (int i = 0; i < range; ++i)
+        freq[i] = 0;
+
+    for (int i = 0; i < n; ++i) {
+        freq[get<0>(A[i]) - min]++;
+    }
+    for (int i = 1; i < range; ++i) {
+        freq[i] += freq[i - 1];
+    }
+
+    out << "0 ";
+    for (int i = 0; i < range - 1; ++i)
+        out << freq[i] << ' ';
+
+    for (int i = n - 1; i >= 0; --i) {
+        C[freq[get<0>(A[i]) - min] - 1] = A[i];
+        freq[get<0>(A[i]) - min]--;
+    }
+
+    for (int i = 0; i < n; ++i)
+        out << "(" << get<0>(C[i]) / 10.0 << ' ' << get<1>(C[i]) / 10.0 << ' ' << get<2>(C[i]) / 10.0 << ") ";
+
+    out << endl;
+    delete[] C;
+    delete[] freq;
+}
+
+int
+main(int argc, char** argv)
+{
+    int ts = (argc > 1) ? stoi(argv[1]) : 100;
+    ifstream fin("input.txt");
+    ofstream fout("output.txt");
+    string ch;
+    int n;
+    double x1, x2, x3;
+
+    for (int i = 0; i < ts; ++i) {
+        fin >> n;
+        tiii* a = new tiii[n];
+        for (int j = 0; j < n; ++j) {
+            fin >> ch;
+            x1 = stod(ch.substr(1, ch.length()));
+            fin >> x2 >> ch;
+            x3 = stod(ch.substr(0, ch.length() - 1));
+            a[j] = { x1 * 10, x2 * 10, x3 * 10 };
+        }
+
+        countingsort(a, n, fout);
+        delete[] a;
+    }
+
+    fin.close();
+    fout.close();
+
+    return 0;
+}
-- 
cgit v1.2.3-18-g5258