Warum wird die Auswahl schneller sortiert als die Blasensortierung?

28

Auf Wikipedia steht : "... Selektionssortierung übertrifft fast immer Blasensortierung und Gnomensortierung." Kann mir bitte jemand erklären, warum Auswahlsortierung als schneller als Blasensortierung angesehen wird, obwohl beide haben:

  1. Zeitliche Komplexität im schlimmsten Fall :O(n2)

  2. Anzahl der Vergleiche : O(n2)

  3. Beste Fallzeitkomplexität :

    • Blasensortierung:O(n)
    • Auswahlsortierung:O(n2)
  4. Durchschnittliche Fallzeitkomplexität :

    • Blasensortierung:O(n2)
    • Auswahlsortierung:O(n2)
Ryo
quelle

Antworten:

32

Alle Komplexitäten, die Sie angegeben haben, sind wahr, sie werden jedoch in Big O-Notation angegeben , sodass alle additiven Werte und Konstanten weggelassen werden.

Um Ihre Frage zu beantworten, müssen wir uns auf eine detaillierte Analyse dieser beiden Algorithmen konzentrieren. Diese Analyse kann von Hand durchgeführt werden oder in vielen Büchern gefunden werden. Ich werde Ergebnisse aus Knuths Art of Computer Programming verwenden .

Durchschnittliche Anzahl von Vergleichen:

  • Blasensortierung :12(N2NlnN(γ+ln21)N)+O(N)
  • Einfügesortierung :14(N2N)+NHN
  • Auswahlsortierung :(N+1)HN2N

Wenn Sie diese Funktionen zeichnen, erhalten Sie ungefähr Folgendes: Handlung plot2

Wie Sie sehen, ist die Blasensortierung mit zunehmender Anzahl von Elementen viel schlechter, obwohl beide Sortiermethoden die gleiche asymptotische Komplexität aufweisen.

Diese Analyse basiert auf der Annahme, dass die Eingabe zufällig ist - was möglicherweise nicht immer zutrifft. Bevor wir jedoch mit dem Sortieren beginnen, können wir die Eingabesequenz (mit einer beliebigen Methode) zufällig permutieren, um den Durchschnittsfall zu erhalten.

Ich habe die Zeitkomplexitätsanalyse weggelassen, da sie von der Implementierung abhängt, aber ähnliche Methoden verwendet werden können.

Bartosz Przybylski
quelle
Ich habe ein Problem mit "wir können zufällig Eingabesequenz permutieren, um Durchschnittsfall zu erhalten". Warum geht das schneller als in der zum Sortieren erforderlichen Zeit?
Sasho Nikolov
1
Sie können eine beliebige Folge von Zahlen permutieren, die mal dauert, wobei die Sequenzlänge ist. Es ist offensichtlich, dass jeder vergleichsbasierte Sortieralgorithmus mindestens Komplexität haben muss, so dass selbst wenn Sie zu seiner Komplexität hinzufügen , nicht so viel geändert wird. Wie auch immer, wir sprechen über Vergleiche, nicht über Zeit. Die Zeitkomplexität hängt von der Implementierung und der Ausführung der Maschine ab, wie ich in der Antwort erwähnt habe. NNO(NlogN)N
Bartosz Przybylski
Ich glaube ich war müde, du hast recht, die Sequenz kann in linearer Zeit permutiert werden.
Sasho Nikolov
Da , ist Ihr Vergleich zur Selektion korrekt gebunden sortieren? Es sieht so aus, als würden Sie andeuten, dass O (n log n) Vergleiche im Durchschnitt durchgeführt werden. HN=Θ(logN)
Templatetypedef
Gamma = 0,577216 ist die Euler-Mascheroni-Konstante. Das entsprechende Kapitel ist "Die Kunst des Programmierens", Band 3, Abschnitt 5.2.2. 109 und 129. Wie haben Sie den Fall der Blasensortierung genau dargestellt, insbesondere den Term O (sqrt (N))? Hast du es gerade vernachlässigt?
mxmlnkn
11

