summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Year_2/Algorithms/countingsort.cc (renamed from Year_2/Algorithms/data_structures/cc/countingsort.cc)0
-rw-r--r--Year_2/Algorithms/data_structures/counting_sort.cc86
-rw-r--r--Year_2/Algorithms/data_structures/heap.c95
-rw-r--r--Year_2/Algorithms/data_structures/heap.rs115
-rw-r--r--Year_2/Algorithms/heapsort.cc208
-rw-r--r--Year_2/Algorithms/ordinamento-lineare.cc (renamed from Year_2/Algorithms/data_structures/cc/ordinamento-lineare.cc)0
6 files changed, 208 insertions, 296 deletions
diff --git a/Year_2/Algorithms/data_structures/cc/countingsort.cc b/Year_2/Algorithms/countingsort.cc
index 49f29d7..49f29d7 100644
--- a/Year_2/Algorithms/data_structures/cc/countingsort.cc
+++ b/Year_2/Algorithms/countingsort.cc
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/data_structures/cc/ordinamento-lineare.cc b/Year_2/Algorithms/ordinamento-lineare.cc
index 5af1b1d..5af1b1d 100644
--- a/Year_2/Algorithms/data_structures/cc/ordinamento-lineare.cc
+++ b/Year_2/Algorithms/ordinamento-lineare.cc
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-24 00:18:26 +0000