Diskussion:Radixsort

nicht stabil? (Erledigt)

Stimmt das, das RadixSort nicht-stabil ist? Wenn ich wie im Beispiel z.B. die 124 doppelt habe und von links nach rechts, von der letzten Stelle anfange einzusortieren ändert sich doch die Position nicht => stabil?! JensKohl 14:26, 3. Jun 2005 (CEST)

Die englische Wiki sagt "Radix sort is a fast stable sorting algorithm". Da würde ich nämlich auch zustimmen. --H. Thole 17:57, 3. Jun 2005 (CEST)

Hab's geändert. --JensKohl 23:43, 9. Jul 2005 (CEST)

Dieser Abschnitt kann archiviert werden. --Zahlenzauber (Diskussion) 16:10, 7. Jan. 2024 (CET)

Bucketsort

Bucketsort hat eine eigene Seite: http://de.wikipedia.org/wiki/Bucketsort

Geschichte

Stimmt es, dass Herman Hollerith den Algorithmus erfunden hat, oder hat er ihn nur benutzt? (nicht signierter Beitrag von 88.68.67.249 (Diskussion | Beiträge) 22:51, 7. Mai 2010 (CEST))

Nachteil in Einleitung falsch?

In der Einleitung des Algorithmus heißt es: Der Nachteil dieses Sortierverfahrens ist, dass es bei einer festen Basis b mit fester Schlüssellänge k nur maximal b hoch k verschiedene Schlüssel sortieren kann. Das ist meiner Meinung nach kein Nachteil, da es für eine feste Basis b und eine feste Schlüssellänge k sowieso nur b^k verschiedene Werte gibt. (Bsp: b=10, k=2 = 10^2 = 100. Mit zwei Stellen kann ich im Dezimalsystem aber sowieso nur maximal 100 Zahlen darstellen (z.b. 0..99)) Regnaron 16:32, 9. Sep 2006 (CEST)

Das ist meiner Meinung nach auch kein Nachteil, aber aus einem anderen Grund: Doppelte Schlüsseleinträge sind nicht verboten, und mehr als b^k Schlüssel stellen überhaupt kein Problem dar. Eine Eingabefolge 1, 3, 2, 3 (b=3, k=1) ist mit dem Radix Verfahren sortierbar und hat mehr als 3^1 Schlüssel. Fas2 11:30, 7. Mär. 2008 (CET)

Versionsgeschichte von Fachverteilung

Teile des Artikels Fachverteilung wurden in diesen Artikel integriert. Die Versionsgechichte:

• 2007-03-28 15:05 (diff) (minor) Ma-Lik (Kt wiki)
• 2007-03-28 07:07 (diff) Madpower (/* Anmerkugnen */)
• 2007-03-28 07:05 (diff) 128.131.166.178 (anon) (AZ: Die Seite wurde neu angelegt.)

--Complex ^обс. 13:13, 1. Apr. 2007 (CEST)

Implementierung mit Pseudocode

was soll die Zeile "Solange a[L].bit(i) = 0 Und L < R" bedeuten? ich verstehe nicht, was ".bit(i)" zurückgibt. Meint es die i-te Stelle der Zahl im Feld a[L]? Wäre dankbar für Rückmeldung. -- 77.11.206.2 12:20, 9. Okt. 2010 (CEST)

Der Pseudocode ist falsch, er wurde von mir durch eine Eins zu Eins Java-Implementierung aus der obigen Beschreibung ersetzt. --91.119.4.128 18:07, 7. Nov. 2010 (CET)

Das Thema scheint zwar schon erledigt zu sein, aber ich lasse zur obigen Frage mal eine Antwort da: bit(i) bedeutet, dass die Zahl in eine Binärzahl umgewandelt werden muss und nur aus einer Abfolge von 0 / 1 besteht. Ansonsten: Wenn im Pseudocode "Solange" oder "WHILE" stehen, dann bedeutet das, dass sich hier eine Schleife befindet. Solange die angegebene(n) Bedingung(en) erfüllt sind, kehrt der Programmablauf immer wieder zu dieser Zeile zurück. --77.21.186.2 14:54, 9. Jul. 2021 (CEST)

Laufzeit