Die asymptotischen Kosten oder -Notation beschreiben das einschränkende Verhalten einer Funktion, da ihr Argument gegen unendlich tendiert, dh ihre Wachstumsrate.O

Die Funktion selbst, z. B. die Anzahl der Vergleiche und / oder Swaps, kann für zwei Algorithmen mit denselben asymptotischen Kosten unterschiedlich sein, vorausgesetzt, sie wachsen mit derselben Rate.

Insbesondere erfordert die Blasensortierung im Durchschnitt Tauschvorgänge pro Eintrag (jeder Eintrag wird elementweise von seiner Anfangsposition zu seiner Endposition verschoben, und jeder Tausch umfasst zwei Einträge), während die Auswahlsortierung nur (einmal ) erfordert Minimum / Maximum wurde gefunden, es wird einmal bis zum Ende des Arrays getauscht).n/41

In Bezug auf die Anzahl der Vergleiche erfordert die Vergleiche, wobei der maximale Abstand zwischen der Anfangsposition eines Eintrags und seiner Endposition ist, der für gleichmäßig verteilte Anfangswerte normalerweise größer als . Die Auswahlsortierung erfordert jedoch immer Vergleiche.k×nkn/2(n1)×(n2)/2

Zusammenfassend lässt sich sagen, dass die asymptotische Grenze ein gutes Gefühl dafür vermittelt, wie die Kosten eines Algorithmus in Bezug auf die Eingabegröße steigen, aber nichts über die relative Leistung verschiedener Algorithmen innerhalb derselben Gruppe aussagt.

Pedro
quelle
1
Dies ist sogar eine sehr gute Antwort
Grijesh Chauhan
Welches Buch bevorzugen Sie?
Grijesh Chauhan
@GrijeshChauhan: Bücher sind Geschmackssache, also nehmen Sie jede Empfehlung mit einem Körnchen Salz an. Ich persönlich mag Cormen, Leiserson und Rivests "Introduction to Algorithms", die einen guten Überblick über eine Reihe von Themen bietet, und Knuths "The Art of Computer Programming" -Reihe, wenn Sie mehr / alle Details zu einem bestimmten Thema benötigen. Möglicherweise möchten Sie überprüfen, ob die Frage zu Büchern bereits gestellt wurde, oder diese Frage posten, falls dies nicht der Fall ist.
Pedro
Für mich ist der dritte Absatz in Ihrer Antwort die eigentliche Antwort. Nicht die Grafiken für große Eingaben, die in einer anderen Antwort angegeben sind.
Überaustausch
3

Die Blasensortierung verwendet mehr Swap-Zeiten, während die Auswahlsortierung dies vermeidet.

Bei Verwendung der Auswahlsortierung werden nhöchstens die Zeiten ausgetauscht. Bei Verwendung der Bubble-Sortierung wird sie jedoch fast ausgetauscht n*(n-1). Und offensichtlich ist die Lesezeit auch im Gedächtnis kürzer als die Schreibzeit. Die Vergleichszeit und andere Laufzeit können ignoriert werden. Auslagerungszeiten sind daher der kritische Engpass des Problems.

simonmysun
quelle
Ich denke, die andere Antwort von Bartek ist vernünftiger, aber ich kann nicht abstimmen oder kommentieren ... Übrigens denke ich immer noch, dass sich das auf die Schreibzeit auswirkt und hoffe, dass er dies berücksichtigen kann, wenn er dies sieht und zustimmt.
simonmysun
Sie können die Anzahl der Vergleiche nicht einfach ignorieren, da es Anwendungsfälle gibt, in denen die zum Vergleichen von zwei Elementen aufgewendete Zeit die zum Austauschen von zwei Elementen aufgewendete Zeit bei weitem überschreiten kann. Betrachten Sie eine verknüpfte Liste extrem langer Zeichenfolgen (z. B. jeweils 100 KB). Das Einlesen jeder Zeichenfolge würde viel länger dauern als das erneute Zuweisen von Zeigern.
Irvin Lim
@IrvinLim Ich denke, Sie haben vielleicht Recht, aber ich muss möglicherweise die statistischen Daten einsehen, bevor ich es mir anders überlege.
SimonMysun