Diskussion:Bucketsort

Das ist nicht kanonisches Bucket Sort

Wie meine Vorposter bereits erkannt haben, ist das hier beschriebene Verfahren weder das bekannte Bucket Sort, noch Radix Sort oder Counting Sort. Es handelt sich hier um eine spezielle Variante von Bucket Sort, auch "Histogram Sort" genannt, welche die Platzverschwendung verhindert. Auf keinen Fall ist es die kanonische Variante von Bucket Sort! Deswegen schlage ich dringend vor, den Artikel umzuschreiben auf das normale Bucket Sort und die Histogramm-Geschichte in einen eigenen Abschnitt auszulagern, da es einfach falsch ist, zu behaupten, das "sei" Bucket Sort. 134.76.3.111 15:58, 9. Feb. 2009 (CET)

Sicher das ihr hier Bucketsort beschreibt? „Introduction to Algorithms“ baut den Algo ganz anders auf. Ich bitte das zu überprüfen. --Cien 21:25, 1. Jun 2005 (CEST)

Stimmt! Dieses Verfahren scheint Counting-Sort zu sein!

Bucketsort ist ein anderer Name für Radixsort oder Distributionsort. Ich würde das gerne Umhängen, kenne mich damit aber nicht so wirklich aus. --JensKohl 23:49, 9. Jul 2005 (CEST)

Mir ist nur der deutsche Begriff Sortieren durch Fachverteilung bekannt, der scheint, so mein Eindurck, aber auch nur wirklich in dem einen Buch gestanden zu haben ... Im Prinzip wird aber genau BucketSort beschrieben, die Warnung kann also wieder raus.

RadixSort ist ein neues Verfahren, das BucketSort nutzt und nicht für alle Arten von Objekten tauglich ist, sondern eine Lexikografische Anordnung nutzt.. Gleicheit der Algorithmen ist keinesfalls gegeben! : Die Beschreibung ist allerdings etwas überarbeitungsbedürftig. Pinoccio 18:34, 14. Jul 2005 (CEST)

Ist BucketSort also allgemeiner, als RadixSort? Laut Vorlesungsunterlagen die ich noch gefunden habe, wurde Hashing bzw. Hashsort im Zusammenhang mit Buckets(ort) erklärt. Das ergibt für mich jetzt allerdings gar keinen Sinn mehr. Da RadixSort anhand der lex. Ordnung sortiert und im gg. dazu HashSort anhand einer Hashfunktion h(x) --JensKohl 19:16, 14. Jul 2005 (CEST)

Zu Details siehe zb [1]. BucketSort funktioniert umso besser je mehr gleiche Elemente es gibt(gleich bzgl dessen wonach sortiert wird), RadixSort benötigt eine Lexikalische Ordnung. mfg Pinoccio 22:59, 14. Jul 2005 (CEST)

"RadixSort ist ein neues Verfahren, das BucketSort nutzt[...]" Bitte was? Nach meinem ADS-Proff ist Radixsort ein Algorithmus aus der Lochkartenzeit. Er wurde manuell durchgeführt und er nutzt Countingsort. Der Schritt von CS wurde von einr mechanischen Sortiermaschine durchgeführt. Man kann ihn also kaum als "neu" bezeichnen^^ Gruß--Falk 22:17, 31. Mai 2006 (CEST)

Oops, muss mich nochmal ein wenig korrigieren. Radixsort muss nicht zwingend Countingsort nutzen. man kann auch alle anderen linearen Sortierverfahren implementieren, solange sie stabil sind (wie z.B. auch Bucketsort^^), was Radixsort aber immernoch nicht zu einem "neu[en]" Alg. macht^^. Gruß--Falk 19:32, 1. Jun 2006 (CEST)

Sollte es nicht so heissen?: Insgesamt ergibt sich für BucketSort also eine Komplexität von O(n+k). (+ statt *)

Nein! Um Gottes Willen^^ Dann könnte man den Alg. ja vollkommen vergessen. Die For-Schleifen werden doch hintereinander ausgeführt und nicht ineinander verschachtelt. Also sind die Laufzeiten der Schleifen nur zu addieren. Gruß--Falk 22:22, 31. Mai 2006 (CEST)

Ja, was bis vor kurzem hier beschrieben wurde war nicht der Bucketsort. Habe den Artikel nun inklusive Literaturangabe überarbeitet. --Gms 22:18, 10. Jun. 2010 (CEST)

Java Implementierung

