Sortieralgorithmen: Bucket sort by ozelot47

View this thread on steempeak.com
· @ozelot47 ·
$6.61
Sortieralgorithmen: Bucket sort
Der **Bucket sort**-Algorithmus ist ein Sortierverfahren, welcher in zwei Schritten aufgebaut ist.
Der erste Schritt besteht darin einen Container zu erstellen, der die Größe <code>n</code> hat. Das <code>n</code> wird im Vorfeld festgelegt und würde im Falle von Zahlen <code>n=10</code> sein, da es 10 Ziffern gibt. Für Buchstaben wäre <code>n=26</code> wenn man die Umlaute weglässt.

Als nächstes werden die Elemente in den Container/die Buckets nach folgendem Muster eingefügt:
Nehme das Element an der Stelle <code>list[i]</code> und füge es in dem Bucket <code>bucket[list[i] / n]</code> ein.

In dem Code-Beispiel von unten wird die Zahl 52 in dem 5.Bucket eingefügt, da <code>52 / 10 = 5.2 = 5</code> ist. Indizes bestehen aus natürlichen Zahlen, daher wird die Nachkommastelle ignoriert.

Wenn alle Elemente aus der Ursprungsliste eingefügt wurden, dann wird jedes Bucket mit einem weiteren Sortieralgorithmus sortiert. Das kann man z.B. mit dem Insertion sort oder dem Merge sort machen. Hat ein Bucket nur ein Element, so muss dieser Bucket natürlich nicht sortiert werden.
Zum Schluss werden alle Buckets von <code>n=1</code> bis <code>n=10</code> durchlaufen und alle Elemente nachfolgend in eine Liste eingefügt die nun aufsteigend sortiert ist.

* Bucket sort (c++)

```
#include <iostream>
#include <algorithm>
#include <vector>

void bucketSort(int list[], int size) { 
    /* create size-amount buckets */
    std::vector<int> bucket[size]; 
     
    /* place elements into different buckets */
    for (unsigned int i=0; i<size; i++)  { 
       int idx = list[i] / size; // bucketindex
       bucket[idx].push_back(list[i]); 
    } 
  
    /* sort all buckets */ 
    for (unsigned int i=0; i<size; i++) {
       sort(bucket[i].begin(), bucket[i].end());
    }
  
    /* collect all elements from the buckets */
    int index = 0; 
    for (unsigned int i = 0; i < size; i++) 
        for (unsigned int j = 0; j < bucket[i].size(); j++) 
          list[index++] = bucket[i][j]; 
} 
  
int main()  {
    const unsigned int SIZE = 10;
    int list[SIZE] = {52,34,81,13,12,61,73,11,31,22};
    bucketSort(list, SIZE); 
  
    for(unsigned int i=0; i<SIZE; i++) {
        std::cout << list[i] << "\n";
    }
    return 0; 
}  
```

Quelle
http://personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm [letzter Zugriff: 13.02.2020, 16:43]
👍  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , and 397 others
👎  
properties (23)
post_id84,363,491
authorozelot47
permlinksortieralgorithmen-bucket-sort
categoryde-stem
json_metadata{"tags":["de-stem","deutsch","stem","steemstem","palnet","science","programming"],"links":["http:\/\/personal.kent.edu\/~rmuhamma\/Algorithms\/MyAlgorithms\/Sorting\/bucketSort.htm"],"app":"steemit\/0.1","format":"markdown"}
created2020-02-13 16:04:21
last_update2020-02-13 16:04:21
depth0
children2
net_rshares21,604,287,096,324
last_payout2020-02-20 16:04:21
cashout_time1969-12-31 23:59:59
total_payout_value3.340 SBD
curator_payout_value3.274 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length2,374
author_reputation13,420,780,634,278
root_title"Sortieralgorithmen: Bucket sort"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
author_curate_reward""
vote details (462)
@steemstem ·
re-ozelot47-sortieralgorithmen-bucket-sort-20200214t054648068z
<div class='text-justify'> <div class='pull-left'> <center> <br /> <img width='200' src='https://res.cloudinary.com/drrz8xekm/image/upload/v1553698283/weenlqbrqvvczjy6dayw.jpg'> </center>  <br/> </div> 

This post has been voted on by the **SteemSTEM curation team** and voting trail. It is elligible for support from @curie and @minnowbooster.<br /> 

If you appreciate the work we are doing, then consider supporting our witness [@stem.witness](https://steemconnect.com/sign/account_witness_vote?approve=1&witness=stem.witness). Additional witness support to the [curie witness](https://steemconnect.com/sign/account_witness_vote?approve=1&witness=curie) would be appreciated as well.<br /> 

For additional information please join us on the [SteemSTEM discord]( https://discord.gg/BPARaqn) and to get to know the rest of the community!<br />

Please consider using the <a href='https://www.steemstem.io'>steemstem.io</a> app and/or including @steemstem in the list of beneficiaries of this post. This could yield a stronger support from SteemSTEM.
👍  
properties (23)
post_id84,378,189
authorsteemstem
permlinkre-ozelot47-sortieralgorithmen-bucket-sort-20200214t054648068z
categoryde-stem
json_metadata{"app":"steemstem-bot"}
created2020-02-14 05:46:51
last_update2020-02-14 05:46:51
depth1
children0
net_rshares15,566,924,110
last_payout2020-02-21 05:46:51
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length1,050
author_reputation229,673,617,633,863
root_title"Sortieralgorithmen: Bucket sort"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
author_curate_reward""
vote details (1)