Frage von ubik89, 25

Was ist der Unterschied zwischen Radixsort und Bucketsort?

Hallo,

ich verstehe den Unterschied zwischen Bucketsort und Radixsort nicht. Beide sortieren doch die Elemente in Buckets.

Kann mir das jemand mal erklären?

Antwort
von Jonas711, 12

Beide sortieren doch die Elemente in Buckets.

So weit hast du recht. Die Unterschiede bestehen darin, wie oft und nach welchen Kriterien einsortiert wird und was im Bucket geschieht.

Bucketsort: Es gibt aufsteigend sortierte Buckets (z.B. 0-9,10-19,20-29). In diese wird eingeordnet. Innerhalb des Buckets wird nach einem anderen Verfahren sortiert. Nach einer Einordnung in die Buckets und anschließender Sortierung ist der Algorithmus damit nach einer Runde beendet.

Radixsort: Du betrachtest immer nur eine Stelle der Elemente und gehst dabei von der kleinsten (rechts) zur größten (links) vor. (z.B. 17 landet beim 1. Mail in Bucket 7, beim zweiten Mal in Bucket 1). In den Buckets selbst wird nicht mehr sortiert, die Sortierung erfolgt stattdessen durch die mehrmalige Einordnung in Buckets.

Beispiel: 17 11 23

Bucketsort

Bucket 10-19: 17,11;

Bucket 20-29: 23. 

Innerhalb des 1. Buckets sind mehrere Elemente. Diese werden mit Insertionsort sortiert: 11,17

Durch Konkatenation hast du damit: 11,17,23.

Radixsort:

1. Runde (letzte Stelle wird betrachtet)

Bucket 1: 11

Bucket 3: 23

Buket 7: 17

Durch Konkatenation (Die Reihenfolge in den Buckets muss beachtet werden): 11,23,17

2. Runde (vorletzte (=1.) Stelle wird betrachtet)

Bucket 1: 11,17

Bucket 2: 23

Durch Konkatenation: 11, 17, 23

Keine passende Antwort gefunden?

Fragen Sie die Community