Diskussion:Sortierverfahren/Archiv/1

Diese Seite ist ein Archiv abgeschlossener Diskussionen. Ihr Inhalt sollte daher nicht mehr verändert werden. Benutze bitte die aktuelle Diskussionsseite, auch um eine archivierte Diskussion weiterzuführen.

Um einen Abschnitt dieser Seite zu verlinken, klicke im Inhaltsverzeichnis auf den Abschnitt und kopiere dann Seitenname und Abschnittsüberschrift aus der Adresszeile deines Browsers, beispielsweise

[[Diskussion:Sortierverfahren/Archiv/1#Thema 1]]

oder als Weblink zur Verlinkung auVorlage:SSerhalb der Wikipedia

https://de.wikiup.org/wiki/Diskussion:Sortierverfahren/Archiv/1#Thema_1

Pigeonholesort

Pigeonholesort ist wohl ein alternativer Name für Countingsort. Da er extrem ungebräuchlich ist, habe ich den Verweis entfernt. Der Artikel sollte meiner Meinung nach gelöscht werden.

scheint:

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:11, 17. Feb. 2014 (CET)

Jaja, die Bequemlichkeit

Für das Verständnis der mathematisch Ungebildeten (und die Bequemlichkeit der Halbgebildeten) schlage ich vor, in die Vergleichstabelle für n zusätzlich einen konkreten Wert (z.B. 1000) einzufügen. Alternativ vielleicht ein Applet bei dem der Leser n selber definiert. Meinungen dazu? 217.237.150.35 13:52, 13. Apr. 2007 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:12, 17. Feb. 2014 (CET)

Fehler in der Einleitung schon im ersten Satz

Im ersten Satz ist der Begriff Menge falsch angewendet. Die Elemente einer Menge haben keine Reihenfolge; demzufolge können sie auch nicht sortiert werden. Sie können allenfalls (z.B. aufgrund einer Ordnungsrelation) in einer bestimmten Reihenfolge angeordnet werden; eine solche Anordnung der Elemente ist aber nicht dasselbe wie die Menge der Elemente, sondern allenfalls ein Bild davon. Eine solche Anordnung wird üblicherweise als Liste bezeichnet; ein Array ist lediglich eine mögliche Darstellung einer Liste; der letzte Satz des Absatzes ist nahezu ein Salto mortale: "Die Folge (jetzt plötzlich!! — N.A.) liegt üblicherweise in Form eines Arrays vor." — Nope! Dieser Satz ist, mit Verlaub gesagt, so falsch, dass nicht einmal sein Gegenteil wahr ist ...

Ich versuche, das entsprechend umzuformulieren. — Nol Aders 03:46, 8. Jun 2005 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:17, 17. Feb. 2014 (CET)

Satz unverständlich

In [Sortierverfahren->Sektion 1] finde ich den Satzteil "[...]wenn von vornherein (unabhängig von den zu sortierenden Daten) feststeht, die Werte an welchen Positionen miteinander verglichen und gegebenenfalls vertauscht werden[...]" unverständlich; möchte aber die Aussage nicht verfälschen. Falls jemand weniger Bedenken hat würde ich etwas wie "an welchen Positionen die Werte miteinander verglichen [...] werden [...]" vorschlagen. --Wizzar 19:58, 1. Mär 2005 (CET)

doch selbst gemacht --Wizzar 20:20, 1. Mär 2005 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:17, 17. Feb. 2014 (CET)

Beweis der unteren Schranke

Der Beweis wurde von Benutzer:MartinWeiglhofer und einem anonymen User in einem eigenen Artikel erstellt und später von mir hierher verschoben. --Pinguin.tk 11:01, 24. Jun 2004 (CEST)

ich finde, der Beweis der unteren Schranke passt hier nicht herein, da der Artikel lediglich einen Überblick über Sortierverfahren bieten soll. Daher besser wieder in einen eigenen Artikel zurück verschieben

na, der Artikel soll ja nicht nur eine Linkliste zu den diversen Sortierverfahren sein, sondern auch inhaltlich was zu bieten haben. Warum findest Du, dass der Beweis hier nicht rein sollte? Wenn er nur von diesem Artikel aus verlinkt ist (so war es zuvor), ist das Auslagern IMHO nicht besonders sinnvoll. Zumal vielleicht nicht so viele Leute dem Link folgen, um den Beweis extra zu lesen, aber wenn er hier schon mal steht, schauen ihn bestimmt ein paar mehr an. Also mehr Informationsvermittlung. --Pinguin.tk 01:33, 28. Jun 2004 (CEST)

Sortierverfahren sind eines der zentralen Themen der Informatik. Das Gebiet ist daher so umfangreich, dass der erste Artikel nicht mehr leisten kann, als alle Unterthemen zu verlinken. Der Beweis der unteren Schranke ist zwar wichtig, aber sicher nur für wenige Leser interessant. Daher sollte er in einen eigenen Artikel.

Ich würde den Teil-Beweis, daß Bäume logarithmische Tiefe haben durch einen Link zu den Graphentheoretikern ersetzen. Das macht die Sache dann viel übersichtlicher. Ansonsten vermisse ich noch die Inversionen. -- MlaWU 22:40, 23. Feb 2005 (CET)

Als ich das erste Mal auf diese Seite kam war ich auf der Suche nach weiterführenden Informationen zu Radixsort und war zunächst sehr verblüfft, dass dieser Algorithmus nicht aufgelistet war; ich fand ihn dann per Textsuche. Der Inhalt des Beweises ist zudem sehr speziell und schreckt alle Nichtinformatiker vom Weiterlesen ab. Daher sollte der Beweis an das Ende des Artikels verschoben werden.--JDHenning 11:17, 27. Jan. 2010 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:19, 17. Feb. 2014 (CET)

was wird gezählt?

Die Anzahl welcher Operationen wird beim Aufwand angegeben? Ich kenne das so, daß man die Anzahl der Vertauschungen zählt. Damit wäre aber zum Beispiel Bubblesort im besten Fall in O(1) enthalten und nicht in O(n). -- MlaWU 14:42, 21. Aug 2005 (CEST)

Jo, du hast recht. Ich habe das jetzt mal ergänzt --Spongo 14:23, 22. Aug 2005 (CEST)

Veto. Wenn die (minimale/maximale) Anzahl der Zugriffe O_z(n) ist, die der Vertauschungen aber O_v(1), so ergibt sich der Aufwand aus nach dem Maximum der Einzelordnungen. Dabei gilt wie üblich O(1)<O(log)<O(n)<O(n^2)<O(exp). Also gilt

O=max(O_v,O_z)

und damit

minmaler Aufwand = max(O(1),O(n))=O(n)

für Bubblesort --Hubi 10:04, 23. Aug 2005 (CEST)

Aber nur, wenn man die Zugriffe zählt. Soweit ich mich erinnere, haben wir damals immer nur die Vetauschungen gezählt und die sind bei Bubblesort gleich der Anzahl der Inversionen, mithin 0 im besten Fall. Aber momentan steht ohnehin beides in der Tabelle. (Wobei O(n-1) natürlich eine etwas merkwürdige Angabe ist) -- MlaWU 12:58, 23. Aug 2005 (CEST)

O(n-1) ist nicht so wirklich eine Komplexitätsklasse, aber ich wollte das etwas genauer angeben. Meinetwegen kann das zu O(n) geändert werden. -- Spongo 01:30, 24. Aug 2005 (CEST)

Was willst du denn genauer (!) angeben? Wenn du die exakte Anzahl vergleiche angeben willst, warumg schreibst du nicht einfach n-1. Eigenerfindungen sind hier kontraproduktiv. Wenn man sich mit Komplexitätsklassen beschäftigt, sollte man schon innerhalb der Notation bleiben. Hubi 12:14, 24. Aug 2005 (CEST)

zu "Was willst du denn genauer (!) angeben?" siehe mein Kommentar unten! Meinste ich habe mir das ausgedacht? Selbst O(1 + 2n + n/2 +80*n²) wäre nach Definition richtig, nur sehr unüblich. Deshalb sage ich auch, dass es geändert werden kann. Aber sowas wie O(n²/2) ergibt Sinn... -- Spongo 14:34, 24. Aug 2005 (CEST)

Meines Erachtens wird bei O(x) ermittelt, wie das Zeitverhalten ist, wenn ich von grossen Feldern auf noch viel größere Felder übergehe, d. h. ich weiss etwa dass ein sortiertes Feld bei Bubblesort minimaler Aufwand bedeutet und ermittle 100 ms bei sagen wir Feldgröße 1000000. Die 100 ms sind durch das Durchsuchen begründet, da ja keine Vertauschungen auftreten. Frage: wie lange braucht der Bubblesort hier etwa bei einem 1000fach größeren, sortierten Feld? Da minimaler Aufwand O(n) ist, nicht O(1), bedeutet dies jetzt 100 Sekunden, oder irre ich da? Gezählt wird immer das Maximum. Hubi 13:05, 23. Aug 2005 (CEST)

Es wird hier eine Unterscheidung gemacht, zwischen Vergleichsoperationen und Kopieroperationen für die Vertauschungen. Was für eine Aussage macht denn O(n) ? Wichtig ist es bei Bubble-, Insertion- und Seletionsort gerade das zu unterscheiden, je nachdem wie lange mein Programm für ein Vergleich bzw. ein Tausch benötigt. Für die Komplexitätsanalyse ist die reelle Laufzeit auf dem Computer unwichtig. Worauf es hier ankommt sind Aussagen wie: Wenn ich die Datenmenge verdopple, müssen auch doppelt soviele Vergleiche aber immer noch 0 Taschoperationen durchgeführt werden im Best-Case. -- Spongo 01:27, 24. Aug 2005 (CEST)

Nein. Hubi 11:25, 24. Aug 2005 (CEST)

Eine so ausführliche Antwort wollte ich garnicht haben... -- Spongo 14:34, 24. Aug 2005 (CEST)

Nach Definition ist O(n-1) identisch mit O(n) und O(n^2) identisch mit O(n^2/2). Die Angabe O(n-1) bringt also gar nichts. Insbesondere ist O(n^m/10000) in derselben Klasse wie O(n^m). Das ist doch genau der Trick der Quantoren. Zitat aus dem Artikel: In der Komplexitätstheorie werden Q. vor allem dazu verwendet, das Zeitverhalten oder den Speicherbedarf von Algorithmen zu bestimmen. Na also. Auf Vergleiche im Verhätlnis Vertauschungen kommt es nicht an. Nehmen wir an, ein Algorithmus benötigt nur ein 10000stel der Zeit zum Vergleichen wie zum Vertauschen, jedoch beides mal linear mit der Größe. Er gehört zur Komplexitätsklasse O(n/10000)+O(n) und damit zu O(n). Jetzt nehmen wir an, er habe ein kubisches Zeitverhalten für die Vergleiche, lineares für die Vertauschungen, wobei immer noch die Vergleiche 10000 mal schneller gehen. Das Zeitverhalten ist dann O(n^3/10000)+O(n) und damit O(n^3). Dies weil bei sehr großen Datenmengen das Zeitverhalten immer noch nur durch die Vergleiche bestimmt wird! Darum geht's --Hubi 17:54, 24. Aug 2005 (CEST)

Davon spreche ich doch auch. Wenn ich weiß, dass mein Programm niemals mehr als z.B. 50 Daten sortieren muss und weiß wie viel ein Vergleich und Tausch an Zeit braucht, kann ich aber abwägen um für n < 50 den optimalen Algo auswählen. Es wäre (wie im oberen Bsp.) n^3/10000 für n < 50 immer noch klein im Vergleich zu den Kopier"kosten" für dieses n. Gerade dafür wollte ich die Unterscheidung in Vergleiche und Kopieraktionen haben. Dabei kann es auch durchaus wichtig sein zwischen n^2 und n^2/2 zu unterscheiden. Klar ist das für Unendlich O(n^3), aber das macht für solche Probleme keine große Aussage. Dass O(n^3/10000)+O(n) = O(n^3) gilt erkennt man ja auf den ersten Blick...

Ein Kompromiss wäre hier die Klasse hinzuschreiben und darunter die Aufsplittung in "genauen" Vergleich-/Tauschaktionen. Nur wirkt dann die Tabelle etwas überladen. -- Spongo 19:04, 24. Aug 2005 (CEST)

Das wäre meiner Meinung nach aber besser. Die Quantoren beschäftigen sich nun mal ausschliesslich mit dem limes nach unendlich. Daher sollte man hier nicht davon abweichen, wenn auch O(n^2/4) mehr Information enthält. Vielleicht in Klammern die Zahl dahinterschreiben, aber nicht ins Argument. --Hubi 19:11, 24. Aug 2005 (CEST)

Also etwa so?

Sortierverfahren	Best-Case	Average-Case	Worst-Case	Stabil	Zusätzlicher Speicherbedarf (in-place-Verfahren?)
Bubblesort (Vergleiche) (Kopieraktionen)	O(n) O(n-1) 0	O(n2) O(n2/2) O(n2/4)	O(n2) O(n2/2) O(n2/2)	ja	-

Es fehlen dann natürlich noch die Unterteilungen bei den anderen Verfahren... -- Spongo 20:48, 24. Aug 2005 (CEST)

Das Hauptproblem ist einfach, daß man den verschiedenen Verfahren in einer Tabelle einfach nicht gerecht werden kann. Vielleicht sollte man den zu treibenden Aufwand wirklich ausführlich hinschreiben. Wird in der Fachliteratur auch so gemacht. Ansonsten möchte ich noch anmerken, daß "O" kein Quantor ist. Quantoren sind "für allle" und "es gibt". -- MlaWU 23:31, 24. Aug 2005 (CEST)

Meines Erachtens bezeichnet O(n-1) diesselbe Funktionsmenge wie O(n+100) und O(n). O(n^2/4) dasselbe wie O(n^2/2) und O(n^2). O ist hier mE einfach die falsche Sprache. Besser wäre:

• wenn eine exakte und kurze Formel angegeben werden kann, dann die ohne O hinschreiben etwa n-1 bei Bubblesort_min.
• wenn die Proportionalität angegeben werden kann (n²/4 + vernachlässigbar), dann ~n²/4 (~ für ungefähr). Wenn nur die Komplexitätsklasse angegeben werdne kann, dann O(n²).

Alles andere erscheint mir fehlerhaft zu sein (in der Notation). --Hubi 09:04, 25. Aug 2005 (CEST)

Etwa so:

Sortierverfahren	Best-Case	Average-Case	Worst-Case	Stabil	Zusätzlicher Speicherbedarf (in-place-Verfahren?)
Bubblesort (Vergleiche) (Kopieraktionen)	O(n) n-1 0	O(n2) ~n2/2 ~n2/4	O(n2) ~n2/2 ~n2/2	ja	-

--Hubi 09:08, 25. Aug 2005 (CEST)

Ok, dann mach ich das mal. Sehe ich das richtig, dass beim Stoogesort eigentlich im Bestcase O(n^2.7) stehen müsste? -- Spongo 11:47, 25. Aug 2005 (CEST)

Ich denke, daß siehst Du richtig. Ich habe aber jetzt mal O(n^2.71) geschrieben, da der genaue Wert für Stoogesort O(n^2.70951129...) ist. Und damit ist Stoogesort nicht in O(n^2.7) enthalten. Merke: Bei Komplexitäten immer aufrunden. -- MlaWU 14:08, 25. Aug 2005 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:24, 17. Feb. 2014 (CET)

Countingsorts Platzkomplexität

Der Speicherbedarf / Platzkomplexität von Countingsort ist derzeit als "-" angegeben - also "kein Speicherbedarf". Im Artikel zu Countingsort steht aber (gut erklärt), der Speicherplatz betrüge O(N+M). --Abdull 14:32, 8. Mär 2006 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:26, 17. Feb. 2014 (CET)

Doppelte Verneinung?

Der folgende Absatz ist nicht klar formuliert:

Und man unterscheidet auch zwischen natürlichen Sortierverfahren, die bei vorsortierten Daten nicht langsamer arbeiten als bei unsortierten Daten, und solchen, die es nicht tun

Was denn jetzt? -- Genesis2093 17:43, 6. Mai 2006 (CEST)

Wo ist das Problem? "die dies nicht tun" wäre zwar schöner, aber ansonsten ist das doch richtig. -- MlaWU 23:52, 8. Mai 2006 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:27, 17. Feb. 2014 (CET)

Laufzeit Stupidsort

Stupidsort wird weitergeleitet auf Bogosort, hat in der Übersicht aber eine andere Laufzeit. Sollte auch gefixt werden.

Wenn Stupidsort und Bogosort dasselbe sind, dann sollte es auch bloß einmal vorkommen. Das einfachste wäre, die untere Zeile zu entfernen und bei Bogosort "oder Stupidsort" hinzufügen. Allerdings sollte vorher sichergestellt sein, dass es wirklich zweimal dasselbe, der Redirect also gerechtfertigt ist.

PS: Du hast die Unterschrift vergessen (--~~~~) --Ce 18:32, 8. Mai 2006 (CEST)

Der Fehler ist mir auch aufgefallen, Stupidsort sollte einach hinter Bogosort erwähnt werden

Wieso ändert es dann niemand? Ich mach mal... --Malte 21:41, 19. Sep 2006 (CEST)

Zwei Zeilen, die zudem nicht als Dubletten erkennbar sind, räumen diesem akademischen Scherz doch ein wenig zuviel Platz ein. Wenn man die Anzahl der Treffer als Maß anlegt, ist "Bogosort" die bedeutend bekanntere Bezeichnung. Vorschlag: stupidsort komplett aus der Tabelle streichen. --141.84.26.161 08:29, 1. Okt 2006 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:28, 17. Feb. 2014 (CET)

Nicht-vergleichsbasiertes Sortieren

hier müsste mal noch angegeben werde was den mit n,m,k,N,M bezeichnet wird.

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:29, 17. Feb. 2014 (CET)

Weitere Beispiele für Sortieralgorithmen

Ich wär noch dafür, Minimum- bzw. Maximum-sort in die Übersicht einzufügen, vorrausgesetzt, diese Beiträge existieren bereits

   gibt es doch schon: Selectionsort

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 09:29, 17. Feb. 2014 (CET)

Kopieraktionen von InsertionsSort im BestCase

Ich bin mir nicht sicher, aber nach meiner Meinung beträgt die Anzahl der Kopieraktionen bei Insertionsort im Best Case 0. Denn wenn die Liste schon sortiert ist, muss auch nichts umgespeichert werden. Selbst wenn man Insertionsort Out-Of-Place implementiert kommt man nur auf n Kopieraktionen und nicht auf 2n

So ist es, im Best Case muss nichts getauscht werden. Die Anzahl der Vergleiche ist dann n-1. Bei Selection Sort der selbe Fehler. Ich änder das mal. 213.54.138.163 20:09, 23. Mai 2007 (CEST)

Verständnisfehler, scheint öfter vorzukommen.

Es geht nicht um die "Anzahl der Kopieraktionen" oder "Anzahl der Vergleiche", sondern um die Zeitkomplexität.

Die Reduktion auf "Anzahl der Vergleiche" oder "Anzahl der Kopieraktionen" resultiert aus der Annahme, das v.a. diese Aktionen Zeitbedarf verursachen. Sofern da etwas auf =0 fällt, ist selbstverständlich das Andere noch zu betrachten (eigentlich alles Andere).

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

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:26, 17. Feb. 2014 (CET)

Untere Schranke für vergleichsorientierte Sortieralgorithmen

Der recht fundamentale Beweis über die untere Schranke für vergleichsorientiere Sortieralgorithmen geht meiner Meinung nach in der Fülle der Informationen (auf dieser Seite) unter. Wäre es nicht besser eine Eigene Seite "Sortierbaum" anzulegen und den Beweis dort etwas ausfürlicher zu erleutern? Über die Suche ist der Beweis soweit ich das sehe gar nicht auffindbar.

? Annahme:

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:27, 17. Feb. 2014 (CET)

Shellsort - Komplexität

Dort steht bei Average Case eine Komplexität, die höher ist als die, die im Worst Case notiert ist. Ab einer bestimmten Anzahl von Elementen ist nämlich n×ld(n)² besser als n^1,25.

Wenn man allerdings dazu schreiben würde, welche Anzahl an Elementen man sortieren möchte, wäre es eindeutig. Ansonsten müssten Average und Worst Case vertauscht werden, da man im Normalfall von n→∞ ausgeht.

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:29, 17. Feb. 2014 (CET)

Bubblesort

Bubblesort ist irgendwie syntaktisch falsch, es wird eine Latex-Formel (?) statt der lesbaren Form angezeigt -- bitte reparieren!! Ebenso bei anderen Algorithmen ... einige Angaben fehlen komplett (!) --> sollte dringend ausgebessert werden

Das ist ein, seit ein paar Tagen, bekannter Bug: Benutzer_Diskussion:Raymond#tex-bug? \varkappa wird nicht gerendert. -- Merlissimo 12:51, 21. Nov. 2008 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:29, 17. Feb. 2014 (CET)

Die Tabelle

1. Was heißt rekursiv? Es ist z.B. überhaupt kein Problem, den Select-Sort rekursiv zu definieren, andererseits ist ein iterativer Merge-Sort auch kein Problem, man braucht noch nicht einmal einen Stack. 2. Was bedeuten die leeren Felder? Das sollte vllt. angemerkt werden... --Chricho 20:07, 11. Apr. 2010 (CEST)

Zu 1: Stimme zu, die Spalte ist Quatsch. --Zahnradzacken 19:02, 16. Okt. 2010 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 10:47, 17. Feb. 2014 (CET)

externes Sortieren

Kann es sein, dass die deutsche WP darüber noch gar nichts schreibt? Oder bin ich nur zu blöd, es zu finden? Siehe en:external sort. Ist "externes Sortieren" dafür die übliche dt. Bezeichnung? --RokerHRO 09:20, 25. Sep. 2010 (CEST)

Ich halte diese doch grundsätzliche Unterscheidung (speicherinterner Sort vs. Sort von externen Daten und ggf. mit externem Workspeicher) ebenfalls für bedeutend und vermisse entsprechende Aussagen. Möglicherweise benutzen solche Externverfahren dann wieder bestimmte interne Algorithmen, doch das sollte zweitrangig sein.
Von Interesse hielte ich auch die Information, für welche Systemplattform(en) die jeweiligen Verfahren verfügbar sind und ggf. als Teil welcher Software-Produkte.--VÖRBY 19:20, 26. Jul. 2011 (CEST)

jetzt:

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 12:10, 17. Feb. 2014 (CET)

Unsinnige Sortierverfahren

Hallo, ich hatte die Überschrift 'Unsinnige Sortierverfahren' auf 'fett' geändert - weil es da nur ein Teilkapitel gab. Oder wäre es besser gewesen, auch andere Textteile als Teilabschnitte zu führen? Unabhängig davon: Könnte jemand vielleicht noch nachtragen, warum diese Verfahren unsinnig sind oder so genannt werden? Danke. --VÖRBY 17:28, 26. Jul. 2011 (CEST)

Nee, also wie ich die Richtlinien kenne, soll man Fettschrift wirklich nur beim Lemma und bei (Redirect-)Nebenlemmata verwenden, hier stattdessen lieber doch eine Überschrift niedrigerer Stufe. --PeterFrankfurt 01:34, 27. Jul. 2011 (CEST)

Guten Morgen. In Hilfe:Inhaltsverzeichnis#Gliederungsebenen steht: „Eine Untergliederungsebene sollte nur angelegt werden, wenn sie mindestens aus zwei Unterabschnitten besteht, es sollte z. B. keinen Abschnitt 2.1 geben, ohne dass es auch einen Abschnitt 2.2 gibt.“ Da im Moment aber auch die 'Fett-Regel' verletzt wird, muss man wohl 'einen Tod sterben'. Wie schon erwähnt könnten evtl. die Texte, in denen Sortiervarianten behandelt werden, als Unterkapitel gestaltet werden; dies möchte ICH jedoch nicht tun (nicht meine 'Kernkompetenz'). Wichtiger wäre mir aber: Es fehlt noch die Erläuterung was "unsinnig" bedeuten soll. Grüße von --VÖRBY 09:04, 27. Jul. 2011 (CEST); aktuell: --VÖRBY 12:28, 27. Aug. 2011 (CEST)

Alternativvorschlag zu Unsinnige Sortierverfahren: Extrem ineffiziente Sortierverfahren oder Auf Ineffizienz optimierte Sortierverfahren — Toshiki 13:05, 27. Aug. 2011 (CEST)

Das Problem mit dem Unterabschnitt lässt sich regeln, wenn man stattdessen einen gesonderten Abschnitt für derartig ineffiziente Verfahren einführt, denn ich frage mich sowieso gerade, ob man die beiden Verfahren (Slow/Bogo) wirklich zu den vergleichsbasierten Algorithmen zählen kann. Bei SlowSort ist die Antwort eindeutig „Ja“, aber BogoSort erzeugt doch nur eine zufällige Permutation und schaut, ob diese dann geordnet ist. Ich würde vorschlagen, dass man einen Abschnitt Ineffizientes Sortieren erzeugt, der Vergleichsbasiertes Sortieren und Nicht-vergleichsbasiertes Sortieren hierarchisch gleichgestellt ist. Das erfordert dann natürlich noch ein paar zusätzliche Erläuterungen, um wirklich eine Überschrift zu verdienen. — Toshiki 13:14, 27. Aug. 2011 (CEST)

Ja, um diesen Text geht es: Wenn das Ganze schon 'unsinnig' ist, warum erwähnt man es dann? Hast du dafür eine plausible Erklärung? Das hierarchische Gleichstellen wäre ja kein Problem, aber möglichst am Ende.--VÖRBY 15:02, 27. Aug. 2011 (CEST)

.Auch wenn die Antwort spät kommt: Unsinnig, weil keinerlei praktische Relevanz. Theoretisch funktionieren sie natürlich.--engeltr 18:56, 27. Okt. 2011 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 12:19, 17. Feb. 2014 (CET)

Quantensort

Den könnte man aus der Liste der unsinnigen Sortierverfahren entfernen. Der Artikel dazu ist auch gelöscht, der war wohl nicth ernstgemeint. Im Artikel hiess es, man bestrahle Bits mit Wellen und dadurch ändern sie Ihren Wert und wenn man Glück hat, erscheinen dadurch Zahlen die genau die vorherigen sind aber sortiert. (nicht signierter Beitrag von 85.2.148.64 (Diskussion) 18:31, 25. Aug. 2011 (CEST))

Nur weil der Artikel Müll war, muss man ja noch nicht gleich den Algorithmus schlechtmachen. Aber ich finde, dass die Average-Case-Laufzeit mit ∞ falsch angegeben ist und dort eigentlich O(n·n!) stehen müsste. Wenn ich es mir recht überlege, kann eigentlich nur BogoSort gemeint sein. Ich lösche den Eintrag. — Toshiki 02:00, 27. Aug. 2011 (CEST)

War schon $O(\infty )$. --engeltr 18:53, 27. Okt. 2011 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 12:20, 17. Feb. 2014 (CET)

Stabil und instabil - Alles nur eine Frage der Anpassung!

Hallo Wikipedianer!

Was mich ein wenig wundert ist, das die Sortierverfahren hier als stabil und instabil bezeichnet werden. Meiner Meinung nach ist das - wenn ich die Definition richtig verstanden habe - Unsinn, weil ein Sortierverfahren grundsätzlich immer beides sein kann. Ein Sortierverfahren gibt schließlich nur die Arbeitsweise vor! Ob der Vergleich der Daten nun stabil oder instabil ist, das wird nur dadurch bestimmt, wie die Daten verglichen werden. Zudem führt die Bezeichnung "instabil" auch immer wieder zu dem Missverständnis, das das betreffende Sortierverfahren unter bestimmten Bedingungen nicht richtig funktioniert.

Beispiel (instabil):

If zahlen(x) > zahlen(x+1) Then Goto tauschen

Beispiel (stabil):

If namen$(x) > namen$(x+1) Then Goto tauschen

If namen$(x) = namen$(x+1) And zahlen(x) > zahlen(x+1) Then Goto tauschen

Im ersten Beispiel wird nur nach Zahlen sortiert. Im zweiten Beispiel wird alphabetisch und nach Zahlen gleichzeitig sortiert, wobei die Namen (alphabetisch) die höhere Priorität haben und die Zahlen nur dann bewertet werden, wenn zwei Namen identisch sind.

Hier noch zwei interessante Informationen:

1. Shell-Sort scheint das schnellste Sortierverfahren zu sein, das es gibt. Zumindest war dies bis jetzt bei allen Sortierverfahren so, die ich bisher mit Test-Datensätzen getestet habe. Das gilt auch für den "Worst-Case"-Fall, mit dem Shell-Sort ebenfalls kein Problem hat. In einem Test habe ich zum Beispiel gemessen, wie lange Shell-Sort und Insertionsort jeweils benötigen, um eine Liste aus 4000 zufälligen Zahlen zu sortieren. Shell-Sort war 26,6 Mal schneller als Insertionsort.

2. Insertionsort und Gnomesort haben in ihrer Funktionsweise große Ähnlichkeit miteinander. Der Unterschied besteht nur in zwei Punkten: 1. Wenn eine Zahl verschoben wurde, dann springt Insertionsort direkt zu der Stelle zurück, an der das Verschieben begonnen hat. / 2. Insertionsort vertauscht beim verschieben von Daten - anders als Gnomesort - nicht immer zwei Werte, sondern es merkt sich das zu verschiebende Element und nimmt es aus dem Array (Liste) heraus. Dann werden die einzelnen Werte so lange einen Schritt nach rechts kopiert, bis die Zielposition erreicht ist. Beim verschieben existieren die zu verschiebenden Werte beim betreffenden Schritt nebeneinander also doppelt im Array. Zum Schluss wird der zu verschiebende und gemerkte Wert, an der richtigen Position wieder ins Array eingefügt. Durch diese Funktionsweise müssen im Array beim verschieben nur halb so viele Werte verändert werden.

--91.34.164.233 16:15, 19. Nov. 2011 (CET)

Zu stabil/instabil: die Wörter beziehen sich auf die Arbeitsweise, aber das ist kein Widerspruch. Sie sind nicht frei gewählt, sondern kommen so in der Fachliteratur vor, werden hier aber auch umschrieben, also weiß ich nicht, was du da ändern willst.

Dein Beispiel ist für einen Beweis dreifach ungeeignet.

1. Beispiele eignen sich als Gegenbeweis einer Aussage, aber nicht zur Verallgemeinerung.
2. Deine beiden Varianten unterscheiden sich in der Ordnungsrelation (dem "Sortierschlüssel"), nicht im Umgang mit gleichen Schlüsseln.
3. Dein Beispiel ist nur ein Auszug, aber vermutlich ist es etwas wie Bubblesort. Das sortiert die Schlüssel jeweils auf die gleiche Art, nämlich stabil. Im ersten Beispiel, das du instabil nennst, ist der Sortierschlüssel die Zahl. Bei gleichen Zahlen tauschst du nicht, also ist dein Verfahren stabil.

Instabil ist dagegen Quicksort. Da das Pivotelement immer nur ein Eintrag ist, kann es passieren, dass ein Eintrag mit gleichem Schlüssel auf der falschen Seite steht und mit dem Pivotelement getauscht werden muss. Und das macht instabile Verfahren aus: zweimal der gleiche Sortierschlüssel kann bedeuten, dass die Einträge getauscht werden.

Zu Shellsort: Ein Beispiel mit 4000 Einträgen ist kein Worst-Case. Wenn du mir dein Beispiel nennst, gebe ich dir einen Algorithmus, der mit nur einem Rechenschritt die Lösung ausgibt. Worst-Case ist ein Szenario in der Laufzeitanalyse. Und da ist z.B. Heapsort in der Theorie klar besser als Shellsort.

Zu Gnome/Insertion: Deine Beschreibung von Insertion-Sort klingt nicht so, als würdest beim Verschieben die binäre Suche beachten. Gnomesort ist dann doch eher mit Bubblesort vergleichbar, das steht aber schon im Gnomesort-Artikel.

Bleibt die Frage: Hast du konkrete Verbesserungsvorschläge, Wünsche oder Kritik in Bezug auf den Artikel?

--Zahnradzacken 19:44, 19. Nov. 2011 (CET)

Hallo Zahnradzacken!

Sorry für die sehr späte Antwort, aber ich bin erst heute wieder dazu gekommen hier vorbeizuschauen. Weil ich auch heute nur ein paar Minuten Zeit habe, eine Frage vorweg: Was meinst Du denn bei Insertion mit binärer Suche? --84.155.110.99 21:17, 1. Dez. 2011 (CET)

Steht doch bei Insertionsort: Beim Suchen nach der korrekten Einfügeposition kann man mit binärer Suche Zeit sparen. (Ob man dadurch die Stabilität riskiert, ist mir jetzt aber auch nicht klar.) --PeterFrankfurt 04:21, 2. Dez. 2011 (CET)

Du kannst aus jedem stabilen Sortierverfahren ein instabiles machen, indem du gleiche Werte noch ein wenig vertauschst. Und aus jedem instabilen ein stabiles, indem du die ursprüngliche Position mitführst. Wenn man sagt, ein Sortierverfahren sei instabil, meint man, dass es nicht möglich ist, das stabil zu implementieren, wenn man nicht zusätzliche Information speichert. Wenn man sagt, es sei stabil, meint man, dass gerade dies möglich ist. Gnomesort unterscheidet sich in der Tat nicht sehr von Insertionsort, allerdings ist er für Gnome angepasst worden, die immer schrittweise hin und her laufen und Töpfe vertauschen wollen. Naja… Die Binärsuche gehört nicht zwingend zu Insertionsort, macht das Verfahren aber auch nicht instabil. --Chricho ¹ 22:37, 2. Dez. 2011 (CET)

Zum letzten Punkt: Eben, und deshalb ist das ja als zusätzliche Option formuliert. (Genauso wie man beim Quicksort beim Runterschachteln irgendwo bei ca. 10 Elementen besser wieder auf Bubblesort oder sowas umschaltet.) --PeterFrankfurt 02:43, 3. Dez. 2011 (CET)

Was hat das mit Quicksort-Bubblesort Kombination zu tun? Im Übrigen wäre Insertionsort üblicher als Bubblesort, um ihn für kleine Listen anzuwenden, der läuft auch i.d.R. schneller. Wüsste nicht, wo man Bubblesort benutzt (naja, vllt. ist der manchmal etwas adaptiver). --Chricho ¹ 23:58, 3. Dez. 2011 (CET)

Was es damit zu tun hat? Dass auch da eine mehr oder weniger freie Wahl von Details des Verfahrens vorliegt. --PeterFrankfurt 02:30, 4. Dez. 2011 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 12:27, 17. Feb. 2014 (CET)

Zu den vorgeschlagenen Laufzeitoptimierungen für HeapSort

Ja, ich gebe zu, gestern bin ich mit den vorgeschlagenen Laufzeitoptimierungen zu Heapsort im Punkt 4) etwas über das Ziel hinausgeschossen. Wenn man statt des letzten Blattes die Spitze des Baumes entfernt, bleibt die Heapeigenschaft natürlich nicht immer erhalten. Das heißt, manche Beispiele funktieren, viele dagegen aber nicht. Sorry, das hätte ich gründlicher überprüfen müssen. Und vielen Dank für die schnelle Korrektur!

Aragorn321 (Diskussion) 11:19, 19. Jul. 2012 (CEST)

Hatte den Gedanken auch schonmal und dann verworfen – daher gings schnell. ;) --Chricho ¹ ² ³ 12:32, 19. Jul. 2012 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 15:49, 17. Feb. 2014 (CET)

