Diskussion:Sortierverfahren

Diese Diskussionsseite dient dazu, Verbesserungen am Artikel „Sortierverfahren“ zu besprechen. Persönliche Betrachtungen zum Thema gehören nicht hierher. Für allgemeine Wissensfragen gibt es die Auskunft.

Füge neue Diskussionsthemen unten an:

Klicke auf Abschnitt hinzufügen, um ein neues Diskussionsthema zu beginnen, und unterschreibe deinen Beitrag bitte mit oder --~~~~.

• Diskussionsregeln
• Hilfe zu Diskussionsseiten
• Sei sachlich und freundlich!
• Greife niemanden persönlich an!
• Geh von guten Absichten aus.

Auf dieser Seite werden Abschnitte ab Überschriftebene 2 automatisch archiviert, die seit 21 Tagen mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind. Die Archivübersicht befindet sich unter Archiv.

Fragen und Anmerkungen zu "stabil gegenüber instabil" bitte auf der Diskussionsseite des Artikels 'Stabiles Sortierverfahren' besprechen.

Quicksort - Speicherverbrauch

In dem Artikel hier steht, dass Quicksort keinen zusaetzlichen Speicher verbraucht (in-place). Im Artikel zu Quicksort steht aber explizit, dass Quicksort nicht in-place ist und einen Speicherverbrauch von O(logn) bzw. (worst case) O(n) hat. --92.195.84.222 00:00, 3. Jun. 2010 (CEST)

Genaus das selbe wollte ich anführen. DA es zwar in-place arbeitet aber immer ein konstanter Faktor O(logn) für die Rekursion verbrauche.. (nicht signierter Beitrag von 134.61.64.189 (Diskussion) 12:15, 1. Jun. 2011 (CEST))

Soweit ich das sehe, ist das noch nicht zu 100% im Artikel bereinigt? --arilou (Diskussion) 09:06, 17. Feb. 2014 (CET)

Anmerkung von mir: Quicksort ist zu 100% in-place, benötigt zum sortieren aber ein Rekursions-Array. In diesem Array muss es so viele Stellen geben, wie das zu sortierende Array Werte hat, weil die Anzahl der gleichzeitig aktiven Rekursionen, mit der Anzahl der zu sortierenden Werte identisch sein kann. Im Rekursions-Array muss es dann pro Anzahl der Werte, Platz für drei Zahlen geben. Der zusätzliche Speicherbedarf ist also exakt dreimal so groß, wie das zu sortierende Array. Wenn eine neue Rekursion starten soll, dann sichert Quicksort zuerst die drei aktuellen Hauptvariablen an das Ende des Rekursions-Array und arbeitet dann mit den neuen Werten der drei Hauptvariablen weiter. Wenn eine Rekursion hingegen geschlossen wird, dann übernimmt Quicksort die Werte der drei Hauptvariablen vom Ende des Rekursions-Arrays, um so dort weitermachen zu können, wo zuvor die letzte Rekursion gestartet wurde. Wenn der aktuelle Vorgang beendet ist und auch das Rekursions-Array leer ist, dann ist die Sortierung beendet. Wenn Interesse besteht, dann kann ich gerne einen Quellcode von Quicksort zur Verfügung stellen, der so auch im Basic des C64 funktionieren würde. --77.21.163.85 23:46, 25. Nov. 2020 (CET)

Wenn der Speicherverbrauch abhängig ist von der Anzahl der zu sortierenden Elemente, dann ist das genau das Gegenteil von "in-place". Ihr Beispiel widerspricht also vollständig Ihrer Aussage "Quicksort ist zu 100% in-place".

Kommentare und Beispielcode zu Quicksort bitte - wenn überhaupt - dann im Artikel Quicksort anbieten/einbringen.

--arilou (Diskussion) 09:11, 26. Nov. 2020 (CET)

Es ist "in-place", weil im Rekursions-Array keine der zu sortierenden Werte stehen. Dort werden pro Stelle immer nur drei der Variablen gespeichert, die das Sortieren steuern. Es handelt sich dabei um die drei Werte, die beim Start an eine neue Rekursion übergeben werden. Im zu sortierenden Array werden immer nur zwei Werte getauscht, wie es auch bei Bubble-Sort der Fall ist. --77.21.163.85 13:00, 26. Nov. 2020 (CET)

Kannst du Belege dafür angeben, dass Rekursions-Arrays ohne zu sortierenden Werte NICHT als Speicherverbrauch gelten? Auch wenn sie die Größe O(n) haben? Extrem neu und extrem seltsam wäre das für mich! –Nomen4Omen (Diskussion) 16:17, 26. Nov. 2020 (CET)

Die Belege würd' ich auch gern sehen. In meinem Studium ist sowas selbstverständlich mit eingerechnet worden. --arilou (Diskussion) 17:50, 26. Nov. 2020 (CET)

Ich habe mal ein bisschen gegoogelt und auf diversen Internetseiten nachgelesen. Es gibt keinen Hinweis darauf, dass die Variablen, die ein Sortierverfahren zum Sortieren verwendet, wie zum Beispiel VON; BIS; POSITION; PIVOT, zum Speicher gezählt werden. Quicksort ist demzufolge immer "in-place", auch wenn die Rekursionen bis zu dreimal mehr Platz im Arbeitsspeicher belegen, als das zu sortierende Array. Wenn im Zusammenhang von "?-place" vom Speicherverbrauch die Rede ist, dann ist damit nur das zu sortierende Array gemeint. Bleiben die zu sortierenden Werte nur im zu sortierenden Array, dann ist es immer "in-place". Werden sie beim Sortieren auch in andere Arrays verschoben / kopiert, dann ist es "out-of-place". --77.21.163.85 04:18, 27. Nov. 2020 (CET)

Hm, also hier in den WP-Artikeln In-Place-Algorithmus sowie in Platzkomplexität wird nicht auf die Daten beschränkt, sondern jeweils der gesamte Speicherbedarf betrachtet.

Eine Unterscheidung zwischen .hm. "Verarbeitungdaten" und "Prozess(intern)werten" ist in der Praxis nicht relevant - teure Datenzugriffe oder viel-Platz-pro-Datum kann ja behohen werden durch 'Sortierverfahren#Indirektes Sortieren'.

Frage ist doch: Kann ein Algorithmus auch auf einem kleinen Mikrocontroller implementiert werden, der nur sehr wenig eigenen Speicher besitzt, oder in Situationen, die keinen malloc ausführen können/dürfen, oder muss im Notfall eine Menge Ram allokierbar sein?

--arilou (Diskussion) 09:37, 27. Nov. 2020 (CET)

Wenn es nur wenig Speicher gibt, dann scheiden einige Sortierverfahren in der Tat aus. Was ist denn "malloc"? --77.21.163.85 01:03, 12. Dez. 2020 (CET)

'malloc' ist der Befehl, mit dem man in der Programmiersprache C Arbeitsspeicher dynamisch (während der Laufzeit) reserviert - also das Betriebssystem auffordert, bitte soundsoviel Arbeitsspeicher für das aktuelle Programm zusätzlich bereitzustellen; Rückgabewert ist dann ein Pointer auf selbigen Speicher.

Ein Problem dabei ist, dass sowohl die entsprechende C-Bibliotheksfunktion als auch die zugehörige OS-Routine selber natürlich keinen zusätzlichen Speicher anfordern dürfen, sonst gäb' das ja eine "Endlosrekursion", wenn die Bearbeitung eines malloc-Aufrufs selbst einen 'malloc' aufrufen würde...

D.h. es gibt (vor allem in Betriebssystemen) Routinen, die mitunter Such- und Sortieraufgaben ausführen müssen (suche freien Ram-Bereich, sortiere verbleibende Bereiche nach Kriterium abc), aber in keinem Fall zusätzlichen Speicher anfordern dürfen - mitunter ist selbst der Stack tabu.

--arilou (Diskussion) 10:30, 14. Dez. 2020 (CET)

Danke für die gute Erklärung. --77.21.163.85 18:17, 15. Dez. 2020 (CET)

Zum Quicksort:

Quicksort kann auch im ungünstigsten Fall in O(n*log n) sortieren, wenn man den Median korrekt bestimmt. Diese Bestimmung ist in O(n) möglich, so dass die optimale Laufzeit von Quicksort gewährleistet ist. -- 217.255.242.252 22:38, 4. Apr. 2009 (CEST)

eventuell könnte man einen Link auf die Seite http://www.sortieralgorithmen.de/ setzen. Da dort wirklich sehr viele Informationen zum Thema sind.

Das ist offenbar früher schon einmal erledigt worden. — Nol Aders 04:06, 8. Jun 2005 (CEST)

Bei Quicksort stand im Worst-Case immer noch O(n^2). Habe dies in O(n*log n) ausgebessert. 80.108.92.137 21:25, 17. Mär. 2012 (CET)

Ich sehe das so, dass hier nur die üblichsten Varianten dargestellt werden, und in allen üblichen Varianten hat Quicksort eine solch hohe Worst-Case-Komplexität. Sonst könnte man auch bei Mergesort inplace schreiben, man braucht nur das richtige inplace Mergeverfahren, solche sind aber sehr aufwändig und gehören nicht zum klassischen Mergesort. Naja, gibt es dazu Meinungen, wie man das handhaben sollte? --Chricho ¹ ² 21:44, 17. Mär. 2012 (CET)

Ich weiß nun, wo der Denkfehler liegt (zumindest meiner). O(n*log n) im Worst-Case steht für die Datensatzbewegungen. Ich habe dies fälschlicherweise mit der Gesamtlaufzeit gleichgesetzt. 80.108.92.137 00:09, 18. Mär. 2012 (CET)

Achso, also Quicksort geht durchaus mit O(n·log n) Worst-Case-Gesamtlaufzeit, hier gibt es zum Beispiel Informationen dazu, allerdings sind diese Verfahren eben relativ kompliziert und Quicksort büßt dann seine Einfachheit und damit Effizienz ein, sodass der typische Quicksort anders aussieht. --Chricho ¹ ² 00:34, 18. Mär. 2012 (CET)

