From ba36beaec6d37d26b075d96e58aad73151d6d39e Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Sat, 7 Jan 2023 18:47:11 +0100
Subject: Fix algs structure

---
 Year_2/Algorithms/countingsort.cc                  |  83 ++++++++
 .../Algorithms/data_structures/cc/countingsort.cc  |  83 --------
 .../data_structures/cc/ordinamento-lineare.cc      | 115 ------------
 Year_2/Algorithms/data_structures/counting_sort.cc |  86 ---------
 Year_2/Algorithms/data_structures/heap.c           |  95 ----------
 Year_2/Algorithms/data_structures/heap.rs          | 115 ------------
 Year_2/Algorithms/heapsort.cc                      | 208 +++++++++++++++++++++
 Year_2/Algorithms/ordinamento-lineare.cc           | 115 ++++++++++++
 8 files changed, 406 insertions(+), 494 deletions(-)
 create mode 100644 Year_2/Algorithms/countingsort.cc
 delete mode 100644 Year_2/Algorithms/data_structures/cc/countingsort.cc
 delete mode 100644 Year_2/Algorithms/data_structures/cc/ordinamento-lineare.cc
 delete mode 100644 Year_2/Algorithms/data_structures/counting_sort.cc
 delete mode 100644 Year_2/Algorithms/data_structures/heap.c
 delete mode 100644 Year_2/Algorithms/data_structures/heap.rs
 create mode 100644 Year_2/Algorithms/heapsort.cc
 create mode 100644 Year_2/Algorithms/ordinamento-lineare.cc

(limited to 'Year_2')