Die Java implementierung kann so nicht stimmen. Die Daten werden nicht sortiert, sondern lediglich mit dem jeweiligen Index des Buckets überschrieben. Wäre gut, wenn das jemand verbessern könnte. --M3ax 01:28, 14. Jun 2006 (CEST)

Bei dieser einfachen Version des Algorithmus ist der Bucket-Index genau der Sortier-Wert. Unter Bucket 4 ist z. B. abgespeichert, wie oft die 4 im Eingabe-Array vorhanden ist. Und genau so oft wird sie dann in das sortierte Array geschrieben. An der nächsten Position wird dann damit weitergemacht, wie oft die 5 im Eingabe-Array vorhanden war usw.

Hat sich nun erledigt, da der Artikel nun Pseudo-Code enthält. --Gms 22:18, 10. Jun. 2010 (CEST)

Falscher Algorithmus

Nach dem, was ich in der englischen Wikipedia lese, scheint der Bucketsort eine Art umgekehrter Radixsort zu sein, welche beide den Countingsort verwenden. Hier im Artikel wird aber nur ein einziger Countingsort-Schritt beschrieben. Die "Alternative für ganze Zahlen" im letzten Abschnitt ist dann der Radix Sort, aber eben nicht der Bucket Sort, weil dieser mit der höchsten Stelle anfangen müsste, und nicht mit der niedrigsten. Anschließend müssten die Buckets dann einzeln mit der nächst-niedrigeren Stelle sortiert werden. --194.97.30.2 12:07, 14. Feb. 2007 (CET)

Ja, sorry, aber der Artikel ist Müll. Mr. Anderson 14:55, 14. Feb. 2007 (CET)

Der Artikel oder der Abschnitt Alternative für ganze Zahlen? Benutzer 194.97.30.2 hat nämlich, soweit ich es verstehe, nur diesen einen Abschnitt kritisiert. --Head 18:35, 14. Feb. 2007 (CET)

Nein (ich bin 194.97.30.2), auch vorher fehlt in der Erklärung des Algorithmus, dass die Buckets in sich nochmal sortiert werden müssen, entweder rekursiv nochmal mit dem Bucketsort, oder halt mit einem anderen Algorithmus --194.97.30.2 09:50, 15. Feb. 2007 (CET)

Das kommt doch darauf an, was man vorhat. Nimm doch mal das Beispiel mit den Bundesländern, das ich geschrieben habe: da gibt es keinen Anlass, die Einträge eines Buckets nochmal anzufassen. Man will es gerade nicht, weil man sich den Vorteil zu Nutze machen will, dass Bucketsort stabil ist, und die Liste war ja schon zuvor nach Stadtnamen sortiert, diese werden jetzt zum zweiten Sortierkriterium.

Was du meinst, steht schon im Abschnitt Variationen: Oft wird der Wertebereich der Schlüssel in Unterbereiche aufgeteilt, um die Anzahl der Buckets zu verringern. In diesem Fall muss innerhalb der Buckets weiter sortiert werden. Aber das ist wie gesagt nur eine Variation, eine Nachsortierung ist nicht immer nötig. --Head 12:34, 15. Feb. 2007 (CET)

Hmmm... vielleicht hast du doch Recht, und erst die Nachsortierung der Buckets macht das Verfahren zu Bucketsort, sonst ist es nur Countingsort. Dann müsste quasi der ganze Artikel nach Countingsort verschoben und Bucketsort von Grundauf neu geschrieben werden. :/ --Head 12:38, 15. Feb. 2007 (CET)

Ich würde vielleicht das Beispiel nach Countingsort rübernehmen.--194.97.30.2 14:15, 15. Feb. 2007 (CET)

Ich habe den Abschnitt Variationen übrigens heute selbst eingefügt.--194.97.30.2 14:19, 15. Feb. 2007 (CET)

Also ich hab jetzt nochmal im Internet gesucht, und es gibt scheinbar wirklich etwas Unklarheit dabei. Die einen beschreiben einen Algorithmus, der identisch mit Countingsort ist (zumindest wie ich ihn kenne), also so, wie er hier beschrieben wird. Andere zählen nicht vorher, sondern nehmen als Buckets verkettete Listen (oder andere Datenstrukturen variabler Größe). Wieder andere sagen, die Buckets müssten nachher durch Rekursion weiter sortiert werden, nochmal andere sagen, man sortiert per vergleichsbasierten Verfahren weiter. Aber in jedem Fall werden die Buckets (wenn überhaupt) einzeln weiter sortiert, und nicht wie der Pascal-Algorithmus ("Alternative für ganze Zahlen") alles komplett. Das ist eindeutig der Radix-Sort. --194.97.30.2 10:43, 15. Feb. 2007 (CET)