Stabilität von Shellsort

To Do: Widerspruch der Angabe zur Stabilität von Shellsort in Tabelle und Einzelbeschreibung beheben.

// wohl von 2010 // --arilou (Diskussion) 09:19, 17. Feb. 2014 (CET)

Batcher-Sort

Sollte Batcher-Sort nicht auch in die Liste aufgenommen werden? Für Informationen zu Batcher-Sort siehe [1] -- 92.229.89.229 16:15, 25. Mär. 2009 (CET)

Weblinks

Bitte die Weblinks unter Berücksichtigung von WP:WEB aussortieren. Danke und Grüße --OecherAlemanne 02:18, 6. Jan. 2009 (CET)

Ob [2] wirklich in diesem Sinne obsolet ist, ist insofern fraglich, weil diese Seite nicht abgemeldet, sondern nur "temporär" nicht erreichbar ist - ein Zustand, der leider nunmehr aber doch schon seit einigen Monaten anhält. Der jetzige Betreiber, ein Schweizer Informatikprofessor, schweigt auf diesbezügliche Anfragen. Der ehemalige Webseitenbetreiber Herr Peter Weigel war wegen dieser Misere so freundlich, seinen Übergabestand der Internetseite von 2006 privat wieder anzubieten, und zwar unter [3]. (nicht signierter Beitrag von 212.101.24.135 (Diskussion | Beiträge) 15:32, 7. Aug. 2009 (CEST))

Danke für die Freischaltung des URL zu Herrn Weigels Internetseite. Die originale Seite dazu ist ja leider immer noch nicht erreichbar. (nicht signierter Beitrag von 89.244.76.187 (Diskussion | Beiträge) 09:58, 17. Aug. 2009 (CEST))

Der Weblink "Applets zur Visualisierung [...] mit Quellcode in Java" [4] führt in eine Sackgasse ("permission denied"). -- Zap Kaw 19:23, 27. Sep. 2010 (CEST)

Die Weblinks sollten meiner Meinung nach um die Website [5] erweitert werden. Bis jetzt übersichtlichste Darstellung der bekanntesten Sortieralgorithmen die ich kenne. ==130.83.115.132 14:17, 4. Jun. 2012 (CEST)

Turnier- Sortierung

Ich vermisse einen Algorithmus, welcher mir als "Tournament Sort" bekannt ist. Funktioniert wie das K.O.- System bei Turnieren. Paarweises vergleichen benachbarter Zahlen → Sieger (größere Zahl) kommt in nächste Runde Wird wiederholt, bis Gesamtsieger feststeht, dieser wird dann entfernt. Neuaustragung des Turniers nur auf dem Pfad des Siegers … Laufzeit: O (n log n)

Kenne den nur ich? Keine Relevanz? Wenn beides nicht zutrifft, würde ich einen kleinen Artikel dazu verfassen. (nicht signierter Beitrag von 139.18.147.11 (Diskussion | Beiträge) 00:04, 30. Mär. 2010 (CEST))

Kenne ich auch, Relevanz wird sich schon herausstellen, wenn der Artikel besteht. --Zahnradzacken 19:00, 16. Okt. 2010 (CEST)

Hört sich wie ein etwas optimierte Variante von Treesort an. Insbesondere "Neuaustragung des Turniers nur auf dem Pfad des Siegers …" erinnert an die Heapify-Operation von Heapsort.

Soweit ich das sehe, ist dieser Disku-Punkt noch nicht abschließend geklärt.

--arilou (Diskussion) 10:43, 17. Feb. 2014 (CET)

Die Tabelle sortieren?

Ist euch mal aufgefallen das man die Tabelle nicht in den Case-Kategorien sortieren kann? Liegt scheinbar daran das die O-Notationen alle den selben Wert haben. Könnte man das irgendwie fixen liegt's an der wiki-software? (nicht signierter Beitrag von 85.182.86.201 (Diskussion) 00:26, 9. Apr. 2011 (CEST))

Bei Sortieren nach "Best Case" werden BubbleSort und InsertionSort falsch einsortiert, obwohl ein {{SortKey|1}} wohl korrekt angegeben ist?

Bei "Average Case" ist Stoogesort falsch.

Bei "Worst Case" sind Shellsort und Stoogesort falsch.

--arilou (Diskussion) 12:18, 17. Feb. 2014 (CET)

Sortieren nach Beziehungen

Da steht: Für das topologische Sortieren gibt es Algorithmen, deren Laufzeit von der Anzahl der Beziehungen ${\mathcal {O}}\left(m\right)$ abhängt. Mir erscheint das sehr ungewöhnlich, daß als Anzahl der Beziehungen ein Landau-Symbol angegeben wird. Müßte da nicht $m$ genügen, bzw. könnte man das nicht ganz weglassen, da es eh nicht mehr verwendet wird?--Bimaterist 22:40, 19. Sep. 2011 (CEST)

Könnte man nicht. Ich glaube, es handelt sich nur um eine etwas unglückliche Formulierung. Gemeint ist sicher, dass die Laufzeit von der Anzahl der Beziehungen $m$ abhängig ist und asymptotisch ${\mathcal {O}}\left(m\right)$ beträgt. — Toshiki^talk 21:26, 21. Sep. 2011 (CEST)

Weiters steht da: Wenn die Beziehungen vollständig sind, also für je zwei Objekte eine Abhängigkeit vorgegeben ist, so geht die topologische Sortierung in eine gewöhnliche Sortierung über. Das Laufzeitverhalten der Algorithmen bei n Objekten ist dann ${\mathcal {O}}\left(1\right)$. Ähm, ${\mathcal {O}}\left(1\right)$ bei "gewöhnlicher Sortierung"? Das ist doch auch falsch, da gehört das bekannte ${\mathcal {O}}(n\cdot \log(n))$ hin, oder?--Bimaterist 22:40, 19. Sep. 2011 (CEST)

${\mathcal {O}}\left(1\right)$ ist in der Tat fragwürdig. Da eine topolgische Sortierung prinzipiell vergleichsbasiert stattfinden muss, halte ich Deine Angabe für sinnvoller. — Toshiki^talk 21:26, 21. Sep. 2011 (CEST)

Hat jemand dazu mal harte Quellen? Oder weiß zumindest, in welcher Literatur man das nachschauen kann (im Cormen steht das glaube ich nicht drin...) --engeltr 18:54, 27. Okt. 2011 (CEST)

Slow Sort ohne obere Schranke?

Wie soll denn bitte das passieren? Es wird doch in jedem Schritt einer an die richtige Stelle gebracht (mit ein paar Rekursionen, die wieder einer gewissen oberen Schranke genügen)? --Chricho ¹ ² 21:33, 17. Mär. 2012 (CET)

Mehrere wichtige Korrekturvorschläge

1) Wenn man schon massenweise Laufzeitenkomplexitäten für Sortieralgorithmen in der O-Notation angibt, sollte man es auch inhaltlich richtig machen. Laufzeitkomplexitätsangaben sollten stets für einen Algorithmus gelten aber nicht für die einzelnen mehr oder weniger unglücklichen Implementationen des beschriebenen Algorithmuses. Wenn zu Beginn eines Sortieralgorithmuses wie in mehreren der vorliegenden Implementation aus purer Faulheit nicht überprüft wird, ob alle zu sortiernden Elemente vielleicht schon richtig sortiert sind, was ja nur eine lineare Laufzeitkomplexität von O(N) hätte, und man sich somit eigentlich die gesamte wesentlich aufwändigere Sortierei mit einer Laufzeit von mindesten O(N*Log(N)) sparen könnte, braucht man sich auch nicht wundern, wenn die Laufzeitkomplexität von Sortieralgorithmen sogar im best case größer als das eigentlich erwartete O(N) ist. Mit anderen Worten: Wenn der Sortieralgorithmus von sich zu dumm ist, festzustellen, ob alle zu sortierenden Elemente schon richtig sortiert sind, und somit das Sortieren eigentlich komplett übersprungen werden könnte, braucht man am Anfang nur einmalig eine explizite Überprüfung dieses Sachverhaltes vorzunehmen und schon haben ausnahmslos alle Sortieralgorithmen im best case auch wieder die erwartete lineare Laufzeitkomplexität O(N).

2) Wie kann es sein, dass z.B. der Heapsort-Algorithmus in England (siehe englische Wikipedia) eine andere Speicherkomplexität hat als in Deutschland? Könnte es sein, dass man hier beim deutschen Heapsort-Algorithmus einfach Äpfel und Birnen zusammengezählt hat? Man sollte schon korrekt zwischen dem von einem Sortieralgorithmus benötigtem Datenspeicherplatz und dem benötigten Programmcodespeicherplatz unterscheiden. Es ist zum Beispiel x-fach erwiesen, dass Heapsort "in-place" arbeiteten kann und somit nur einen konstanten zusätzlichen Datenspeicherplatz benötigt, also O(1). Ob eine moderne Implementation von Heapsort rekursiv ist und für diese super schicken rekursiven Methodenaufrufe entsprechend viel Programmcodespeicherplatz benötigt wird oder statt der Rekursion eine klassische Repeat-Schleife mit einem entsprechendem Abbruchkriterium zum Einsatz kommt, was ja auf jeden Fall auch möglich wäre, ist ganz offensichtlich wieder implementationsabhängig. Ergo gilt, dass der Heapsort-Algorithmus auch nur konstanten zusätzlichen Programmspeicherplatz benötigt, also O(1).

3) Der Heapsort-Algorithmus läßt sich - wie wahrscheinlich jeder andere Sortieralgorithmus auch - stabil oder nicht stabil implementieren, das ist also wieder einmal implementationsabhängig. Die hier vorliegende Pseudocode-Implementation ist natürlich nicht stabil, aber mit den in der englischen Wikipedia vorgeschlagenen kleinen Implentationsänderungen, könnte man Heapsort stabil machen. Man braucht dazu nur sicherstellen, dass bei allen Elementen mit einem gleichen Schlüsselwert die bereits vorhandene Indexreihenfolge unverändert erhalten bleibt.

