From e402f549e8101bcddb6181b8b8b42d10e217c780 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Fri, 11 Nov 2022 10:46:24 +0100 Subject: Add `countingsort` --- .../Algorithms/data_structures/cc/countingsort.cc | 83 ++++++++++++++++++++++ 1 file changed, 83 insertions(+) create mode 100644 Year_2/Algorithms/data_structures/cc/countingsort.cc diff --git a/Year_2/Algorithms/data_structures/cc/countingsort.cc b/Year_2/Algorithms/data_structures/cc/countingsort.cc new file mode 100644 index 0000000..49f29d7 --- /dev/null +++ b/Year_2/Algorithms/data_structures/cc/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; +} -- cgit v1.2.3-18-g5258