Der Artikel behauptet, O(n log(n)) sei eine bessere Abschätzung für die Laufzeit als O(n), da die Länge der Elemente mit ihrer Anzahl oft zunehme. Dies ist in realen Anwendungsfällen, wo 32/64-Bit-Integer oder Floats mittels Radixsort sortiert werden, wohl eher weniger gegeben: hier ist die Laufzeit stets O(n) (best/worst/average case). (nicht signierter Beitrag von 84.63.3.251 (Diskussion) 20:47, 23. Nov. 2011 (CET))

Dem möchte ich ausdrücklich zustimmen! Die Länge der Elemente, d.h. also indirekt die maximale Anzahl verschiedener Elemente, hängt im Allgemeinen eher von der Anwendung ab. Möchte ich zum Beispiel eine Liste aller Menschen meines Wohnortes nach dem jeweiligen Alter der Menschen sortieren, so ist die Länge der Liste vielleicht 100.000, die Länge eines Wertes muss aber nicht größer als 7 oder 8 bit sein. Der entscheidende Punkt ist, dass wenn ich beschließe, plötzliche alle Menschen dieser Welt zu sortieren, so ist die Liste viel länger und bspw. nicht mehr durch 32 Bit darstellbar --- die Länge eines Elements wird dadurch jedoch überhaupt nicht beeinflusst. In einem Wort: Länge der Liste und darzustellender Wertebereich hängen im Allgemeinen eher nicht zusammen. Oder in welcher Anwendung ist das so, abgesehen von Indizierung? --108.205.202.240 01:09, 25. Nov. 2011 (CET)

Die Laufzeit hängt vom intern verwendeten Sortieralgorithmus ab. D.h. wenn ich meine zu sortierenden Werte d Ziffern haben, so hab ich eine Laufzeit von Theta(d*(Laufzeit des internen Sortieralgorithmus)) im Cormen wird als Beispiel für einen "internen" Algorithmus Counting-Sort genommen, wo dann die Laufzeit Theta(d(n+k)) wäre, wobei d die Anzahl der Bits beschreibt, k der Wertebereich den die Elemente annehmen können und n die Anzahl der Element im Array. Linear wäre in dem Fall die Laufzeit dann wenn d = O(1) und k = O(n). (nicht signierter Beitrag von 46.223.74.215 (Diskussion) 21:59, 21. Mai 2014 (CEST))

Speicherverbrauch

Es gibt durchaus Radixsort-Verfahren, die in-place arbeiten, beispielsweise MSD-Radix Sort (siehe englische Wikipedia "radix sort"). Dieses Verfahren hat die "typischen" Radixsort Eigenschaften, verarbeitet also die Binärdarstellung der Elemente, hat Laufzeit O(m*n) usw. Stabil ist es allerdings ersteinmal nicht. Also entweder sollte man nicht sagen, dass Radixsort immer out-of-place ist oder aber definieren, welche Algorithmen genau gemeint sind, falls hier bspw. MSD-Radix Sort nicht betrachtet werden soll. -- 108.205.202.240 01:32, 25. Nov. 2011 (CET)

Java-Beispiel

In der Sammelphase sollte hier nicht die i-niederwertigste Ziffer der binären Darstellung berechnet und verwendet werden, sondern die b-näre Darstellung. Die Beschränkung der Eingabe auf binäre Elemente nutzt z.B. nicht den Effekt, dass bei linearen Zusammenhang von Basis b und Eingabelänge n die Komplexität asymptotisch gegen O(n*c) mit logn(n^c) = c strebt, statt O((b+n)logb(c)) mit c als größten vorkommenden Wert. (nicht signierter Beitrag von 92.192.43.69 (Diskussion) 09:19, 29. Jan. 2013 (CET))

Rekursives Beispiel nicht sinnvoll

Das rekursive Beispiel ist in meinen Augen nicht sinnvoll gewählt, da es eine triviale Rekursion ist, die man besser iterativ formuliert.

Folgende Überarbeitung schlage ich vor, die iterativ ist:

#include <algorithm>
#include <cstdint>
#include <vector>

using namespace std;

#define BASE 10

template <typename ForwardIt>
void radix_sort(ForwardIt begin, ForwardIt end) {
    // Falls Container leer ist
    if (begin == end)
        return;

    // Partitionierung
    vector<uint32_t> partition[BASE];
    uint32_t maximum = *max_element(begin, end);

    // Solange höchstwertigste Ziffer noch nicht erreicht
    for (int factor = 1; factor <= maximum; factor *= BASE) {
        // Ziffer ermitteln und im Segment abbilden
        for (ForwardIt iterator = begin; iterator != end; ++iterator)
            partition[*iterator / factor % BASE].push_back(*iterator);

        ForwardIt copy = begin;

        // Änderungen aus jedem Segment übernehmen
        for (auto& segment: partition) {
            for (uint32_t element: segment) {
                *copy = element;
                ++copy;
            }

            segment.clear();
        }
    }
}