4) Man sollte sich schon mal fragen, ob man einen Sortieralgorithmus nicht nur inhaltlich richtig, sondern auch inhaltlich sinnvoll implementiert hat, was bestimmt nicht der Fall ist, wenn die angegebene Implementation eines Sortieralgorithmus alle Elemente, die bereits richtig sortiert waren, zuerst expizit anders sortiert, nur um das Ganze danach wieder umzukehren. Man kann Heapsort z.B. auch so implementieren, dass sich der Anfang des Arrays pro Runde um eins auf das Ende des Arrays zubewegt und nicht umgekehrt. Dazu müßte man nur einen Offset für den stetig wachsenden Array-Anfang statt eines stetig schrumpfenden Array-Endes verwalten. Soll aufsteigend sortiert werden, sollte man natürlich die Variante MinHeap anwenden, dann kann das Element mit dem jeweils kleinsten Schlüsselwert gleich am jeweilgen Anfang des Arrays stehen bleiben. Alle eigentlich unnötigen Herumswappereien von bereits richtig sortierten Elementen, die dann natürlich später wieder rückgängig gemacht werden müssen, könnten somit ersatzlos entfallen, was der Laufzeit der vorliegenden Implementation des Heapsort-Algorithmuses ganz bestimmt nicht schaden würde ...

Aragorn321 (Diskussion) 17:46, 18. Jul. 2012 (CEST)

Ganz zu Beginn schreibst du, die Analyse solle sich auf den Algorithmus, nicht auf die Implementierung beziehen. Alles Weitere geht aber vom Gegenteil aus.

1. Die Entscheidung, vorab die Eingabe darauf zu prüfen, ob sie zufällig schon sortiert ist, ist eine Frage der – wie du selbst sagst – Implementierung. Und abhängig von diesem Detail willst du nun die Aussagekraft des Best Case verwässern, weil plötzlich alle "Algorithmen" gleich abschneiden? Außerdem übersiehst du zwei Punkte:
   • Die Abfrage kann teuer sein und es ist eine Frage der Statistik, wie häufig der Fall auftritt und ob man die Kosten in Kauf nehmen will. Die Frage, was passiert, wenn man die Abfrage weglässt, kann die unverfälschte Laufzeit im Best Case beantworten.
   • Wenn nun der Algorithmus die Abfrage enthält, ist der Best Case einfach ein anderer: Alles ist sortiert, bis auf ein falsch einsortiertes Element.
2. Was soll "Programmcodespeicherkomplexität" sein und wie wird sie durch Rekursion beeinflusst?
3. +4. Deine Bemerkungen zu Heap Sort kannst du ja gerne in den Artikel einfließen lassen. Vor allem, weil ich im englischen Artikel keine Hinweise auf stabile Implementierungen finden konnte. Vielleicht stellst du die genaue Idee vorher noch hier ein und beantwortest die Frage, welcher der Schritte die Stabilität gewährleistet. Was du bei "Man braucht dazu nur sicherstellen, dass …" schreibst, ist ja gerade die Herausforderung eines stabilen Sortieralgorithmus. Der Aussagegehalt dieses Satzes übersteigt also nicht den des Satzes "Man braucht beim Sortieralgorithmus nur sicher zu stellen, dass am Ende jedes Element gegenüber seinen Nachbarn die Ordnungsrelation erfüllt."

--Zahnradzacken (Diskussion) 22:36, 18. Jul. 2012 (CEST)

1. Nun, die Bestcase-Komplexität ist relativ irrelevant, da stimme ich dir zu.
2. Ich sehe in der Tat keinen Grund, warum ein Heapsort logarithmischen Speicherbedarf haben sollte, wenn man Verweise auf Elemente als konstant groß annimmt. Die Rekursionen wären alle Endrekursionen.
3. Kannst du mir erklären, wie man Heapsort bitte stabil implementieren kann? Ich finde dazu auch nichts in der englischen Wikipedia. (natürlich inplace, ohne zusätzliches Merken der Positionen). Und was du da sagst, mit Minheap benutzen und dann nicht nach hinten packen müssen: Das funktioniert nicht, denn wenn du dann eins nach rechts gehst hast du da zwei separate Heaps, deren Spitze fehlt, die du dann zusammenfügen müsstest, was natürlich deutlich aufwändiger ist, als ein einziges Element zu versickern.
4. Das mit der sinnvollen Implementierung ist so eine Sache. Man kann Mergesort inplace implementieren. Allerdings sind die Verfahren, um inplace, stabil und in Linearzeit einen Merge durchzuführen, nichttrivial. Das sollte man dann nicht mehr als Standardmergesort ansehen, denn dort liegt eben eine erhebliche zusätzliche Logik in dieser Mergeimplementierung. Die Ausführung ist auch sehr aufwändig. Und auf verketteten Listen geht es ohnehin inplace, das ist aber nicht der Standardfall. Ebenso bei Quicksort, mit geeigneter Pivotisierung erhält man dort eine $\mathrm {O} (n\log n)$ Worstcase-Komplexität, die aber eben auch sehr aufwändig ist. --Chricho ¹ ² ³ 00:32, 19. Jul. 2012 (CEST)

Zu Laufzeitverhalten und Speicherplatzbedarf von Algorithmen und deren Implementationen

Nach meinen Kenntnissen gibt es für jeden allgemein bekannten Algorithmus, zu denen auch die Sortieralgorithmen zählen, genau einen anerkannten wissenschaftlichen Beweis, der nicht nur das genaue Verhalten des Algorithmuses sondern auch sein Laufzeitverhalten und seinen Speicherplatzbedarf beschreibt und beweist. Zu jedem dieser Algorithmen gibt es dann meist Hunderte von verschiedenen Implementationen in verschiedenen Programmiersprachen und mit unterschiedlichen Spezialvarianten. Natürlich haben auch all diese verschiedenen Implementationen ein und desselben Algoritmuses ihre eigenes Laufzeitverhalten und ihren eigenen Speicherbedarf, welche sich manchmal auch von dem Laufzeitverhalten und dem Speicherplatzbedarf des originalen Algorithmuses deutlich unterscheiden. Man darf jetzt aber nicht dem Trugschluß verfallen, dass die ermittelte Laufzeit oder der ermittelte Speicherplatzbedarf einer konkreten (meist der eigenen) Implementation eines Algorithmus festlegt, wie das Laufzeitverhalten oder der Speicherplatzbedarf des originalen Algorithmuses ist. Wenn also die eine Implementierung massiv rekursive Methodenaufrufe verwendet, welche den Programmspeicher-Stack entsprechend anwachsen lassen, eine andere Implementierung des selben Algorithmus aber ohne Rekursion sondern statt dessen mit einer klassischen Schleife auskommt und damit ein wesentlich besseres Speicherplatzverhalten aufweist, sollte man nicht den Speicherplatzbedarf der "schlechteren" Implementierung als den des originalen Algorithmus angeben.

Niemand will hier etwas verwässern (aber verbessern) bezüglich des angegebenen Laufzeitverhaltens von Sortieralgorithmen im Best Case. Allgemein bekannt ist, dass eine Überprüfung auf die korrekte Sortierung von N gegeben Elementen nur eine lineare Laufzeitkomplexität von O(N) hat. Denn man braucht dazu nur einal alle Elemente mit ihrem Vorganger bzw. Nachfolger in der Liste bzw. dem Array zu vergleichen also z.B. [test ob (a[i-1] <= a[i]) für alle i=(1,...,N-1)]. Ich weiss nicht, wo jetzt das konkrete Problem darin besteht, diesen simplen Test auf die korrekte Sortierung von N Elementen, der nachweislich keinen zusätzlichen Speicher braucht und ganz offensichtlich nur eine lineare Laufzeit hat, einer Implementierung eines Sortieralgorithmuses voranzustellen, wenn der Sortieralgorithmus nicht von allein feststellt, dass es eigentlich nichts zu sortieren gibt. Wenn ich z.B. N=2^25 sortierte Elemente zu sortieren habe, bin ich mit dem zusätzlichen Test bereits nach 2^25 Schritten fertig, ohne vorherigen Test dagegen erst nach mindestens 25*2^25 oder gar erst 2^50 Schritten. (nicht signierter Beitrag von Aragorn321 (Diskussion | Beiträge) 11:19, 19. Jul 2012 (CEST))

Zu Absatz 1: Wenn du aufzeigen kannst, wo im Artikel eine ungünstige Implementierung als Grundlage der Komplexität des abstrakten Algorithmus herangezogen wurde, wird das hier bestimmt verbessert. Mir kommen deine Ausführungen allgemein vor, nicht bezogen auf den Artikel.

Zu Absatz 2: Was heißt hier "nur linear"? Zeit ist Zeit. Rechne mal aus, wieviele Eingaben es theoretisch gibt und wie viele davon sortiert sind. Wegen dieser seltenen Fälle auch bei allen unsortierten Liste erst einmal die Liste zu durchlaufen (Worst case: erst beim letzten Element ein Dreher), kann teuer sein. Bei deinem Beispiel: Wenn ich nun 100 Eingaben mit 2^25 Elementen habe, eine davon ist sortiert (extrem über der wirklichen Eintrittswahrscheinlichkeit), muss ich bei der sortierten Liste 2^25 Schritte durchführen, bei den anderen 99 Listen ohne Annahme über ihre Anordnung im Schnitt 2^25/2 = 2^24 unnötige Schritte, bevor die eigentliche Sortierung beginnt. Macht 99*2^24 unnötige Schritte wegen einmaliger Ersparnis von 25*2^25. Dabei ist $99\cdot 2^{24}-25\cdot 2^{25}=822083584>0$.

Schon wenn sogar 1% aller Eingaben sortiert wäre, wäre es im Schnitt teurer, immer zu prüfen.

