summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSanto Cariotti <santo@dcariotti.me>2022-10-28 10:01:15 +0200
committerSanto Cariotti <santo@dcariotti.me>2022-10-28 10:01:15 +0200
commit087ed3b52e6ff11697847fe158dbef8347a58347 (patch)
tree4738d36afecd94abbb3f3379279cd8a3e9945b56
parent8a54cce9efe8bad8a0e3d80adb4b7d771dcc5b6e (diff)
Add couting sort
-rw-r--r--Year_2/Algorithms/data_structures/counting_sort.cc86
1 files changed, 86 insertions, 0 deletions
diff --git a/Year_2/Algorithms/data_structures/counting_sort.cc b/Year_2/Algorithms/data_structures/counting_sort.cc
new file mode 100644
index 0000000..71cb505
--- /dev/null
+++ b/Year_2/Algorithms/data_structures/counting_sort.cc
@@ -0,0 +1,86 @@
+#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;
+}