From ba36beaec6d37d26b075d96e58aad73151d6d39e Mon Sep 17 00:00:00 2001 From: Santo Cariotti 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 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 +#include +#include +#include + +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 -#include -#include -#include - -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 -#include -#include -#include - -using namespace std; - -template -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(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(A[i] - min)] - 1] = A[i]; - freq[static_cast(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 -#include -#include -#include - -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 -#include -#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 { - array: [T; 32], - is_minheap: bool, - size: usize, -} - -impl Heap -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(array: [T; 32], n: usize) -> Heap { - let mut heap = Heap::::new(); - - heap.size = n; - heap.array = array; - - for i in (1..=n / 2).rev() { - heap.heapify(i); - } - - heap -} - -fn heapsort(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::::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 +#include + +using namespace std; + +enum class HeapType { + MAX, + MIN, +}; + +template +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* + 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* h = new heap(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* h = new heap(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* h = new heap(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* h = new heap(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 +#include +#include +#include + +using namespace std; + +template +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(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(A[i] - min)] - 1] = A[i]; + freq[static_cast(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