HeapSort arbeitet in-place

HeapSort arbeitet in-place (siehe dazu auch den Artikel von HeapSort), deshalb muss die Zeile "Zusätzlicher Speicherbedarf (sofern nicht in-place)" bei HeapSort frei bleiben. (nicht signierter Beitrag von 77.23.51.169 (Diskussion) 14:19, 6. Aug. 2012 (CEST))

Stimmt, war aber schon seit 30. Juli gelöscht, nur nicht gesichtet. --Zahnradzacken (Diskussion) 18:27, 6. Aug. 2012 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 15:50, 17. Feb. 2014 (CET)

Zur Stabilität oder Instabilität von Sortieralgorithmen

Ein Sortieralgorithmus heißt stabil, wenn er die (nach anderen Kriterien) bereits existierende Sortierung im Falle von gleichen Schlüsselwerten (eines neuen Kriteriums) nicht verändert, d.h ein stabiler Sortieralgorithmus muss im Falle von gleichen Schlüsselwerten die bisherige Sortierung berücksichtigen. Ein nicht stabiler Sortieralgorithmus braucht darauf keine Rücksicht zu nehmen. Woher bekommt man aber mitten im Algorithmus die Information über eine eventuell vorliegende Sortierung, die dann explizit zu berücksichtigen ist, um diesen Algorithmus stabil zu machen? Dazu würde ich die stets vorhandene Indizierung der Elemente vorschlagen. Jedes zu sortierende Element hat immer einen eindeutigen Index. Wurden die gegebenen N Elemente bereits nach einem Kriterium K0 sortiert, so gilt für eine aufsteigende Sortierreihenfolge [a[i-1] <= a[i] für alle i=(1,...,N-1)]. Existieren nun für das neue Sortierkriterium K1 mehrere verschiedene Elemente mit dem gleichen Schlüsselwert so haben diese Elemente aber alle trotzdem noch einen eindeutigen und somit verschiedenen Index aus der vorherigen Sortierung nach K0. Damit kann man aus den Elementen mit gleichem Schlüsselwert auch stets dasjenige herausfinden, welches den größten bzw. kleinsten Index aus der evtl. vorangegangenen Sortierung besitzt und es somit zum "größten" oder "kleinsten" Element unter all jenen Elementen mit den gleichen Schlüsselwert machen. Mit anderen Worten: Berücksichtig man bei gleichen Schlüsselwerten auch den vorhandenen eindeutigen Index, gibt es eigentlich gar keine Elemente die wirklich gleich sind. Somit hat man (trotz teilweiser gleicher Werte) stets N verschiedene Elemente zu sortieren, womit die Frage nach "stabil" oder "nicht stabil" komplett entfällt. (nicht signierter Beitrag von Aragorn321 (Diskussion | Beiträge) 11:19, 19. Jul 2012 (CEST))