Die Buckets einzeln zu sortieren ist nur dann möglich, wenn man mit der höchsten Ziffer das Einordnen begonnen hat. Insofern ist der Pascal-Algorithmus korrekt gewesen. Und wenn man nicht mit einem anderen Sortierverfahren die Buckets einzeln sortieren möchte (wer möchte das?), dann ist es völlig egal, ob man nun die Buckets einzeln oder wieder komplett sortiert. Selbst nachdenken ist oftmals sinnvoller, als immer nur die Bücher zu wälzen. Gez. der Schreiber des Pascal-Algorithmus

Hab den Artikel jetzt entsprechend angepasst. --194.97.30.2 11:30, 15. Feb. 2007 (CET)

Ja, der Artikel beschrieb nicht den Bucketsort. Habe ihn entsprechend überarbeitet. --Gms 22:18, 10. Jun. 2010 (CEST)

Fehlende Quellenangaben

Dieser Artikel ist so gut wie wertlos. Ohne Quellen. Hier müsste eine gründliche Überarbeitung stattfinden, ohne diese ist dieser Artikel zu löschen.

Da muss ich widersprechen. Ein Text ohne Quellenangabe ist besser als gar kein Text. Und welche Quellen soll man denn angeben, wenn man eigene Algorithmen einbindet? Ein Lexikon kommt auch sehr gut ohne Quellenangaben aus.

Bei der Überarbeitung habe ich eine zentrale Literatur-Quelle ergänzt. --Gms 22:18, 10. Jun. 2010 (CEST)

Pseudocode

evt. Beispiel noch als Pseudocode (siehe englische Wikipedia) (nicht signierter Beitrag von 95.208.71.204 (Diskussion | Beiträge) 16:55, 28. Mai 2009 (CEST))

Algorithmus ist nun als Pseudo-Code spezifiziert (was bei diesem Algorithmus gut 'passt'). --Gms 22:18, 10. Jun. 2010 (CEST)

Laufzeit/Komplexität

Im Artikel steht "Die Laufzeit des Algorithmus liegt im Worst-Case in O(n)" unter der Annahme einer Gleichverteilung. Das ist allerdings der "Average Case" tatsächlich liegt der Algorithmus im Worst Case in O(n*n). Vergleiche dazu auch "Algorithmik" - Spektrum Akademischer Verlag 2001 von Uwe Schöning (nicht signierter Beitrag von Underscores1990 (Diskussion | Beiträge) 12:58, 19. Mai 2011 (CEST))

Stimme zu bei Worst Case in O(n*n). Ob Die Gleichverteilung wirklich den "Average Case" darstellt ("gefühlsmäßig" macht man das immer so), müsste m.E. durch Durchspielen aller möglichen Verteilungen bewiesen werden! Wozu aber keine Quelle angegeben zu sein scheint. --Nomen4Omen (Diskussion) 10:46, 16. Okt. 2017 (CEST)

Voraussetzungen falsch

Die im Artikel derzeit behauptete Voraussetzung einer Gleichverteilung für optimale Laufzeit ist falsch, wie sich auch aus der angegebenen Quelle ergibt. Dort steht nämlich "Even if the input is not drawn from a uniform distribution, bucket sort may still run in linear time.", was auch nachvollziehbar vorgerechnet wurde auf den Seiten davor.
Die folgende Aufgabe 8.4.4. liefert übrigens auch noch einen wichtigen Hinweis: entscheidend ist eigentlich, daß die Funtkion f die zu sortierenden Werte ausreichend gut verteilt. --Pinoccio 17:08, 12. Jun. 2010 (CEST)

Die Formulierung der Voraussetzung ist höchstens zu stark. D.h. die Aussage 'wenn Eingabe gleichverteilt dann O(n) Laufzeit' ist richtig. Aber klar, selbst wenn die Eingabe nicht perfekt gleichverteilt ist, kann der Algorithmus eine lineare Laufzeit haben - aber nur, wenn unter der Verteilung ebenso Gleichung 8.1 (Cormen) erfüllt ist, also wenn die Summe der Erwartungswerte der quadrierten Bucketgrößen linear ist (was bei der Gleichverteilung der Fall ist). D.h. es ist nicht für alle möglichen Verteilungen eine Funktion f konstruierbar, so dass der Algorithmus Bucketsort in O(n) ist. --Gms 12:31, 15. Jun. 2010 (CEST)

Habe den Artikel überarbeitet – sollte nun erledigt sein. --Gms 10:35, 24. Feb. 2012 (CET)