Und für die Komplexität macht diese Sonderfallprüfung sowieso keinen Sinn, weil, wie gesagt, der Best Case für den eigentlichen Sortiervorgang dann nicht mehr die sortierte Liste ist und ja eben nicht Implementierungen die Grundlage für die Komplexität sind. --Zahnradzacken (Diskussion) 12:46, 19. Jul. 2012 (CEST)

Die Angabe einer Bestcase-Laufzeit ohne solch künstliche "Optimierungen" ist durchaus sinnvoll, denn sie bietet Hinweise auf Adaptivität des Algorithmus. --Chricho ¹ ² ³ 00:05, 20. Jul. 2012 (CEST)

In der Welt, in der ich lebe, sind nahezu alle sortierbaren Daten schon sortiert. Jede Art von Katalogen, Verzeichnissen, Listen, Tabellen, Terminkalender liegen schon nach irgendwelchen Kriterien sortiert vor. Oder hat jemand schon mal ein unsortiertes Telefonbuch gesehen? Jede Anwendung, jeder Explorer oder Commander präsentiert mir auf dem Bildschirm vorsortierte Daten. Über das Internet werden sortierte Listen verschickt und empfangen. Alle Internetserver heben sich alle ihnen bekannten IP-Adressen sortiert auf. In Datenbanken gibt es massenweise Indexe oder Schlüssel, die nahezu alle sortierbaren Daten auf der Festplatte oder wenigstens im Cache sortiert vorhalten, alles nur damit nicht noch einmal sortiert werden muss, was schon mal sortiert war. Wenn ich wirklich mal unsortierte Daten haben will, benutze ich extra einen Zufallsgenerator, um mir diese Daten generieren zu lassen, dann sind sie wirklich noch nicht sortiert. Mit anderen Worten - in meiner Welt ist es eher der Regelfall und nicht die absolute Ausnahme, dass die Daten auf die ich zugreifen will, schon sortiert vorliegen.

Dabei spielt es keine Rolle, ob die Daten aufsteigend oder absteigend sortiert sind, denn diese beiden Sortierungen lassen sich in linearer Zeit ineinander überführen. Die übliche Methode dazu heißt reverse(), welche es ja eigentlich gar nicht geben dürfte, wenn wirklich so wenig (< 1%) sortiert wäre, wie weiter oben behauptet. Hier wird nur das erste Element mit dem letzten Element vertauscht, dann das zweite mit dem vorletzten usw. also

reverse(a) { swap(a[i], a[N-1-i]) für alle i =(0,...,N/2-1) }

Aber nehmen wir ruhig mal an, die ganze Welt wäre wirklich unsortiert, dann gelten laut der Mathematik, die ich gelernt habe, trotzdem noch folgende von jedermann überprüfbare Fakten:

1) Die Wahrscheinlichkeit p, dass zwei wirklich zufällige maximal N Bit lange Zahlen a und b die Bedingung (a <= b) erfüllen, beträgt p = (1/2 + 1/2^(i+N)) also p = (1/2 + epsilon).
2) Für hinreichend großes N=(16, 32, 64, ...) ist dieses epsilon aus 1) fast 0 und die Wahrscheinlichkeit p aus 1) somit gleich 1/2.
3) Damit eine Folge von M Elementen (a0, a1, a2, ... aM-1) aufsteigend sortiert ist, muss gelten (a0 <= a1) && (a1 <= a2) && (a2 <= a3) && ... && (aM-2 <= aM-1).
4) Alle diese unter 3) erwähnten Vergleiche der Form (aI <= aI+1) sind, wahrscheinlichkeitstheoretisch betrachtet, unabhängige Ereignisse, die alle mit einer Wahrscheinlichkeit von p = 1/2 eintreten.
5) Das k malige Eintreten von unabhängigen Ereignissen mit der Wahrscheinlichkeit p läßt sich mit der Binomialverteiling ermitteln und beträgt Pk = p^k.
6) Die Wahrscheinlichkeit dass der Test auf Sortiertheit der gegebenen M Elemente bereits schon nach k Vergleichen abgebrochen werden entspricht dem Pk aus 5).
7) Die Folge dieser einzelnen Wahrscheinlichkeiten Pk für k=(1,2,...) lautet 1/2, 1/4, 1/8, 1/16, 1/32, 1/64, ...
8) Die Summe der Folge (k/2^k) = 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + 6/64 + ... (M-1)/2^(M-1) gibt an, wieviel Vergleiche der Sortierungstest durchschnittlich bis zum Abbruch braucht.
9) Die Summe der unter 8) angegebenen Folge konvergiert gegen den Wert 2. 

Mit anderen Worten: es werden durschnittlich nur 2 einzelne und nicht wie behauptet 2^24 Vergleiche benötigt, bis der Test auf Sortiertheit (mit dem Ergebnis Nein) abgebrochen wird. Damit ergeben sich bei den oben erwähnten 99 nicht sortieren Eingaben der Länge L=2^25 nur 99 * 2 = 198 zusätzliche Vergleiche. Hinzu kommen 1*2^25 Vergleiche des Tests auf Sortiertheit für die eine sortierte Eingabe der Länge L=2^25. Dafür werden bei der einen sortierten Eingabe der Länge L=2^25 bei einem schnellen Sortieralgorithmus ca. 25*2^25 = 838.860.800 Schritte gespart. Nach Adam Ries bleibt somit eine Gesamtersparnis von mindestens

$25\cdot 2^{25}-1\cdot 2^{25}-198=24\cdot 2^{25}-198=805.306.368-198=805.306.170>0$ 

Schritten. Und das bei nur 1% sortierter Eingaben! Wie groß wäre wohl die Verbesserung wenn vielleicht 75% aller Eingaben schon sortiert sind? Aragorn321 (Diskussion) 02:29, 20. Jul. 2012 (CEST)

Du holst bei deinen Beiträgen aber ganz schön weit aus. Wenn die Welt, in der du lebst, keine unsortierten Listen kennt, dann wundert es mich, dass dich überhaupt Sortieralgorithmen interessieren. In all den Beispielen, die du verwendest, spielen Sortieralgorithmen eine Rolle.

Und ich gebe zu, dass meine Annahme der durchschnittlichen Anzahl an Schritten für den Vorabtest Unfug war. Interessant finde ich, dass der niedrige Durchschnitt der Anzahl an Schritten gerade daher kommt, dass eine weitgehend sortierte Liste sehr unwahrscheinlich ist.

Mein anderes Argument halte ich aber aufrecht: Man will wissen, wie sich das Verfahren (nicht die beste Implementierung) verhält. Wenn ich weiß, dass Insertionsort im besten Fall linear ist, brauche ich dafür keinen Vorabtest, bei Heapsort sollte man darüber nachdenken, gerade weil man weiß, dass auch der Best case nicht linear ist. Ich vermute, was Benutzer:Chricho mit "Adaptivität" meinte, geht in die gleiche Richtung. --Zahnradzacken (Diskussion) 19:12, 20. Jul. 2012 (CEST)

Aragorn321, Zahnradzacke, tztztz.

@Aragorn321: Natürlich kann man jedem Sortieralgorithmus irgendwelche Vorab-Prüfungen voranstellen, und diese sind i.A. dann wohl auch sinnvoll. Sie ändern aber nichts an der Zeit-/Platzkomplexität des Sortieralgorithmus' selbst. Wenn also festgestellt wurde "ja, es muss sortiert werden", gilt genau das in der Tabelle genannte.