Ja, darauf wies ich bereits hin: Dieses Verfahren ist immer möglich, braucht aber zusätzlichen linearen Speicher, um sich die alten Positionen zu merken. Und bei Quicksort und Heapsort in der Standardvariante macht man genau das nicht, sie sind nicht stabil, das ist schon ein sinnvolles Kriterium, und dafür brauchen sie nicht linearen Speicher. --Chricho ¹ ² ³ 12:29, 19. Jul. 2012 (CEST)

Hab' einen entsprechenden Abschnitt im Artikel hinzugefügt.

Im Endeffekt verlängert man den Sortierschlüssel hinten mit der früheren Position. (Sie wird somit zum neuen, "niederwertigsten" Teil des Schlüssels.)

Bezogen auf den alten Sortierschlüssel ist das Verfahren nun stabil, da man nun als zusätzliche Precondition zusichern kann, dass keine 2 Elemente exakt identisch sind, sondern bei identischem Schlüsselteil_alt einen Schlüsselteil_neu mit "stabiler" Sortierung besitzen.

Bezogen auf den neuen Gesamt-Sortierschlüssel ist das Verfahren selbst natürlich weiter instabil.

Man handelt sich entsprechend aufwendigere Vergleiche ein, sowie mehr Platzbedarf.

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

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 15:46, 14. Mär. 2018 (CET)