--Diaspomod (Diskussion) 21:51, 18. Nov. 2019 (CET)

Stabil und in situ schließen sich aus?

Die folgende Aussage

"Der Radixsort kann entweder stabil (d. h. duplikate Schlüssel treten nach der Sortierung in der gleichen Reihenfolge auf wie in der Ursprungsmenge) oder in-place (d. h. kein zusätzlicher Speicher nötig) realisiert werden."

ist falsch. Wer schreibt so etwas?

Prinzipiell kann Radixsort, jedenfalls die LSD-Variante, nämlich mit jedem stabilen, in situ arbeitenden Sortieralgorithmus kombiniert werden. Das Radixsort bezieht sich nämlich genaugenommen nur auf die Vergleiche der (Schlüssel der) Sortierelemente untereinander oder einfach nur auf das Abtasten der/des jeweiligen Stelle, Ziffer oder Bits (bei nichtvergleichenden Sortieralgorithmen) . Doch weil dann diese Radixeigenschaft für den gesamten Algorithmus relevant und in gewisser Weise sogar dominant ist, ist das ein Radixsort.

So kann man z.B. auch das altbekannte Bubblesort, das sowohl stabil ist als auch in situ arbeitet, als Radixsort implementieren. Von den Elemente(schlüssel)n werden dann nur die jeweiligen Stellen/Ziffen/Bits miteinander verglichen und die Elemente dementsprechend bewegt (verschoben oder vertauscht). Da aber die Schlüssel n Stellen/Ziffern/Bits haben, muß für jede(s) jeweilige Stelle/Ziffer/Bit dann der Sortieralgorithmus erneut angewandt werden, in einer Hauptschleife demnach n mal durchlaufen werden.

Hier ein Beispiel eines Radixsorts LSD als "umhüllenden", Bubblesort als eigentlichen Sortieralgorithmus in Pascal innerhalb der Arraygrenzen "links" und "rechts" im (aus beliebigen integren Zahlen beinhaltenden) Array "Arr" mit beliebig auszugestaltender Tauschprozedur:

 for z:=0 to Bitanzahl do
   for y:=rechts downto links+1 do
     for x:=links to y-1 do
       if Arr[x] shr z and 1 > Arr[x+1] shr z and 1 then tausche(Arr[x],Arr[x+1])

Das "RadixLSDInPlace" in https://github.com/w0rthy/ArrayVisualizer ist jedenfalls ein LSD-Radixsort, das in situ arbeitet und zudem auch noch stabil ist.88.69.190.40 17:45, 13. Dez. 2019 (CET)

Könntest du kurz erklären, was in marked vom ArrayController und im Array vregs gespeichert wird? Der Algorithmus sieht auf den ersten Blick durch die Swap Methode nach Bubblesort aus...

Ein Bubblesort, der n Mal für jede Stelle ausgeführt werden muss, weil man nur ein Stellenwert vergleicht, würde ich nicht als Radixsort identifizieren, da es keine Partitionierungsphase gibt und bei Radixsort die Zahlen nicht miteinander verglichen werden. Das wäre doch eben nur ein wiederholter Bubblesort, da man eine ungeeignete Vergleichsrelation benutzt. Der Vorteil von Radixsort kommt dadurch jedenfalls nicht zum Tragen. Oder habe ich es falsch verstanden? --Diaspomod (Diskussion) 00:50, 15. Dez. 2019 (CET)

lineare Laufzeit geht immer (LSD)

Zu Beginn heißt es: Das Sortierverfahren hat, unter der Voraussetzung, dass die maximale Länge der zu sortierenden Schlüssel von vornherein bekannt ist, eine lineare Laufzeit.

Das funktioniert zumindest bei LSD auch dann, wenn die maximale Länge zu Beginn nicht bekannt ist. Der Trick funktioniert so, dass Radixsort die Auszählung und nachfolgende Neuordnung der Elemente auf Basis der 1er, vorab als eigenständiger Programmteil durchführen muss. Dann kann man parallel dazu noch nach der größten Zahl suchen. --Zahlenzauber (Diskussion) 16:44, 23. Dez. 2023 (CET)

