From ef29888a7e0e6b9d806c8140b3cf2aef4d8bdbd5 Mon Sep 17 00:00:00 2001
From: Desislava Shunina <115353472+desiish@users.noreply.github.com>
Date: Tue, 15 Oct 2024 17:20:40 +0300
Subject: add CountingSort.cpp

---
 Practicum/pract02/CountingSort.cpp | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)
 create mode 100644 Practicum/pract02/CountingSort.cpp

(limited to 'Practicum/pract02')

diff --git a/Practicum/pract02/CountingSort.cpp b/Practicum/pract02/CountingSort.cpp
new file mode 100644
index 0000000..04e1e81
--- /dev/null
+++ b/Practicum/pract02/CountingSort.cpp
@@ -0,0 +1,30 @@
+void counting_sort(int* arr, size_t arrLength) {
+    constexpr int MAX_SIZE = 1e5;
+    int arr_copy[MAX_SIZE];
+
+    int max = arr[0];
+    for (int i = 0; i < arrLength; ++i) {
+        if (max < arr[i]) {
+            max = arr[i];
+        }
+        arr_copy[i] = arr[i];
+    }
+
+    int count[MAX_SIZE];
+    for (int i = 0; i < max + 1; ++i) {
+        count[i] = 0;
+    }
+
+    for (int i = 0; i < arrLength; ++i) {
+        count[arr[i]]++;
+    }
+
+    for (int i = 1; i <= max; ++i) {
+        count[i] += count[i - 1];
+    }
+
+    for (int i = arrLength - 1; i >= 0; --i) {
+        arr[count[arr_copy[i]] - 1] = arr_copy[i];
+        count[arr_copy[i]]--;
+    }
+}
-- 
cgit v1.3.1-23-gd82d