@Zahnradzacke: Für die Einträge der Algorithmus-Eigenschaften in hiesiger Tabelle sollte die jeweils "beste" bekannte Implementierung verwendet werden, die "allgemein arbeiten kann" (also keine spezifischen Details einer konkreten CPU ausnützt o.ä.); zusätzlich kann es ja Anmerkungen geben (wie's z.Zt ja auch gibt) "häufig O(...) bei üblichen Implementierungen". Aber Vorzug hat die beste bekannte Implementierung - schlechter geht schließlich immer.

--arilou (Diskussion) 15:36, 17. Feb. 2014 (CET)

PS: Evtl. könnten Aragon321's theoretische Erwägungen bzgl. "ist ein Vorabtest auf bestehende Sortierung sinnvoll" als Abschnitt in den Artikel übernommen werden, mit Hinweis "wenn bereits sortierte Eingabe-Arrays erwartet werden, ..."

Nicht ausgeführte Punkte

Zu einigen Begriffen im Artikel fehlt eine Verlinkung, oder ein Detail-Abschnitt:

• natürliches Sortierverfahren: Bedeutung ist zwar beschrieben, nicht aber, welche denn nun natürlich sind und welche nicht.
• Adaptive Sortierverfahren sind (soweit ich das sehe) hier gar nicht genannt/aufgelistet.

--arilou (Diskussion) 12:02, 17. Feb. 2014 (CET)

sortieren-ordnen

ich rege mich ja nicht auf....aber "sortieren" bedeutet, eine Menge nach verschiedenen Sorten in Teilmengen unterteilen, während hier "ordnen" eine Reihenfolge innerhalb einer Menge herstellt. Ra-raisch (Diskussion) 14:22, 18. Mai 2015 (CEST)

Nun, dann ist "Sortieren" ja richtig, und "Ordnen" falsch. Denn das (Sortier-)Kriterium kann durchaus mehrere Elemente als "gleich" einstufen, und somit aus ihnen eine Teilmenge bilden. Dass tatsächlich alle Elemente unterschiedliche Schlüssel besitzen, ist ein Sonderfall.

Außerdem nennt alle Welt die Dinger nunmal "Sortierverfahren"...

--arilou (Diskussion) 14:29, 18. Mai 2015 (CEST)

Nichtvergleichbasiertes Sortieren

@Fabiwanne: @Arilou: Hallo! Bloße Abbildbarkeit reicht nicht, man braucht eine Abbildung, die auch die Ordnung erhält. Dass dies mit Verweis auf die Endlichkeit des Speichers immer möglich sein soll, ist aus mehreren Gründen irreführend. Erstens geht man in der Algorithmik üblicherweise von Datentypen aus, die beliebig viel Speicher einnehmen können (so etwa die Listen/Felder, von denen wir hier die ganze Zeit reden). Zweitens: Unter dieser Voraussetzung gibt es Datentypen, für die keine fixe Abbildung auf Ganzzahlen, sondern nur eine von der jeweiligen zu sortierenden Liste abhängige möglich ist. Beispiel: Brüche. Um dann für einen Radixsort etwa diese Abbildung zu bestimmen, braucht man schon einen Algorithmus (man muss vmtl. so etwas wie die nächsten Nachbarn bestimmen und braucht dafür schon mindestens n·log n) Drittens: Man möchte ggf. auch sortieren, wenn man eine Blackboxen hat, die man eben nicht auf Zahlen abbilden kann (wir reden auf einer typisierten Ebene, und praktisch relevant kann das auch werden). Viertens: Wenn wir tatsächlich über Situationen mit endlichem Speicher sprechen wollen, dann ist auch die Frage, ob die Abbildung innerhalb dieses begrenzten Speichers gelingt.

Der Abschnitt wäre allerdings auch sonst zu überarbeiten, „Bei großen Anzahlen zu sortierender Datensätze sind diese Algorithmen den vergleichsbasierten Verfahren überlegen“ ist in dieser Allgemeinheit jedenfalls nicht richtig, das hängt zumindest auch von der Verteilung der Werte ab. --Chricho ¹ ² ³ 13:26, 4. Jul. 2017 (CEST)

Es erfreut mich stets, wenn ein Artikel Verbesserung erfährt, auch wenn mein eigenes (Fach-)Wissen nicht der Weisheit letzter Schluss gewesen sein mag.

Ich dachte bei der Nicht-Abbildbarkeit zwar eher daran, wenn man z.B.

• mehrere Graphen nach "Komplexität" sortieren wollte (viel Spaß beim Definieren, nach welchen Kriterien, _und_ dann auch noch Herausfinden, "zu wie viel Prozent" ein Graph "komplex ist");
• Messwerte mit Ungenauigkeitsangaben. Zwei Messwerte mit praktisch demselben Wert, aber deutlich verschiedenen Genauigkeitsangaben - welcher ist da jetzt "größer"?
• Personen mit mehreren Vornamen. Laut deutschem Recht gibt es keine Reihenfolge mehr. D.h. wer im Personalausweis "Hugo Egon Müller" stehen hat, ist genauso "Egon Hugo Müller". Und kommt "Albert Egon Hugo Müller" jetzt _vor_ den beiden anderen, weil "A" < ("E" or "H")? Oder nach ihnen, weil länger?
• zweideutige Angaben. Z.B. in einem Zylinderkoordinatensystem (X;Radius;Winkel), in dem Winkel eine 360°-Periode hat, und so für den selben Punkt im Raum verschiedene Zahlendarstellungen existieren, die dann auch sonstwo "einsortiert" werden - nur nicht als "gleich" beieinander.

Auf jeden Fall kann das Herstellen einer Ordnung schwierig sein, zusätzliche Annahmen oder Vorgaben erfordern und/oder Vorverarbeitungsschritte notwendig machen. Und zu guter Letzt gilt immernoch, dass man nicht Äpfel mit Birnen vergleichen soll/kann - aber durchaus beide in einer Liste drinstehen können...

--arilou (Diskussion) 14:13, 4. Jul. 2017 (CEST)

Prinzipiell gilt die Abbildbarkeit auf die natürlichen Zahlen auch auf nicht endlichem Speicher. Außerdem kann man das natürlich so gestalten, dass die Daten nach der Abbildung wider in den speicher passen. Das Problem, dass der Algorithmus selbst einen eventuell extrem großen Speicherbedarf hat (Der eigentliche Grund warum man solche Algorithmen in den meisten Fällen ungern verwendet.) wurde ja bereits im Satz zuvor erwähnt. Dass solche Abbildungen dann möglicherweise etwas zu komplex werden habe ich ja schon angehängt. Fabiwanne (Diskussion) 14:47, 4. Jul. 2017 (CEST)

Nein, „extrem“ ist der Speicherbedarf auch dieser Algorithmen nicht. Auch wenn Speicher keine Rolle spielt, benutzt man sie nicht, weil sie oft nicht schneller sind (etwa weil die Anzahl der Stellen eines Integers deutlich größer als der Logarithmus der Länge der Liste ist).

Zur Situation bei einem Rechnermodell mit unbegrenztem Speicher: Die rationalen Zahlen (alle Brüche) zum Beispiel kannst du zum Beispiel nicht ordnungserhaltend auf die natürlichen Zahlen abbilden. Nur (noch auf ein paar Sonderfälle erweiterbar) für eine gegebene endliche Menge von rationalen Zahlen kannst du diese auf die natürlichen Zahlen abbilden, wobei du dann aber für jede gegebene Menge eine eigene Abbildung brauchst. --Chricho ¹ ² ³ 16:16, 4. Jul. 2017 (CEST)

Zu schneller: Deswegen steht am Anfang des Satze "Bei großen Anzahlen zu sortierender Datensätze" oder anders Formuliert: Wenn der Logarithmus der Anzahl der Datensätze deutlich größer als die Anzahl der Stellen eines Integers sind.

Der Fall wird schon abgefangen. – Wenn du das genauer spezifiziern willst tue es.

Zum Fall abzählbar Unendlich: Ja. Hast du recht. Aber dann schreib das so. Erweitere den Satz so, dass er auch für beliebig große Datentypen gilt. Aber einen Satz der nur für Endliche Datentypen (Und das sind nun mal die, die man benutzt.) gilt auf einen zu reverten, der sogar für endliche falsch ist, ist absoluter Quatsch. --Fabiwanne (Diskussion) 13:33, 5. Jul. 2017 (CEST)

Btw. ist der Satz noch immer richtig nur halt missverständlich. Unmöglich ist auch "nicht in annehmbarem Aufwand möglich." --Fabiwanne (Diskussion) 13:38, 5. Jul. 2017 (CEST)

Nochmal ne weitere Anmerkung: Bucketsort lässt sich mit Hilfe von Hashtabeln und Linked lists problemlos auf ℚ umschreiben. Voraussetzung für eine schnellere Laufzeit ist auch hier wieder dass die Anzahl der Stellen des längsten nenner*zähler deutlich kleiner als der Logarithmus der Länge der Liste ist. Laufzeit O(n+max(Zähler)*max(Nenner)). Ich würde Fast wetten, dass das für jeden Datentyp geht. Vielleicht sollte man die Schranke wirklich Einabuen. --Fabiwanne (Diskussion) 13:51, 5. Jul. 2017 (CEST)

Halt habe die Schranke kommentarlos übernommen. So stimmt die aber nicht. Einträge verteil 512 auf den Zahlenraum 0-1024: Vergleichsbasierte Laufzeit: 512*lb(512)=4608 Bucketsort: 2*512+1024=2048. aber (lb(512)=9)<(lb(1024)=10) Es gilt halt einfach n*lb(n)>n+k Das lässt sich nicht weiter vereinfachen. --Fabiwanne (Diskussion) 13:58, 5. Jul. 2017 (CEST)

Das „anders Formuliert“ ist aber kein „anders Formuliert“, sondern eine ganz andere Aussage, wenn wir die Anzahl der Stellen eines Integers selbst als Variable auffassen (was auch für die Praxis relevant ist, da man ja nicht immer dieselben Integers benutzt).

Zum egtl. Diskussionspunkt hier: Nein, die Algorithmik und Komplexitätstheorie und so auch dieser Artikel arbeiten in der Regel nicht nur mit endlichen Datentypen, so würden auch die ganzen Komplexitätsaussagen hier keinen Sinn machen, wenn die Arrays nicht beliebig groß werden könnten. Die Abbildung, die du für Brüche beschreibst, ist übrigens gerade keine Abbildung des Datentypes „auf Zahlenwerten gleicher Ordnung“ (wie es jetzt wieder im Artikel steht), sondern eben eine Abbildung nur von endlichen Listen von Brüchen auf endliche Listen von Ganzzahlen. Damit, dass man nächste Nachbarn bestimmen muss, hatte ich oben natürlich für den Fall Unrecht für den Fall von Brüchen, deren Zähler und Nenner man auslesen kann, aber für kompliziertere Datentypen von größeren Teilmengen der reellen Zahlen als Brüchen oder Blackbox-Brüche, mit denen nur Arithmetik möglich ist, bleibt die Aussage richtig. Daher ist „Zahlenwerte“ statt Ganzzahlen eben auch keine richtige Formulierung.

Natürlich geht das, was du beschreibst, für jeden Datentyp, indem man das Array zunächst vergleichsbasiert sortiert und dann die Position in dem sortierten Array als zugeordneten Integer wählt, womit dann nichts gewonnen ist. Ein besseres Verfahren gibt es hingegen nicht für jeden Datentyp (oder meintest du mit deiner Wette noch etwas anderes?). Beste Grüße --Chricho ¹ ² ³ 17:12, 5. Jul. 2017 (CEST)

Zuerst: Ich habe nie ein Verfahren beschrieben und mich ausdrücklich auf ganz ℚ bezogen. Diese Menge ist abzählbar unendlich und damit nicht endlich. (Die genannte Laufzeit ist die Laufzeit, wenn man einigermaßen intelligent Hauptnenner bildet und dann einfach Bucketsort nach Zähler ausführt.) Wie gesagt ich habe keinen Beweis, dass das es für jede abzählbare Menge so etwas gibt, ich nehme es aber an. Beweise für das Gegenteil sind aber gerne gesehen.

Für die reellen Zahlen (und jede andere nicht Abzählbare Menge) ist jegliche Aussage Quatsch, da schon Gleichheit nicht berechenbar ist, und damit auch Vergleichsbasierte Verfahren versagen.

Bei Sortierverfahren, geht man eigentlich immer nur in der Menge der zu sortierenden Elemente von unendlich aus. Die Datentypen selbst setzt man auf beliebig aber fest. So macht man das in der Komplexitätstheorie eigentlich fast überall. Um Laufzeiten zu bestimmen betrachtet man nur einen oder wenige Teile und hält den Rest für fest. Im Oberen Abschnitt zu Vergleichsbasierten Verfahren wird btw. folgendes geschrieben: „Bei der Komplexitätsanalyse wird davon ausgegangen, dass der Aufwand zum Vergleich zweier Elemente konstant ist.“ Das ist nunmal eine andere Definition dafür, dass die zu vergleichenden Datentypen endlich sind. Ohne eine solche Einschränkung wird der ganze Artikel sinnlos. Ist schon die worst case Laufzeit für einen einzigen Vergleich gegen unendlich, ist jede weitere Betrachtung der Komplexität sinnlos. Eine ähnliche Einschränkung bräuchte es halt auch für nicht vergleichsbasierte Verfahren. Sonst wird das ganze sinnlos. --Fabiwanne (Diskussion) 23:11, 10. Jul. 2017 (CEST)

Zu ℚ etc.: Das Problem ist da, dass – wenn man über Effizienz reden möchte – es nicht bloß darauf ankommt, dass die Abbildung effizient berechenbar ist (sagen wir in konstanter Zeit), sondern auch darauf, dass diese Abbildung die Parameter (Stellenzahl zum Beispiel bei Radixsort) in die Höhe schnellen lassen kann. Es gibt für jeden Datentypen (ob abzählbar oder nicht) mit Orakel-Vergleich so etwas – das habe ich oben beschrieben –, aber nur mit amortisiert logarithmischer Laufzeit zur Bestimmung der Position. Besser geht es im Allgemeinen nicht – nur wenn man schon eine gewisse Zusatzstruktur hat.

„Das ist nunmal eine andere Definition dafür, dass die zu vergleichenden Datentypen endlich sind.“ Nein, dass man davon ausgeht, dass Integer-Operationen in konstanter Zeit erfolgen, heißt nicht, dass man davon ausgeht, dass die Integers nur endlich groß sind, siehe Registermaschine, ein übliches Modell in der Komplexitätstheorie. Dass andernfalls eine Betrachtung der Komplexität sinnlos wäre, ist allerdings falsch, man muss nur richtig parametrisieren (siehe parameterized complexity). Und ist lexikographisches Sortieren von Strings zum Beispiel etwa kein sinnvolles Problem? Was eine „worst case Laufzeit gegen unendlich“ sein soll, weiß ich nicht. --Chricho ¹ ² ³ 00:38, 11. Jul. 2017 (CEST)

Wie gesagt: Gleichheit auf ℝ (und anderen nicht abzählbaren Datentypen) ist im Allgemeinen nicht berechenbar. Das war mit „worst case Laufzeit gegen unendlich“ gemeint. Garantiert nicht in logarithmischer Laufzeit berechenbar.

Strings sind wider ein schönes Beispiel für einfache Abbildbarkeit auf ℕ bei Beibehaltung der Ordnung und damit der Laufzeit O(n+k) auf einer Registermaschine. Und bei all dem geht es um richtiges parametrisieren. In dem ganzen Artikel (und bei fast jedem Vergleich von Sortierverfahren) geht es um Laufzeit in n. Das ist oben durch den Satz „Aufwand zum Vergleich zweier Elemente konstant“ verdeutlicht und im nächsten Abschnitt mit „Bei großen Anzahlen zu sortierender Datensätze“ Und das ist im Grund auch das was die Idee der Registermaschine ist. Der Parameter „Länge des Integers“ ist verhältnismäßig moderat.

Wie gesagt, du kannst gerne verdeutlichen, dass da noch irgend welche anderen Parameter eine Rolle spielen. Im Grunde lässt sich das ja schon aus den Laufzeiten ablesen. Dann aber mit ausdrücklichem Hinweis auf die entsprechend andere Parametrisierung. --Fabiwanne (Diskussion) 03:56, 11. Jul. 2017 (CEST)

Im grunde hast du es ja schon auf den Punkt gebracht:

Ums kurz und bündig zu formulieren (bündiger, als es der Artikel tut): Für Countingsort und Radixsort gilt: Man erreicht eine lineare Laufzeit in Abhängigkeit von der Anzahl der Elemente, handelt sich jedoch zusätzliche Parameter für die Laufzeit ein – sie lohnen sich dann im Ergebnis nur bei Arrays einer Länge in der Größenordnung des Wertebereichs

Sowas – etwas weniger Lachs formuliert – gehört in den Artikel. --Fabiwanne (Diskussion) 04:04, 11. Jul. 2017 (CEST)

Große Verständnisfrage

Hallo Ihr!
Tut mir aufrichtig leid! Aus dem Satz: »Bei Sortierverfahren, die nicht auf Vergleichen beruhen, kann ein linearer Anstieg der benötigten Zeit mit der Anzahl der zu sortierenden Elemente erreicht werden.« kann ich nicht erkennen, wie ohne Vergleich sortiert werden soll. Geht das denn?
Wenn nur gemeint ist, dass ein Sortierschlüssel im record nicht aufgezeichnet ist (wie man aus manchen Beispielen schließen könnte), dann kann man ja auch den erzeugten Sortierbegriff in O(n) in die record sequence eintragen und danach konventionell sortieren. (Auch in enwiki finde ich keinen Artikel oder auch nur Abschnitt, der das erklären würde.) Also: es wäre schon sehr angenehm, so etwas wie eine Definition von »Nichtvergleichbasiertes Sortieren« zu haben. --Nomen4Omen (Diskussion) 20:28, 5. Jul. 2017 (CEST)

Lieber Nomen4Omen! Schau dir einfach die angeführten Sortierverfahren an. Es werden andere Strukturen benutzt als der Vergleich, beim Radixsort ist es zum Beispiel die Darstellung der zu sortierenden Zahlen in einem Stellenwertsystem, beim Bucketsort eine Heuristik, die eine näherungsweise Position angibt … Beste Grüße --Chricho ¹ ² ³ 10:45, 8. Jul. 2017 (CEST)

@Chricho: Danke für Deine Antwort. Dennoch hinterlässt sie mich etwas ratlos und frustriert. Denn

1. Wenn's um Struktur geht, dann ist Vergleich eine Ordnungsstruktur resp. Ordnungsrelation. Und ich weiß nicht, was eine Heuristik soll, die keine Ordnungsrelation etabliert ?? Auf jeden Fall kennt ein Stellenwertsystem eine Ordnungsrelation !! Die ist es also nicht ?? Was dann ??
2. Irgendwie sollte man schon annehmen, dass es zwischen den angeführten Verfahren mehr Gemeinsamkeiten geben sollte als die Negation, etwas NICHT zu sein. Jedenfalls wäre es für einen Leser, der im Moment noch geneigt ist, sehr angenehm, wenn die Autoren des Artikels da mehr anbieten würden, als dass man sich einfach »die angeführten Sortierverfahren an«schaut. Dies insbesondere im Lichte der vorangegangenen Bemerkung, die ja schon das erste beste angegebene Verfahren Bucketsort aushebeln und zu einem vergleichsbasierten machen würde. --Nomen4Omen (Diskussion) 11:52, 8. Jul. 2017 (CEST)

Entschuldige, in meinem Beitrag oben habe ich Radix- und Bucketsort vertauscht. Also, zur Aufklärung: Das „nicht“ in „nicht-vergleichsbasiert“ bedeutet nicht, dass keine Ordnungsrelation auf dem Datentyp besteht, es bedeutet vielmehr „nicht ausschließlich vergleichsbasiert“, sondern mit einer Zusatzstruktur arbeitend (dass man auch vergleichen kann, lässt sich o.B.d.A. voraussetzen, wenn nicht, dann wäre sie von der Struktur, die man verwendet induziert). Was du dir unter „Aushebeln“ vorstellst, weiß ich nicht, die Verfahren lassen sich allesamt nicht in vergleichsbasierte übersetzen, ohne die Komplexität zu verändern. --Chricho ¹ ² ³ 09:39, 9. Jul. 2017 (CEST)

@Chricho: Danke für die Antwort. Ich glaube, ich verstehe jetzt besser, wie's gemeint ist. (Der Vergleich mit dem Lochkartensortierer hat mir geholfen.)

Wenn ich's recht verstehe, wird der paarweise Vergleich – also der Vergleich zwischen 2 Records – (zumindest teilweise) ersetzt durch eine Adressrechnung, die irgendwie aus dem eigentlichen Sortierbegriff gebildet wird und die nicht die Ordnung „zerstört“. In Relationensprechweise ist die Adressrechnung „nicht feiner“ als die Sortierfolge. Genauer: Ist $s_{1}\leq s_{2}$ die Ordnung der Sortierschlüssel, dann ist immer $AdrRech(s_{1})\leq AdrRech(s_{2})$. Im Fall, dass zu viele Duplikate entstehen, kann ja noch konventionell nachsortiert werden.

Ich habe nur Countingsort näher angeschaut. Die Annahmen sind ja keineswegs dieselben wie beim allgemeinen WortCase-Sort. In der Komplexitätsdiskussion vermisse ich völlig bspw. die Diskussion des Falles $k\sim {\mathcal {O}}(n\log n)$, dessen Ergebnis ja total anders aussieht als $n+k$, nämlich ${\mathcal {O}}(n\log n)$.

Der Satz »... kann ein linearer Anstieg der benötigten Zeit mit der Anzahl der zu sortierenden Elemente erreicht werden.« ist ja so recht wischi-waschi. Klingt ähnlich wie »bis zu 100 % Rabatt«. --Nomen4Omen (Diskussion) 19:18, 10. Jul. 2017 (CEST)

Aber es bleibt ja zugleich auch ${\mathcal {O}}(n+k)$. Ums kurz und bündig zu formulieren (bündiger, als es der Artikel tut): Für Countingsort und Radixsort gilt: Man erreicht eine lineare Laufzeit in Abhängigkeit von der Anzahl der Elemente, handelt sich jedoch zusätzliche Parameter für die Laufzeit ein – sie lohnen sich dann im Ergebnis nur bei Arrays einer Länge in der Größenordnung des Wertebereichs (sind also praktisch eher selten sinnvoll). Bei Bucketsort hängt es von der Variante ab, was genau dabei rauskommt, allgemein kann man sagen: Bucketsort funktioniert bei gleichverteilten Daten oder Daten mit bekannter Verteilung in Linearzeit, aber braucht viel Speicher. Flashsort wiederum behebt das Speicherproblem – wie dessen praktische Performance heutzutage aussieht, kann ich aber nicht sagen. --Chricho ¹ ² ³ 20:11, 10. Jul. 2017 (CEST)

@Chricho: Danke für Deine Antwort. Mir scheint, ich hab's im Wesentlichen getroffen.

Dann meine Hauptfrage: Könnte man nicht das mit der Adressrechnung oder Indizierung hineinbringen ?

Dass die Adressrechnung „ordnungserhaltend“ zu sein hat, steht nicht richtig deutlich da.

Schön, dass Du auch ein paar Drawbacks erwähnst. Z.B. Viel Speicher. Frage: Muss der viele Speicher nachher auch durchgelesen werden? Gibt es in den Artikeln Versuche, dies zu quantifizieren?

Ich möchte mich in das Thema nicht wirklich einarbeiten, möchte den Artikel also nicht selbst verbessern. --Nomen4Omen (Diskussion) 20:32, 10. Jul. 2017 (CEST)

Ja, muss er (aber bei Flashsort braucht man ja weniger Speicher), aber wie gesagt, ich kenne mich mit neueren Praxiswerten nicht aus, und ich weiß auch von keiner verbreiteten Bibliothek oder dergleichen, dass sie Flashsort implementieren würde. --Chricho ¹ ² ³ 20:54, 10. Jul. 2017 (CEST)

Bzgl. der ursprünglichen Frage: Ich war mal so frei, im Artikel mit einem Halbsatz auszuhelfen. Das Thema scheint ja häufiger für Un-/Missverständnisse zu sorgen. --arilou (Diskussion) 12:36, 16. Okt. 2017 (CEST)

Struktur für mehrere Artikel / Lemma: (Informatik)

Die Sortierung im chinesischen Wörterbuch erfolgt in erster Ebene nach der Zahl der Striche.

1. Wie weiter?
2. In welchen Artikel einbringen?
3. Industrielle SV, Erweiterung oder Hinweis auf solche Verfahren? BKL?

AVS (Diskussion) 13:13, 15. Okt. 2017 (CEST)

Es gibt keine speziellen "industrielle Sortierverfahren". Bzw. die hier beschriebenen werden auch dort eingesetzt.

[China]: Ich halte es für sinnvoll, das im Artikel zu erwähnen. Betrifft immerhin >1 Mrd. Menschen auf der Welt. Technisch gesehen ist es ja simpel: "Bilde das Schriftzeichen auf Zahl_der_Striche ab; sortiere gemäß diesem Integer-Wert".

--arilou (Diskussion) 12:04, 16. Okt. 2017 (CEST)

1. Danke
2. Doch, Sieben, ein mechanisches Verfahren. Magnetische Trennung von Müll etc. Der Artikel sollte vielleicht besser heissen 'Sortierverfahren (Informatik)' Gruß AVS (Diskussion) 16:33, 16. Okt. 2017 (CEST)

'Sieben' ist eine parallele Ausführung eines nicht-vergleichsbasierten Sortierverfahrens, z.B. Bucketsort, mit Sortierschlüssel "größer_als_Siebmasche" (also 1 bit). Magnetisches Mülltrennen ist gleichartig.

Aber ich stimme dir zu, dass in der Umgangssprache (und auf selbiger soll die Wikipedia ja aufbauen) auch solche "physikalische Unterscheidungs- und Ordnungsprozesse" als 'Sortierverfahren' bezeichnet werden.

Hm, als eine sinnvolle Artikelstruktur würde ich vorschlagen:

Sortierverfahren als Weiterleitung auf Sortierverfahren (Begriffsklärung), dort aufgeführt Sortierverfahren (Informatik) (Umbenennung von hiesigem Artikel) sowie Sortierverfahren (physikalisch). 'Sieben' kann nicht nur die Industrie; als Kriterium kann jede messbare physikalische Eigenschaft einer Objektmenge verwendet werden.

--arilou (Diskussion) 11:43, 17. Okt. 2017 (CEST)

1. Ja.
2. Es müssten sich weitere Kern-Mitarbeiter des Artikels äussern. Sonst könnte das Disk.-Klima, das erfreulich (Ausnahme!) ist, gestört werden. . Gruß AVS (Diskussion) 16:29, 17. Okt. 2017 (CEST)

Nun, es hat sich 2 Jahre lang sonst niemand geäußert - also liegt's nur an uns, das umzusetzen. Ich war mal so frei, einen Artikel "Technische Sortierverfahren" anzulegen und mittels WP:BKH zu verlinken. --arilou (Diskussion) 08:51, 2. Sep. 2019 (CEST)

Hinzufügen von unteren Schranken

In dem Artikel wird bisher an allen Stellen nur von oberen Schranken (O(x)) geredet. Implizit werden diese aber von den Lesern des Artikels vermutlich immer als obere und untere Schranken (Theta(n)) wahrgenommen. Ich würde demnächst den Artikel komplett auf Theta umstellen, um deutlich zu machen wo eine obere Schranke auch tatsächlich eine untere Schranke ist und wo nicht. Aktuell befeuert der Artikel die (falsche) Wahrnehmung, dass O(x) mehr als eine obere Schranke beschreibt. Gibt es dazu Einwände? --Cerotidinon (Diskussion) 03:53, 31. Aug. 2019 (CEST)

Hm; ich denke, dass "Best Case", "Average Case" und "Worst Case" ins Deutsche zu übersetzen der bessere Weg ist, die Artikel-Verständlichkeit zu erhöhen: "Günstigster Fall", "Normalfall", "Ungünstigster Fall" - ggf. inkl. englischer Bezeichnung in Klammern.

(Moment, das mach' ich gleich mal im Artikel!) ... done

Die O-Notation ist weit verbreitet und vielen Lesern geläufig. Von ihr abzuweichen würde ich gerne vermeiden, wenn irgend möglich.

--arilou (Diskussion) 08:34, 2. Sep. 2019 (CEST)

Ich denke, da hast du mich falsch verstanden. Es geht nicht darum, ob man im besten oder im schlechtesten Fall ist, sondern ob die angegebene Laufzeit eine untere oder eine obere Schranke darstellt. Die O-Notation umfasst nicht nur O, sondern auch Omega und Theta. Dass man O am Häufigsten sieht liegt daran, dass man häufig besonders daran interessiert ist was eine obere Schranke für die Laufzeit ist, also "wie schnell" etwas geht. Gerade bei Sortieralgorithmen ist es aber auch enorm relevant zu wissen wie untere Schranken sind, also "wie langsam" etwas ist.

Ein Beispiel zur Veranschaulichung - Wenn ich einen O(N)-Algorithmus habe und einen O(N^2)-Algorithmus, dann heißt das nicht, dass der erste Algorithmus schneller ist als der zweite. Ich sage nur der erste Algorithmus braucht höchstens N Schritte und der zweite Algorithmus höchstens N^2 Schritte. Es kann aber trotzdem sein, dass der zweite Algorithmus eigentlich nur log(N) Schritte benötigt. Wenn ich statt O das Theta benutze, dann bedeutet dass auch, dass der Algorithmus mindestens so viele Schritte braucht. --Cerotidinon (Diskussion) 16:31, 2. Sep. 2019 (CEST)

Ähm - die O-Notation beschreibt weder eine untere noch eine obere Schranke, sondern das asymptotische Verhalten für große n.

Und dann ist ein O(n)-Algorithmus sehrwohl schneller als ein O(n²). (Natürlich muss man noch prüfen, was im konkreten Fall "groß" für n bedeutet - mitunter gelten 10.000 Elemente noch als "kleines Problem"...)

--arilou (Diskussion) 16:58, 2. Sep. 2019 (CEST)

Nachtrag: Im Artikel kommt der Begriff "obere Schranke" überhaupt nicht vor! Eine untere Schranke wird explizit behandelt, und dort auch nicht mit O-Notation, sondern exakter.

Also: Wo soll der Artikel genau wie verbessert werden?!?

--arilou (Diskussion) 17:01, 2. Sep. 2019 (CEST)

Das ist beides falsch. O-Notation beschreibt immer und ausschließlich (asymptotisch) obere Schranken. Siehe Landau-Symbole#Definition. Der Artikel erweckt leider genau den falschen Eindruck, den auch du von der O-Notation hast, nämlich, dass das große O eine asymptotisch untere Schranke beschreiben würde. So könnte man zum Beispiel denken, dass der Average Case von Combosort genauso schlecht ist, wie der Average Case von Bubble Sort. Das ist allerdings (vermutlich) nicht der Fall. Es wurde lediglich bisher keine bessere obere Schranke bewiesen. Diese Art von Missverständnissen würde ich mit einer Änderung gerne vermeiden. --Cerotidinon (Diskussion) 18:01, 2. Sep. 2019 (CEST)

Vermutlich müsste bei den meisten Angaben im Artikel das Zeichen 'O' durch das Zeichen '$\Theta$' ersetzt werden. Das ist doch so ziemlich alles, worauf deine Kritik hinausläuft, oder?

--arilou (Diskussion) 08:49, 3. Sep. 2019 (CEST)

Exakt! (Natürlich nur dort, wo es auch stimmt, das ist hier aber an den meisten Stellen der Fall) --Cerotidinon (Diskussion) 10:59, 3. Sep. 2019 (CEST)

Mergesort Speicherverbrauch

Im Hauptartikel von Mergesort steht drin, dass Mergesort den Speicherverbrauch O(n) = n hat, hier in der Tabelle steht drin, dass Mergesort keinen zusätzlichen Speicher braucht - was stimmt denn jetzt? "kein In-place"

Ich würde sagen je nach Implementierung, dennoch sollten die beiden Artikel nicht widersprüchlich sein.

MFG Steffen (nicht signierter Beitrag von SternBogen (Diskussion | Beiträge) 13:12, 3. Nov. 2019 (CET))

Wie im Artikel unter Mergesort#Sonstiges angedeutet, lässt sich Mergesort nur dann „inplace“ implementieren, wenn die Records in verketteten Listen vorliegen. Dann kann der ohnehin für die Ketten vorhandene $\Theta (n)$-Speicherplatz zum Aufschreiben der geänderten Reihenfolge benutzt werden. Wenn es ein Array von Zeigern gibt, die auf die Records zeigen, kann man in einem vorbereitenden Durchlauf den $\Theta (n)$-Speicherplatz dieser Zeiger möglicherweise benutzen, um diese Zeiger in Kettenzeiger abzuändern. Liegen die Records aber einfach so im Speicher herum, dann kann man die Ordnung nur durch Transporte festhalten. Und für die letzte Mergephase braucht man wohl Platz in der Größenordnung der Hälfte der Records.
Insofern lässt sich mMn nicht viel mehr als das recht schwache „je nach Implementierung“ aussagen. --Nomen4Omen (Diskussion) 15:53, 3. Nov. 2019 (CET)

Landau-Symbole

Dieser Artikel könnte meiner Meinung nach immer noch ein wenig bezüglich der Landau-Notation verbessert werden. Beim Abschnitt "Nicht-vergleichsbasiertes Sortieren" finden sich z.B. folgende Formel: Zeit: O(n + l), wobei l ein Skalar ist und nicht von n abhängt. Das ist zwar nicht falsch, man könnte aber auch genau so gut O( n + 13403294 - π^30) schreiben, oder eben O(n). Dasselbe gilt für O(n \cdot l), was genau dasselbe wie O(n) ist, wenn l ungleich 0. Das sollte man ändern, um nicht ein falsches Verständnis der oberen Abschätzung zu suggerieren. Des Weiteren sollte O wo immer möglich durch Θ ersetzt werden, da Θ echt mehr Informationen enthält als O. Das ist z.B. bei O(1) und O(n) problemlos möglich, es finden sich bestimmt genug Quellen, dass jedes (vergleichsbasierte) Sortierverfahren in Ω(n) liegt.

Des Weiteren ist mir insbesondere nicht klar, was O(n) .. O(n²) bei Flashsort bedeuten soll. Dieser Ausdruck findet sich auch im Originalartikel nicht wieder.

Falls es keine Einwände gibt, würde ich diese Änderungen gerne demnächst durchführen. --PhilologistLaGr (Diskussion) 22:37, 24. Jan. 2020 (CET)

O(n + l) = O(n), wenn l konstant ist, aber O(n + l) = O(l), wenn n konstant ist. M.a.W.: wenn die Variationsbreite von l riesig ist, dann ist es ein Fehler, diese zu unterdrücken. --Nomen4Omen (Diskussion) 18:26, 25. Jan. 2020 (CET)

Danke für die Klarstellung. 1. Ich habe in meinem Kommentar irrtümlich O(n+l) geschrieben, es ist aber O(n+k). Auch verstehe ich, wie man auf diese Notation kommt, wenn man den in diesem Artikel gelisteten Pseudocode betrachtet. Allerdings kann man sich vielleicht so weit aus dem Fenster lehnen, dass jede Implementierung die Anzahl Buckets nicht größer als die Anzahl an zu Sortierenden Daten wählt. Dann gilt $k\leq n$ und dann wäre Bucketsort in $\mathrm {O} (n+n)=\mathrm {O} (n)$ Außerdem bleibt das Problem, dass dieses Detail nicht im Artikel zu Bucketsort selbst auftaucht.

Der Faktor l bei O(n · l), wobei l die (positive) maximale Schlüssellänge ist, kann man sich aber wirklich schenken, das ist nicht, wofür die Landau-Notation gut ist.--PhilologistLaGr (Diskussion) 10:19, 29. Jan. 2020 (CET)

Die Laufzeit hängt laut Bucketsort#Komplexität von der Qualität der Funktion $f$ ab, die wiederum stark von den gegebenen Schlüsseln abhängt. Abgesehen von der Problematik, ein gutes, monotones $f$ zu finden, kann es theoretisch passieren, dass dieses bei einer ungünstigen Eingabe alle Schlüssel in ein und denselben Topf wirft, so dass in der ersten foreach-Schleife überhaupt nichts geleistet wird. Deshalb kann es vorteilhaft sein, die Anzahl $k$ der Buckets relativ groß $k\gg n$ zu wählen, damit die erste foreach-Schleife die Schlüssel etwas auseinanderzieht.

Ist $l$ die Anzahl der Stellen des längsten Schlüssels, dann wird interessanterweise diese bei den vergleichsbasierten Verfahren als beschränkt angesehen (und ignoriert), obwohl jeder Vergleich einen asymptotischen Aufwand von ${\mathcal {O}}(l)$ erfordert.

übrigens ist bei den vergleichsbasierten Verfahren die Ordnungsrelation allermeist auf recht einfache Weise gegeben, also auch das Laufzeitverhalten leichter und robuster abzuschätzen.

Du hast Recht, dass man in großer Gefahr ist, sich selbst zu belügen. Z.B. zählt man bei der Registermaschine den Zugriff auf ein Register als 1, obwohl schon die Adresse eines Registers asymptotisch die Länge ${\mathcal {O}}(\log({\rm {{AnzahlderRegister}))}}$ haben muss und diese bei jedem Zugriff dekodiert werden muss.

Andererseits sind vermutlich alle Sachen, die im Weltall so existieren, endlich. Also beschränkt und in ${\mathcal {O}}(1)$. Insofern kommt es bei der Landau-Notation sehr darauf an, welche Abhängigkeit man ausdrücken möchte.

--Nomen4Omen (Diskussion) 12:41, 29. Jan. 2020 (CET)

Ich störe mich vor allem daran, dass die Landau-Notation dafür gedacht ist, den wesentlichen Faktor für die Laufzeit zu bestimmen. Es sollen eben nicht, danke für das Beispiel, die Zugriffsdauer auf das Register oder ähnliche, nicht weiter wesentliche Teilprobleme versteckt werden. Außerdem ist mir noch nie eine Landau-Notation mit zwei Variablen über den Weg gelaufen, sodass ich zuerst irrtümlich annahm, $\mathrm {O} (n+k)$ sei eine Funktion in n und mit Konstante k.

Darüber hinaus wird bei der Berechnung des Average Cases (im Bucket-Sort-Artikel) die Annahme getroffen, dass die Daten normalverteilt sind und man das im Vorhinein weiß. Dann dürfte sich das Ganze wieder zu $\mathrm {O} (n)$ herunterkürzen.

Zum letzten: Das kommt jetzt darauf an, ob es eine Bijektion zwischen dem, was es auf der Welt gibt, und irgendeinem mathematischen Konstrukt gibt. Falls ja, dürftest du Recht haben, falls nein, wohl nicht. Aber das wäre ohnehin erst einmal zu zeigen ... --PhilologistLaGr (Diskussion) 09:10, 31. Jan. 2020 (CET)

Es ist überall in der Informatik-Literatur üblich, bei Bucketsort u.ä. O(n+k) zu schreiben (oder eben Θ), da es für diese Sortierverfahren nunmal wesentliche Aspekte für die Laufzeit gibt, die nicht von n abhängen, sondern von einer zweiten Größe. Wenn ich n=30.000 Werte sortieren soll vom Typ unsigned_int_32, also k=4 Milliarden Buckets habe, dann ist O(4 Milliarden) eben wichtiger als O(30.000). Es kann bei diesen Algorithmen weder n noch k vernachlässigt werden.

--arilou (Diskussion) 12:03, 26. Feb. 2020 (CET)

Beweis der unteren Schranke für vergleichsbasiertes Sortieren

Hallo, der Beweis für die untere Schranke für den Average Case finde ich nicht sonderlich gelungen. Schon die Annahme $k_{1}+k_{2}=k$ kann ich für den Fall $k_{1}\neq k\land k_{2}\neq k$ nicht recht nachvollziehen. An dieser Stelle würde sich wohl auch ein strikt induktiver Beweis mehr anbieten. Ist das nur meine Meinung? --PhilologistLaGr (Diskussion) 22:58, 5. Feb. 2020 (CET)

Speicherbedarf von Timsort

Ich habe aktuell keine Zeit es zu bearbeiten, aber braucht Timsort nicht extra Speicherplatz? Vgl. englischer Artikel. Felix D. (Diskussion) 11:29, 5. Mär. 2020 (CET)

Bubblesort (Worst-Case) / Falsche Formel

Bei Bubblesort ist die Formel für den Worst-Case als O(n²) angegeben. Ich denke richtig wäre hier O(n²/2).

Grund für meine Hypothese:

Mit n² berechnet man eine Fläche, also Anzahl Elemente * Anzahl Elemente. Man bekommt also eine quadratische Fläche, deren Kanten der Anzahl von n entsprechen. Weil sich bei Bubblesort jedoch bei jedem Durchlauf durch das Array die Anzahl der Schritte um 1 reduziert, sieht die Anzahl grafisch wie ein Quadrat aus, das von einer Ecke zur schräg gegenüberliegenden Ecke in zwei Teile geteilt wurde. Daher muss O = n² / 2 sein. --77.21.186.2 11:41, 27. Jun. 2021 (CEST)

Nach der Definition der bigO Notation ist O(n²) = O(n²/2), weil es nur auf das "Asymptotische" ankommt und solche konstante Faktoren dabei weggeworfen werden. Wenn du Genaueres angeben möchtest (was manche Autoren machen!), dann kannst du von der maximalen Anzahl der Vergleiche (= n²/2 oder = n(n−1)/2) sprechen und lässt das O weg. –Nomen4Omen (Diskussion) 12:13, 27. Jun. 2021 (CEST)

Ok --77.21.186.2 16:13, 27. Jun. 2021 (CEST)