Warum ist die Auswahlsortierung schneller als die Blasensortierung?

Alle von Ihnen angegebenen Komplexitäten sind wahr, jedoch gegeben In Big O-Notation werden alle additiven Werte und Konstanten weggelassen.

Um Ihre Frage zu beantworten, benötigen wir d sich auf eine detaillierte Analyse dieser beiden Algorithmen zu konzentrieren. Diese Analyse kann von Hand durchgeführt oder in vielen Büchern gefunden werden. Ich werde Ergebnisse aus Knuths Kunst der Computerprogrammierung verwenden.

Durchschnittliche Anzahl von Vergleichen:

• Blasensortierung : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Einfügesortierung : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Auswahlsortierung : $ (N + 1) H_N – 2N $

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

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

Diese Analyse basiert auf der Annahme, dass die Eingabe zufällig ist – was möglicherweise nicht immer der Fall ist. 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 können verwendet werden.

Kommentare

• Ich habe ein Problem mit " Wir können die Eingabesequenz zufällig permutieren, um einen Durchschnittsfall zu erhalten ". Warum kann dies schneller als die zum Sortieren erforderliche Zeit erfolgen?
• Sie können eine beliebige Folge von Zahlen permutieren, die $ N $ Zeit benötigt, wobei $ N $ die Sequenzlänge ist. Es ist ' offensichtlich, dass jeder vergleichsbasierte Sortieralgorithmus mindestens $ \ mathcal O (N \ log N) $ Komplexität aufweisen muss, selbst wenn Sie $ N $ hinzufügen ' Die Komplexität ' wird nicht so stark verändert. Wie auch immer, wir sprechen vom Vergleich, nicht von der Zeit. Die Komplexität der Zeit hängt von der Implementierung und dem laufenden Computer ab, wie ich in der Antwort erwähnt habe.
• Ich glaube, ich war müde, Sie haben Recht, die Sequenz kann in linearer Zeit permutiert werden
• Ist Ihr Vergleich für die Auswahlsortierung korrekt, da $ H_N = \ Theta (log N) $ ist? Es sieht so aus, als würden Sie ' implizieren, dass im Durchschnitt O (n log n) Vergleiche durchgeführt werden.
• Gamma = 0,577216 ist Euler-Mascheroni ' s Konstante. Das relevante Kapitel ist " Die Kunst des Programmierens " vol 3 Abschnitt 5.2.2 pg. 109 und 129. Wie haben Sie den Fall der Blasensortierung genau dargestellt, insbesondere den Term O (sqrt (N))? Haben Sie es einfach vernachlässigt?

Die asymptotischen Kosten oder $ \ mathcal O $ -Notation, beschreibt das begrenzende Verhalten einer Funktion, da ihr Argument gegen unendlich tendiert, dh ihre Wachstumsrate.

Die Funktion selbst, z. 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 $ n / 4 $ Swaps pro Eintrag (jeder Eintrag wird elementweise von seiner Anfangsposition an seine Endposition verschoben, und jeder Swap umfasst zwei Einträge), während die Auswahlsortierung nur $ 1 $ erfordert (sobald das Minimum / Maximum gefunden wurde, wird er einmal getauscht bis zum Ende des Arrays).

In Bezug auf die Anzahl der Vergleiche erfordert die Blasensortierung $ k \ times n $ Vergleiche, wobei $ k $ der maximale Abstand zwischen der Anfangsposition eines Eintrags und ist Die endgültige Position ist normalerweise größer als $ n / 2 $ für gleichmäßig verteilte Anfangswerte. Die Auswahlsortierung erfordert jedoch immer $ (n-1) \ mal (n-2) / 2 $ Vergleiche.

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

Kommentare

• Dies ist sogar eine sehr gute Antwort.
• Welches Buch bevorzugen Sie?
• @GrijeshChauhan: Bücher sind Geschmackssache, nehmen Sie also jede Empfehlung mit einem Körnchen Salz. Ich persönlich mag Cormen, Leiserson und Rivest ' s " Einführung in Algorithmen ", Dies gibt einen guten Überblick über eine Reihe von Themen und Knuth ' s " Die Kunst der Computerprogrammierung " -Serie, wenn Sie mehr / alle Details zu einem bestimmten Thema benötigen. Vielleicht möchten Sie überprüfen, ob die Frage nach Büchern hier schon einmal gestellt wurde, oder diese Frage posten, wenn sie nicht ' t ist.
• Für mich der dritte Absatz in Ihre Antwort ist die eigentliche Antwort. Nicht die Diagramme für große Eingaben, die in einer anderen Antwort angegeben sind.

Die Blasensortierung verwendet mehr Austauschzeiten. während die Auswahlsortierung dies vermeidet.

Bei Verwendung der Sortierauswahl wird n höchstens