Sortieren ohne Vergleich?

Geht nicht, meine ich! Selbst wenn nicht mehrere Objekte mit einander verglichen werden (durch wen oder was auch immer), wird ein betrachtetes Objekt mit der Objektbeschreibung des Sortierenden (Verfahren/Person) verglichen. Gruß AVS (Diskussion) 13:13, 15. Okt. 2017 (CEST)

Der Artikel meint: Sortieren, ohne die zu sortierenden Objekte untereinander auf "kleiner", "größer" oder "gleich" zu vergleichen.

Und das geht sehrwohl.

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

Nachtrag: Auch ohne das jew. Element mit einer "Objektbeschreibung" oder "Obj.-Referenz" vergleichen zu müssen. Kein Test auf 'größer', 'kleiner' oder 'gleich'.

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 15:46, 14. Mär. 2018 (CET)

Stabil und instabil / Ich kapiere es nicht!

Es tut mir wirklich leid, aber ich programmiere schon seit dem Jahr 1983 in Basic und habe schon mehrere eigene Sortierverfahren entwickelt, die hier im Artikel zwar nicht aufgeführt sind, aber ich muss Euch trotzdem leider mitteilen, dass ich Eure Betitelung mit "stabil" und "instabil" nicht kapiere. Ein Sortierverfahren ist doch nicht grundsätzlich "stabil" oder "instabil", denn ein Sortierverfahren gibt doch nur an, wie sich die Werte / Daten im Array bewegen. Beispiel "Bubble-Sort": Wenn die Anzahl der Daten im Array mindestens 2 ist, dann läuft der Algorithmus von der Position 1, bis zur Position "Anzahl der Werte"-1. An jeder Stelle wird dann überprüft, ob der nächste Wert kleiner ist, als der aktuelle (aufsteigend). In diesem Fall werden beide Werte vertauscht und sich gemerkt, dass es eine Änderung gegeben hat. Am Ende angekommen wird dann überprüft, ob es beim Durchlauf eine Änderung gegeben hat. In diesem Fall startet der Algorithmus wieder von vorne und dies so oft, bis es bei einem Durchlauf keine Änderung mehr gegeben hat. Anstelle zwei Zahlen zu vergleichen, kann man hier natürlich auch nach Alphabet und beliebig vielen zusätzlichen Kriterien gleichzeitig sortieren. Alles eine Frage davon, wie beide Datensätze verglichen werden. Es ist also die Art des Vergleichs der Daten innerhalb eines Sortierverfahrens der vorgibt, was passiert. --77.20.212.22 16:50, 13. Mär. 2018 (CET)

