diff options
| author | Paul Jungeblut <s_jungeb@i08pc54.atis-stud.uni-karlsruhe.de> | 2014-11-25 14:28:29 +0100 |
|---|---|---|
| committer | Paul Jungeblut <s_jungeb@i08pc54.atis-stud.uni-karlsruhe.de> | 2014-11-25 14:28:29 +0100 |
| commit | ce929ea18aae0f2b80207bb38a329c824bf29166 (patch) | |
| tree | 78c01cc5007a150725388da16d0df7695dffacd8 /sonstiges/bucketSort.cpp | |
| parent | 1ac1594eec26e68365f6663220a7bd6eed1ce4ee (diff) | |
linear time sorting
Diffstat (limited to 'sonstiges/bucketSort.cpp')
| -rw-r--r-- | sonstiges/bucketSort.cpp | 16 |
1 files changed, 16 insertions, 0 deletions
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 |