Vorgehensweise (in-place)

Ich habe mir mal auf YouTube ein Video[1] angesehen, wie die "in-place"-Variante funktioniert. Es wurde zwar nichts beschrieben, weil man nur das Array als Balken gesehen hat und wie diese sich bewegen, aber ich habe aus dem Video schon das eine oder andere ableiten können. Es gibt - wie meistens üblich - zuerst eine Auszählung und dann beginnen sich alle ungeordneten Elemente von rechts nach links zu bewegen. Die Elemente die nicht passen, ordnen sich am linken Rand nach rechts an und die passenden werden rechts am passenden Bereich angehängt. Die Bereiche mit den passenden Elementen, wandern dann vom rechten Rand des Arrays nach links. Aufgrund dieser Funktionsweise sollte die "in-place"-Variante eigentlich ebenfalls stabil sein und nicht instabil, wie es aktuell im Artikel steht. Allerdings lässt das Video vermuten, dass die "in-place"-Variante um ein vielfaches langsamer sein könnte als Bubblesort, was den Sinn bereits im Vorfeld infrage stellt. Die "eine" Erklärung kann es aber sowieso nicht geben, weil man einen Algorithmus ja so oder so programmieren kann. --Zahlenzauber (Diskussion) 14:22, 31. Dez. 2023 (CET)

Ich habe noch einmal genauer hingesehen. Einer der 10 geordneten Bereiche ist auf der linken Seite und wächst nach rechts und die 9 anderen Bereiche wandern von rechts nach links. Der unsortierte Bereich befindet sich zwischen den Bereichen 1 und 2. --Zahlenzauber (Diskussion) 14:26, 31. Dez. 2023 (CET)

Funktionsweise der dezimalen "in-place"-Variante

Ich hätte dem oben verlinkten Video noch etwas hinzuzufügen: Offensichtlich scheinen hier keine binären Zahlen sortiert zu werden, sondern dezimale. Des Weiteren ist ganz klar zu erkennen, dass diese "in-place"-Variante große Gemeinsamkeiten mit Insertionsort hat. Die erste noch unsortierte Zahl wird - wenn sie nicht an den Bereich "0" angehängt werden kann - gepuffert und dann bewegen sich der noch unsortierte Bereich, sowie alle Bereiche bis zum richtigen Bereich, um ein Element nach links. Dann wird die gepufferte Zahl hinten an den richtigen Bereich angehängt. Diese "in-place"-Variante ist daher grundsätzlich immer stabil. Allerdings dürfte es ziemlich unsinnig sein damit zu sortieren, weil Insertionsort immer schneller sortiert. Würde man Zahlen von 0 bis 99 sortieren, dann wäre Insertionsort mindestens doppelt und bei Zahlen von 0 bis 999 mindestens dreimal so schnell und so weiter. Man sollte auch bedenken, dass Radixsort bei einer dezimalen "in-place"-Sortierung die betreffenden Stellen der Zahlen erst mit einer aufwändigen Formel herausrechnen muss. (X = Int(Zahl/Teiler)-Int(Int(Zahl/Teiler)/10)*10) Weil Insertionsort hingegen die ganzen Zahlen vergleicht, wird Insertionsort auch deshalb um ein vielfaches schneller sortieren. --Zahlenzauber (Diskussion) 13:46, 7. Jan. 2024 (CET)

Anmerkung zu "Vorgehensweise (via Countingsort)"

Zu Beginn heißt es, dass zwei Phasen erforderlich wären. Eine Zählphase und eine Sammelphase. Dazu sage ich: Das wird im Normalfall zwar so programmiert, aber grundsätzlich ist diese Aussage auch falsch, weil man das auch mit nur einer Phase machen kann. Während die Sammelphase läuft, kann man natürlich auch parallel dazu bereits die Zählphase für die nächste Sammelphase laufen lassen, also beides mit nur einem Durchlauf durch das Array. Zu Beginn muss man dann natürlich einen Vor-Algorithmus einbauen, der die Zählphase für die erste Sammelphase ausführt. Wieder parallel dazu, kann man dann im Fall von Radixsort (LSD) noch nach der größten Zahl suchen. Merke: Algorithmen kann man fast immer so oder so programmieren, weshalb eine Aussage nicht immer grundsätzlich richtig ist. --Zahlenzauber (Diskussion) 16:29, 7. Jan. 2024 (CET)