@77.20.212.22:

Hast Du in den Artikel Stabiles_Sortierverfahren mal reingeschaut? Da kannst Du sehen, dass ein Verfahren zwar grundsätzlich "stabil", aber nicht "grundsätzlich instabil" ist. Im Fall, dass sein totales Vergleichsunterprogramm zum Ergebnis = (gleich) kommt, ist dem instabilen Verfahren wurscht, wo unter den gleichen es das neue Datum hintut. Ein stabiles jedoch tut das neue Datum bspw. an den letzten (neuesten) Platz unter allen gleichen. (Für solches Verhalten hat man den vielleicht etwas seltsamen und anderweitig vorbelasteten Begriff "stabil" ausgesucht.)

Unwichtig ist die Sache nicht. Denn angenommen, wir sind im Windows Explorer und ich möchte an das neueste Dokument (.doc) ran. Ich kann nicht gleichzeitig nach Datum und Dateityp sortieren, aber nach jedem von beiden einzeln. Also sortiere ich zuerst nach Datum, dann nach Dateityp. Wenn der Explorer (immer) stabil sortiert, dann bleibt unter allen Dokumenten die Datumsreihenfolge garantiert (und nicht nur zufällig) erhalten und ich muss nicht noch einmal mit dem Auge durch alle Dokumente gehen und dort das Neueste aufspüren. --Nomen4Omen (Diskussion) 17:24, 13. Mär. 2018 (CET)