diff --git a/Year_2/Algorithms/countingsort.cc b/Year_2/Algorithms/countingsort.cc
new file mode 100644
index 0000000..49f29d7
--- /dev/null
+++ b/Year_2/Algorithms/countingsort.cc
@@ -0,0 +1,83 @@
+#include <fstream>
+#include <iostream>
+#include <string.h>
+#include <string>
+
+using namespace std;
+
+void
+counting_sort(int* A, size_t n, ofstream& fout)
+{
+    int i, j;
+    int max, min;
+    int* freq;
+    int* t;
+    int range;
+
+    max = A[0], min = A[0];
+    t = new int[n];
+
+    for (i = 1; i < n; ++i) {
+        if (A[i] > max)
+            max = A[i];
+
+        if (A[i] < min)
+            min = A[i];
+    }
+
+    range = (max - min) + 1;
+
+    freq = new int[range];
+
+    for (i = 0; i < range; ++i) {
+        freq[i] = 0;
+    }
+
+    for (i = 0; i < n; ++i) {
+        freq[A[i] - min] += 1;
+    }
+    for (i = 1; i < range; ++i) {
+        freq[i] = freq[i] + freq[i - 1];
+    }
+    fout << "0 ";
+    for (i = 0; i < range - 1; ++i) {
+        fout << freq[i] << ' ';
+    }
+
+    for (i = n - 1; i >= 0; --i) {
+        t[freq[A[i] - min] - 1] = A[i];
+        freq[A[i] - min]--;
+    }
+
+    for (i = 0; i < n; ++i) {
+        A[i] = t[i];
+        fout << A[i] << ' ';
+    }
+    fout << endl;
+
+    delete[] freq;
+    delete[] t;
+}
+
+int
+main()
+{
+    ifstream fin("input.txt");
+    ofstream fout("output.txt");
+    int N;
+
+    for (int i = 0; i < 100; ++i) {
+        fin >> N;
+        int* a = new int[N];
+
+        for (int j = 0; j < N; ++j) {
+            fin >> a[j];
+        }
+
+        counting_sort(a, N, fout);
+
+        delete[] a;
+    }
+
+    return 0;
+}
diff --git a/Year_2/Algorithms/data_structures/cc/countingsort.cc b/Year_2/Algorithms/data_structures/cc/countingsort.cc
deleted file mode 100644
index 49f29d7..0000000
--- a/Year_2/Algorithms/data_structures/cc/countingsort.cc
+++ /dev/null
@@ -1,83 +0,0 @@
-#include <fstream>
-#include <iostream>
-#include <string.h>
-#include <string>
-
-using namespace std;
-
-void
-counting_sort(int* A, size_t n, ofstream& fout)
-{
-    int i, j;
-    int max, min;
-    int* freq;
-    int* t;
-    int range;
-
-    max = A[0], min = A[0];
-    t = new int[n];
-
-    for (i = 1; i < n; ++i) {
-        if (A[i] > max)
-            max = A[i];
-
-        if (A[i] < min)
-            min = A[i];
-    }
-
-    range = (max - min) + 1;
-
-    freq = new int[range];
-
-    for (i = 0; i < range; ++i) {
-        freq[i] = 0;
-    }
-
-    for (i = 0; i < n; ++i) {
-        freq[A[i] - min] += 1;
-    }
-    for (i = 1; i < range; ++i) {
-        freq[i] = freq[i] + freq[i - 1];
-    }
-    fout << "0 ";
-    for (i = 0; i < range - 1; ++i) {
-        fout << freq[i] << ' ';
-    }
-
-    for (i = n - 1; i >= 0; --i) {
-        t[freq[A[i] - min] - 1] = A[i];
-        freq[A[i] - min]--;
-    }
-
-    for (i = 0; i < n; ++i) {
-        A[i] = t[i];
-        fout << A[i] << ' ';
-    }
-    fout << endl;
-
-    delete[] freq;
-    delete[] t;
-}
-
-int
-main()
-{
-    ifstream fin("input.txt");
-    ofstream fout("output.txt");
-    int N;
-
-    for (int i = 0; i < 100; ++i) {
-        fin >> N;
-        int* a = new int[N];
-
-        for (int j = 0; j < N; ++j) {
-            fin >> a[j];
-        }
-
-        counting_sort(a, N, fout);
-
-        delete[] a;
-    }
-
-    return 0;
-}
diff --git a/Year_2/Algorithms/data_structures/cc/ordinamento-lineare.cc b/Year_2/Algorithms/data_structures/cc/ordinamento-lineare.cc
deleted file mode 100644
index 5af1b1d..0000000
--- a/Year_2/Algorithms/data_structures/cc/ordinamento-lineare.cc
+++ /dev/null
@@ -1,115 +0,0 @@
-#include <fstream>
-#include <iostream>
-#include <stdlib.h>
-#include <string>
-
-using namespace std;
-
-template <typename T>
-void
-counting_sort(T* A, size_t n, ofstream& fout, int incr, bool is_char = false)
-{
-    int i, j;
-    int max, min;
-    int* freq;
-    int* t;
-    int range;
-
-    for (i = 0; i < n; ++i) {
-        A[i] = A[i] * incr;
-    }
-
-    max = A[0], min = A[0];
-    t = new int[n];
-
-    for (i = 1; i < n; ++i) {
-        if (A[i] > max)
-            max = A[i];
-
-        if (A[i] < min)
-            min = A[i];
-    }
-
-    range = (max - min) + 1;
-
-    freq = new int[range];
-
-    for (i = 0; i < range; ++i) {
-        freq[i] = 0;
-    }
-
-    for (i = 0; i < n; ++i) {
-        freq[static_cast<int>(A[i] - min)] += 1;
-    }
-    for (i = 1; i < range; ++i) {
-        freq[i] = freq[i] + freq[i - 1];
-    }
-    fout << "0 ";
-    for (i = 0; i < range - 1; ++i) {
-        fout << freq[i] << ' ';
-    }
-
-    for (i = n - 1; i >= 0; --i) {
-        t[freq[static_cast<int>(A[i] - min)] - 1] = A[i];
-        freq[static_cast<int>(A[i] - min)]--;
-    }
-
-    for (i = 0; i < n; ++i) {
-        A[i] = t[i];
-        if (is_char) {
-            fout << (char)A[i] << ' ';
-        } else {
-            fout << A[i] / incr << ' ';
-        }
-    }
-    fout << endl;
-
-    delete[] freq;
-    delete[] t;
-}
-
-int
-main()
-{
-    ifstream fin("input.txt");
-    ofstream fout("output.txt");
-    string type;
-    int N;
-
-    for (int i = 0; i < 100; ++i) {
-        fin >> type;
-        fin >> N;
-
-        if (type == "double") {
-            double* a = new double[N];
-
-            for (int j = 0; j < N; ++j) {
-                fin >> a[j];
-            }
-
-            counting_sort(a, N, fout, 10);
-
-            delete[] a;
-        } else if (type == "char") {
-            char* a = new char[N];
-
-            for (int j = 0; j < N; ++j) {
-                fin >> a[j];
-            }
-
-            counting_sort(a, N, fout, 1, true);
-            delete[] a;
-        } else {
-            int* a = new int[N];
-
-            for (int j = 0; j < N; ++j) {
-                fin >> a[j];
-            }
-
-            counting_sort(a, N, fout, 1);
-            delete[] a;
-        }
-    }
-
-    return 0;
-}
diff --git a/Year_2/Algorithms/data_structures/counting_sort.cc b/Year_2/Algorithms/data_structures/counting_sort.cc
deleted file mode 100644
index 71cb505..0000000
--- a/Year_2/Algorithms/data_structures/counting_sort.cc
+++ /dev/null
@@ -1,86 +0,0 @@
-#include <fstream>
-#include <iostream>
-#include <string.h>
-#include <string>
-
-using namespace std;
-
-void
-counting_sort(int* A, size_t n)
-{
-    int i, j;
-    int max, min;
-    int* freq;
-    int* t;
-    int range;
-
-    max = A[0], min = A[0];
-    t = new int[n];
-
-    for (i = 1; i < n; ++i) {
-        if (A[i] > max)
-            max = A[i];
-
-        if (A[i] < min)
-            min = A[i];
-    }
-
-    range = (max - min) + 1;
-
-    freq = new int[range];
-
-    for (i = 0; i < range; ++i) {
-        freq[i] = 0;
-    }
-
-    for (i = 0; i < n; ++i) {
-        freq[A[i] - min] += 1;
-    }
-    for (i = 1; i < range; ++i) {
-        freq[i] = freq[i] + freq[i - 1];
-    }
-
-    for (i = n - 1; i >= 0; --i) {
-        t[freq[A[i] - min] - 1] = A[i];
-        freq[A[i] - min]--;
-    }
-
-    for (i = 0; i < n; ++i)
-        A[i] = t[i];
-
-    delete[] freq;
-    delete[] t;
-}
-
-int
-main()
-{
-    ifstream fin("input.txt");
-    ofstream fout("output.txt");
-    string s;
-
-    int* A = new int[1024];
-    int n;
-    char* token;
-
-    for (int i = 0; i < 100; ++i) {
-        getline(fin, s);
-        n = 0;
-        token = strtok((char*)s.c_str(), " ");
-        while (token) {
-            A[n++] = atoi(token);
-            token = strtok(NULL, " ");
-        }
-
-        counting_sort(A, n);
-
-        for (int i = 0; i < n - 1; ++i) {
-            fout << A[i] << ' ';
-        }
-        fout << A[n - 1] << endl;
-    }
-
-    delete[] A;
-
-    return 0;
-}
diff --git a/Year_2/Algorithms/data_structures/heap.c b/Year_2/Algorithms/data_structures/heap.c
deleted file mode 100644
index be7024b..0000000
--- a/Year_2/Algorithms/data_structures/heap.c
+++ /dev/null
@@ -1,95 +0,0 @@
-#include<stdio.h>
-#include<stdlib.h>
-#define HEAP_TYPE 0 // if 0 is max heap, else min heap
-
-unsigned heapsize = 0;
-
-int compare(int x, int y) {
-    return (!HEAP_TYPE) ? x < y : x > y;
-}
-
-void swap(int* a, int x, int y) {
-    int temp = a[x];
-    a[x] = a[y];
-    a[y] = temp;
-}
-
-void insert(int* a, int k) {
-    a[++heapsize] = k;
-    unsigned i = heapsize;
-
-    while(i > 1 && compare(a[i>>1], a[i])) {
-        swap(a, i, i >> 1);
-        i >>= 1;
-    }
-}
-
-void heapify(int* a, int n, int i) {
-    int l = i << 1;
-    int r = l | 1;
-
-    int max = i;
-    if(l <= n && !compare(a[l], a[max])) max = l;
-    if(r <= n && !compare(a[r], a[max])) max = r;
-
-    if(max != i) {
-        swap(a, i, max);
-        heapify(a, n, max);
-    }
-}
-
-void build(int* a, int n) {
-    for(unsigned i = n/2; i > 0; --i) {
-        heapify(a, n, i);
-    }
-}
-
-int extract(int* a) {
-    swap(a, 1, heapsize);
-    --heapsize;
-    heapify(a, heapsize, 1);
-    return *(a+heapsize+1);
-}
-
-int* heapsort(int* a, int n) {
-    int* b = malloc(sizeof(int) * n);
-    build(a, n);
-    for(unsigned i = n-1; i != -1; --i) {
-        b[i] = extract(a);
-    }
-
-    return b;
-}
-
-void increase_key(int* a, int i, int k) {
-    swap(a, i, k);
-    while(i > 1 && compare(a[i>>1], a[i])) {
-        swap(a, i, i >> 1);
-        i >>= 1;
-    }
-}
-
-int main() {
-    heapsize = 0;
-    int* a = malloc(sizeof(int) * 7);
-
-    insert(a, 5);
-    insert(a, 24);
-    insert(a, 1);
-    insert(a, 12);
-    insert(a, 35);
-    insert(a, -1);
-
-    printf("heap = ");
-    for(unsigned i = 1; i <= heapsize; ++i)
-        printf("%d ", *(a+i));
-
-    int n = heapsize;
-    int* b = heapsort(a, heapsize);
-    printf("\nheapsort = ");
-    for(unsigned i = 0; i < n; ++i)
-        printf("%d ", *(b+i));
-    free(b);
-    free(a);
-    return 0;
-}
diff --git a/Year_2/Algorithms/data_structures/heap.rs b/Year_2/Algorithms/data_structures/heap.rs
deleted file mode 100644
index 9dde55c..0000000
--- a/Year_2/Algorithms/data_structures/heap.rs
+++ /dev/null
@@ -1,115 +0,0 @@
-struct Heap<T> {
-    array: [T; 32],
-    is_minheap: bool,
-    size: usize,
-}
-
-impl<T> Heap<T>
-where
-    T: PartialOrd + Copy + Default,
-{
-    fn new() -> Self {
-        Heap {
-            array: [T::default(); 32],
-            is_minheap: false,
-            size: 0,
-        }
-    }
-
-    fn insert(&mut self, k: T) {
-        self.size += 1;
-        self.array[self.size] = k;
-        let mut i = self.size;
-
-        while i > 1 && self.compare(i >> 1, i) {
-            let temp = self.array[i];
-            self.array[i] = self.array[i >> 1];
-            self.array[i >> 1] = temp;
-            i >>= 1;
-        }
-    }
-
-    fn heapify(&mut self, i: usize) {
-        let l = i << 1;
-        let r = l | 1;
-
-        let mut max = i;
-        if l <= self.size && !self.compare(l, max) {
-            max = l;
-        }
-        if r <= self.size && !self.compare(r, max) {
-            max = r;
-        }
-
-        if max != i {
-            let temp = self.array[i];
-            self.array[i] = self.array[max];
-            self.array[max] = temp;
-            self.heapify(max);
-        }
-    }
-
-    fn extract(&mut self) -> T {
-        let temp = self.array[1];
-        self.array[1] = self.array[self.size];
-        self.array[self.size] = temp;
-        self.size -= 1;
-
-        self.heapify(1);
-
-        self.array[self.size + 1]
-    }
-
-    fn compare(&self, x: usize, y: usize) -> bool {
-        match self.is_minheap {
-            false => self.array[x] < self.array[y],
-            true => self.array[x] > self.array[y],
-        }
-    }
-}
-
-fn build<T: PartialOrd + Copy + Default>(array: [T; 32], n: usize) -> Heap<T> {
-    let mut heap = Heap::<T>::new();
-
-    heap.size = n;
-    heap.array = array;
-
-    for i in (1..=n / 2).rev() {
-        heap.heapify(i);
-    }
-
-    heap
-}
-
-fn heapsort<T: PartialOrd + Copy + Default>(array: [T; 32], n: usize) -> [T; 32] {
-    let mut heap = build(array, n);
-    let mut arr: [T; 32] = [T::default(); 32];
-    for i in (0..n).rev() {
-        arr[i] = heap.extract();
-    }
-
-    arr
-}
-
-fn main() {
-    let mut h = Heap::<i32>::new();
-    println!("{:?}", h.array);
-    h.insert(5);
-    h.insert(24);
-    h.insert(1);
-    h.insert(12);
-    h.insert(35);
-    h.insert(-1);
-    println!("{:?}\n", h.array);
-
-    let mut arr: [i32; 32] = [0; 32];
-    arr[1] = 5;
-    arr[2] = 24;
-    arr[3] = 1;
-    arr[4] = 12;
-    arr[5] = 35;
-    arr[6] = -1;
-    println!("{:?}", &arr);
-    let hh = heapsort(arr, 6);
-    println!("{:?}", hh);
-}
diff --git a/Year_2/Algorithms/heapsort.cc b/Year_2/Algorithms/heapsort.cc
new file mode 100644
index 0000000..7f1ad24
--- /dev/null
+++ b/Year_2/Algorithms/heapsort.cc
@@ -0,0 +1,208 @@
+#include <fstream>
+#include <iostream>
+
+using namespace std;
+
+enum class HeapType {
+    MAX,
+    MIN,
+};
+
+template <class T>
+class heap {
+public:
+    heap(HeapType type, int size)
+        : _type(type)
+        , _n { size }
+    {
+        _heapsize = 0;
+
+        a = new T[size + 1];
+    }
+
+    heap(HeapType type, T* arr, int size)
+        : _type(type)
+        , _n { size + 1 }
+    {
+        _heapsize = size - 1;
+
+        a = new T[size + 1];
+
+        for (int i = 1; i < _n; ++i) {
+            a[i] = arr[i - 1];
+        }
+
+        build(_heapsize);
+    }
+
+    void
+    swap(unsigned x, unsigned y)
+    {
+        auto t = a[x];
+        a[x] = a[y];
+        a[y] = t;
+    }
+
+    heap<T>*
+    insert(T key)
+    {
+        if (_heapsize == _n - 1)
+            return this;
+
+        a[++_heapsize] = key;
+
+        unsigned i = _heapsize;
+        while (i > 1 && compare(i >> 1, i)) {
+            swap(i, i >> 1);
+            i >>= 1;
+        }
+
+        return this;
+    }
+
+    void
+    heapify(int i)
+    {
+        _heapify_count++;
+        int l = i << 1;
+        int r = l | 1;
+
+        int max = i;
+        if (l <= _heapsize && compare(l, max) < 0)
+            max = l;
+        if (r <= _heapsize && compare(r, max) < 0)
+            max = r;
+
+        if (max != i) {
+            swap(i, max);
+            heapify(max);
+        }
+    }
+
+    void
+    build(int n)
+    {
+        for (unsigned i = n / 2; i > 0; --i) {
+            heapify(i);
+        }
+    }
+
+    T
+    extract()
+    {
+        swap(1, _heapsize);
+        --_heapsize;
+        heapify(1);
+        return *(a + _heapsize + 1);
+    }
+
+    void
+    heapsort(ofstream& fout)
+    {
+        T* b = new T[_heapsize];
+
+        _heapify_count = 0;
+        int n = _heapsize;
+        for (unsigned i = 0; i < n; ++i) {
+            b[i] = extract();
+        }
+        fout << _heapify_count << ' ';
+        for (unsigned i = 0; i < n; ++i) {
+            fout << b[i] << ' ';
+        }
+        fout << endl;
+
+        delete[] b;
+    }
+
+    ~heap()
+    {
+        delete[] a;
+    }
+
+    int
+    compare(unsigned x, unsigned y)
+    {
+        return _type == HeapType::MIN ? a[x] - a[y] : a[y] - a[x];
+    }
+
+private:
+    HeapType _type;
+    int _n;
+    int _heapsize;
+    T* a;
+    unsigned _heapify_count = 0;
+};
+
+int
+main()
+{
+    ifstream fin("input.txt");
+    ofstream fout("output.txt");
+
+    string type;
+    int n;
+
+    for (int i = 0; i < 3; ++i) {
+        fin >> type >> n;
+
+        if (type == "int") {
+
+            int k;
+
+            heap<int>* h = new heap<int>(HeapType::MIN, n * 10);
+            for (int j = 0; j < n; ++j) {
+                fin >> k;
+                h->insert(k);
+            }
+
+            h->heapsort(fout);
+
+            delete h;
+        } else if (type == "char") {
+            char* keys = new char[n];
+
+            for (int j = 0; j < n; ++j) {
+                fin >> keys[j];
+            }
+
+            heap<char>* h = new heap<char>(HeapType::MIN, keys, n + 1);
+
+            h->heapsort(fout);
+
+            delete h;
+            delete[] keys;
+        } else if (type == "bool") {
+            bool* keys = new bool[n];
+
+            for (int j = 0; j < n; ++j) {
+                fin >> keys[j];
+            }
+
+            heap<bool>* h = new heap<bool>(HeapType::MIN, keys, n + 1);
+
+            h->heapsort(fout);
+
+            delete h;
+            delete[] keys;
+        } else if (type == "double") {
+            double* keys = new double[n];
+
+            for (int j = 0; j < n; ++j) {
+                fin >> keys[j];
+            }
+
+            heap<double>* h = new heap<double>(HeapType::MIN, keys, n + 1);
+
+            h->heapsort(fout);
+
+            delete h;
+            delete[] keys;
+        }
+    }
+
+    fin.close();
+    fout.close();
+
+    return 0;
+}
diff --git a/Year_2/Algorithms/ordinamento-lineare.cc b/Year_2/Algorithms/ordinamento-lineare.cc
new file mode 100644
index 0000000..5af1b1d
--- /dev/null
+++ b/Year_2/Algorithms/ordinamento-lineare.cc
@@ -0,0 +1,115 @@
+#include <fstream>
+#include <iostream>
+#include <stdlib.h>
+#include <string>
+
+using namespace std;
+
+template <typename T>
+void
+counting_sort(T* A, size_t n, ofstream& fout, int incr, bool is_char = false)
+{
+    int i, j;
+    int max, min;
+    int* freq;
+    int* t;
+    int range;
+
+    for (i = 0; i < n; ++i) {
+        A[i] = A[i] * incr;
+    }
+
+    max = A[0], min = A[0];
+    t = new int[n];
+
+    for (i = 1; i < n; ++i) {
+        if (A[i] > max)
+            max = A[i];
+
+        if (A[i] < min)
+            min = A[i];
+    }
+
+    range = (max - min) + 1;
+
+    freq = new int[range];
+
+    for (i = 0; i < range; ++i) {
+        freq[i] = 0;
+    }
+
+    for (i = 0; i < n; ++i) {
+        freq[static_cast<int>(A[i] - min)] += 1;
+    }
+    for (i = 1; i < range; ++i) {
+        freq[i] = freq[i] + freq[i - 1];
+    }
+    fout << "0 ";
+    for (i = 0; i < range - 1; ++i) {
+        fout << freq[i] << ' ';
+    }
+
+    for (i = n - 1; i >= 0; --i) {
+        t[freq[static_cast<int>(A[i] - min)] - 1] = A[i];
+        freq[static_cast<int>(A[i] - min)]--;
+    }
+
+    for (i = 0; i < n; ++i) {
+        A[i] = t[i];
+        if (is_char) {
+            fout << (char)A[i] << ' ';
+        } else {
+            fout << A[i] / incr << ' ';
+        }
+    }
+    fout << endl;
+
+    delete[] freq;
+    delete[] t;
+}
+
+int
+main()
+{
+    ifstream fin("input.txt");
+    ofstream fout("output.txt");
+    string type;
+    int N;
+
+    for (int i = 0; i < 100; ++i) {
+        fin >> type;
+        fin >> N;
+
+        if (type == "double") {
+            double* a = new double[N];
+
+            for (int j = 0; j < N; ++j) {
+                fin >> a[j];
+            }
+
+            counting_sort(a, N, fout, 10);
+
+            delete[] a;
+        } else if (type == "char") {
+            char* a = new char[N];
+
+            for (int j = 0; j < N; ++j) {
+                fin >> a[j];
+            }
+
+            counting_sort(a, N, fout, 1, true);
+            delete[] a;
+        } else {
+            int* a = new int[N];
+
+            for (int j = 0; j < N; ++j) {
+                fin >> a[j];
+            }
+
+            counting_sort(a, N, fout, 1);
+            delete[] a;
+        }
+    }
+
+    return 0;
+}
-- 
cgit v1.2.3-18-g5258