Diskussion:Radixsort

aus Wikipedia, der freien Enzyklopädie

nicht stabil?

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)

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:

--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)