@ Nomen4Omen

Das kann man so aber mit allen Sortierverfahren erreichen. Bedingung 1: sortiere nach Datum und wenn Datum = Datum dann / Bedingung 2: sortiere nach Dateityp

Das ist doch genau das, was ich schon angesprochen habe. Den anderen Artikel hatte ich vorher schon gelesen. Er könnte meiner Meinung nach gelöscht werden, weil er nach meinem Standpunkt überflüssig ist.

Ich habe bereits Anfang der 90er-Jahre mal Bubble-Sort so angepasst, dass es eine Videoverwaltung für das System "Video 2000" auf einem "Commodore Plus4" sortieren konnte. Hier wurde nach drei Dingen gleichzeitig sortiert: Der Nummer der Kassette, der Seite der Kassette (1/2) und der Zählwerksstelle. Oder wenn gewollt, nur alphabetisch nach den Namen der aufgezeichneten Sendungen. Alles mit nur einem Durchlauf. Später habe ich dann Quicksort verwendet und auch entsprechend angepasst. --77.20.212.22 15:07, 14. Mär. 2018 (CET)

"Stabil" oder "Instabil" bezeichnet nunmal gerade den Fall, was mit der Reihenfolge von (nach einem anderen Sortierkriterium) vorsortierten Daten geschieht.

