diff options
author | Santo Cariotti <santo@dcariotti.me> | 2023-01-07 18:47:11 +0100 |
---|---|---|
committer | Santo Cariotti <santo@dcariotti.me> | 2023-01-07 18:47:11 +0100 |
commit | ba36beaec6d37d26b075d96e58aad73151d6d39e (patch) | |
tree | 23226d5a3d5b49616abbb37e1ba3f9666faa489d /Year_2/Algorithms/data_structures | |
parent | a5534f16ecaf4b93f1bcd775f1e1df64203b3b65 (diff) |
Fix algs structure
Diffstat (limited to 'Year_2/Algorithms/data_structures')
-rw-r--r-- | Year_2/Algorithms/data_structures/cc/countingsort.cc | 83 | ||||
-rw-r--r-- | Year_2/Algorithms/data_structures/cc/ordinamento-lineare.cc | 115 | ||||
-rw-r--r-- | Year_2/Algorithms/data_structures/counting_sort.cc | 86 | ||||
-rw-r--r-- | Year_2/Algorithms/data_structures/heap.c | 95 | ||||
-rw-r--r-- | Year_2/Algorithms/data_structures/heap.rs | 115 |
5 files changed, 0 insertions, 494 deletions
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); -} |