Diskussion:Sortierverfahren

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 Signatur und Zeitstempel oder --~~~~.

Hinweise

Automatische Archivierung
Auf dieser Seite werden Abschnitte 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.

--arilou (Diskussion) 15:46, 14. Mär. 2018 (CET)

Quicksort - Speicherverbrauch[Quelltext bearbeiten]

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)

Zum Quicksort:[Quelltext bearbeiten]

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[Quelltext bearbeiten]

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[Quelltext bearbeiten]

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[Quelltext bearbeiten]

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[Quelltext bearbeiten]

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?[Quelltext bearbeiten]

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[Quelltext bearbeiten]

Da steht: Für das topologische Sortieren gibt es Algorithmen, deren Laufzeit von der Anzahl der Beziehungen abhängt. Mir erscheint das sehr ungewöhnlich, daß als Anzahl der Beziehungen ein Landau-Symbol angegeben wird. Müßte da nicht 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 abhängig ist und asymptotisch beträgt. — Toshikitalk 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 . Ähm, bei "gewöhnlicher Sortierung"? Das ist doch auch falsch, da gehört das bekannte hin, oder?--Bimaterist 22:40, 19. Sep. 2011 (CEST)

ist in der Tat fragwürdig. Da eine topolgische Sortierung prinzipiell vergleichsbasiert stattfinden muss, halte ich Deine Angabe für sinnvoller. — Toshikitalk 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?[Quelltext bearbeiten]

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[Quelltext bearbeiten]

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 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[Quelltext bearbeiten]

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

 

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[Quelltext bearbeiten]

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[Quelltext bearbeiten]

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[Quelltext bearbeiten]

@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[Quelltext bearbeiten]

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 die Ordnung der Sortierschlüssel, dann ist immer . 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 , dessen Ergebnis ja total anders aussieht als , nämlich .
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 . 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)

Sortierung im chinesischen Wörterbuch[Quelltext bearbeiten]

Struktur für mehrere Artikel / Lemma: (Informatik)[Quelltext bearbeiten]

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)