From ce929ea18aae0f2b80207bb38a329c824bf29166 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc54.atis-stud.uni-karlsruhe.de>
Date: Tue, 25 Nov 2014 14:28:29 +0100
Subject: linear time sorting

---
 sonstiges/bucketSort.cpp | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
 create mode 100644 sonstiges/bucketSort.cpp

(limited to 'sonstiges/bucketSort.cpp')

diff --git a/sonstiges/bucketSort.cpp b/sonstiges/bucketSort.cpp
new file mode 100644
index 0000000..90533e1
--- /dev/null
+++ b/sonstiges/bucketSort.cpp
@@ -0,0 +1,16 @@
+vector<int> res;
+void bucketSort(vector<int> &a) { //stores result in global vector res
+	int c[BUCKETS] = {0};
+	for (int i = 0; i < (int)a.size(); i++) c[a[i]]++;
+	int C = 0;
+	for (int i = 0; i < BUCKETS; i++) {
+		int tmp = C;
+		C += c[i];
+		c[i] = tmp;
+	}
+	res.resize(a.size());
+	for (int i = 0; i < (int)a.size(); i++) {
+		res[c[a[i]]] = a[i];
+		c[a[i]]++;
+	}
+}
\ No newline at end of file
-- 
cgit v1.2.3