Natürlich kann man eine Sortierung 'stabil' machen, wenn man dieses andere Kriterium als "niederwertigeres Sortierkriterium" in den Sortierschlüssel aufnimmt. Das geht immer.

Aber: Bei manchen Sortierverfahren muss man das machen, bei anderen ist es unnötig. Erstere nennt man "instabil", zweitere "stabil".

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

Nachtrag: Alles oben, #Zur Stabilität oder Instabilität von Sortieralgorithmen schon mal erklärt...

@ Arilou

Ok, damit habe ich es jetzt verstanden.

Zu meinem Quicksort von früher: Es war zwar nicht ganz einfach die Logik mit den Selbstaufrufen "Rekursionen" umzusetzen, aber ich habe dann eine sehr einfache Lösung dafür gefunden: Ein Hilfs-Array, in dem die drei aktuellen Hauptvariablen hinten angehängt werden. Wenn eine Rekursion von Quicksort fertig ist, dann werden die letzten drei Hauptvariablen aus dem Hilfs-Array gezogen und Quicksort startet neu. Wenn das Hilfs-Array leer ist, dann ist die Sortierung beendet. Anders wird wohl auch keine Umsetzung von Quicksort möglich sein, weil die Anzahl der gleichzeitig pausierenden Rekursionen, mit der Anzahl der zu sortierenden Datensätze identisch sein kann. --77.20.212.22 15:36, 14. Mär. 2018 (CET)

(OT:) Du hast dir einen eigenen Stack gebaut und die Rekursion zu einer Iteration über dem Stack umgebaut. (Könnte man auch nennen "du hat eine eigene kleine Stack-Verwaltung erstellt".)

"Jahr 1983 in Basic" - dein Vorgehen ist typisch, wenn die Programmiersprache keine echten Unterroutinen anbietet - frühe Basic-Formen waren oft derart beschränkt.

--arilou (Diskussion) 09:43, 15. Mär. 2018 (CET)

Archivierung dieses Abschnittes wurde gewünscht von: arilou (Diskussion) 15:46, 14. Mär. 2018 (CET)

Welches Sortierverfahren ist das schnellste?

Kurze Frage: Welches ist denn eigentlich das schnellste bekannte Sortierverfahren das es gibt? Anhand der Formeln von $\Theta$ könnte man ja denken, dass viele Sortierverfahren identisch schnell sind. --77.21.163.85 00:29, 16. Apr. 2021 (CEST)

Die Frage lässt sich nicht beantworten, weil es von den jeweiligen Randbedingungen abhängt.

Anzahl der zu sortierenden Elemente? Eher "weniger als 10" oder "mehr als 1 Million"?

Schlüsseltyp? 8-Bit-Ganzzahl oder String variabler Länge?

Kosten eines Vergleichs? Zwei Ganzzahlen oder zwei Strings_caseInsensitive?

Kosten einer Umpositionierung? Werden im Ram ein paar Bytes rumgeschubst, oder wird auf einem Bandgerät umgespult?

Programm-Rahmenbedingungen? Ein Betriebssystem-Scheduler darf evtl. kein zusätzliches Ram reservieren, egal wie viele Tasks es zu sortieren gilt.

...

--arilou (Diskussion) 10:54, 19. Apr. 2021 (CEST)

Ok, dann werde ich mal etwas präziser: Es ging mir mit meiner Frage nur um die Art und Weise, wie sich die Werte beim Sortieren bewegen. Welches Verfahren wäre denn dann in etwa das schnellste, wenn man innerhalb von Excel mit Visual Basic ein Array mit Zahlen sortieren würde? --77.21.163.85 23:21, 6. Mai 2021 (CEST)

Im Grunde immernoch zu unpräzise.

Anzahl der Zahlen? Eher "unter 100" oder "können mehr als 1 Mio Werte sein"?

Gleitkommazahlen oder "8-Bit-Integer"? Lassen sich die Gleitkommazahlen gruppieren (für einen Bucketsort)?

Sollen wirklich nur die Zahlenwerte sortiert werden, oder ist jede Zeile ein "Datensatz" und deren andere Spalten müssen mitkopiert werden?

Ist das eine seltene Aufgabe (darf nur begrenzt Programmierarbeit/-zeit verbrauchen), oder wird die Routine später tausend- oder millionenfach eingesetzt, und jedes Quäntchen Beschleunigung zählt, selbst wenn man dafür einen Arbeitstag Programmierarbeit investieren muss?

Tja, es gibt einen Grund, warum in vielen Fällen Sortieralgorithmen zum Einsatz kommen, die in den meisten Fällen recht gut abschneiden - weil nunmal recht viele Randbedingungen Einfluss darauf haben, welcher Algorithmus vmtl. "der schnellste" sein wird.

Eine zeitlang war überall Quicksort eingebaut, mittlerweile ist aber wohl Mergesort beliebter. Häufig wird jedoch eine parallele Variante (z.B. Merge-Algorithmen#k-Wege-Mischen) verwendet, da heutige Computer ja meist Mehrkernsysteme sind.

--arilou (Diskussion) 09:44, 7. Mai 2021 (CEST)

PS: In Excel gibt es afaik eine eingebaute Sortierfunktion. Die ist fehlerfrei implementiert, millionenfach getestet, und vmtl. viel schneller, als denselben Algorithmus in interpretiertem VBA nachzuimplementieren.

Ich denke da an eine Million LONG-Zahlen (1 bis 1.000.000), die zufällig gemischt sind.

Wie lautet denn der Befehl zum Sortieren? Bis jetzt wusste ich nur, dass man die Tabelle mit Makros sortieren lassen kann. Den Code habe ich durch eine Makro-Aufzeichnung bekommen und dann angepasst. --77.21.163.85 12:56, 7. Mai 2021 (CEST)

Von Hand findest du das bei

Menü -> Daten -> Sortieren

Die Hilfe dazu nennt die zwei VBA-Funktionen 'SORT' und 'SORTBY'.

Meine VBA-Zeiten liegen aber schon lange zurück, die genaue Verwendung kann ich nicht weiter beschreiben.

--arilou (Diskussion) 13:50, 7. Mai 2021 (CEST)

Archivierung dieses Abschnittes wurde gewünscht von: 77.21.163.85 11:40, 12. Jun. 2021 (CEST)