Einfügungssortierung gegen Blasensortierungsalgorithmen

Ich versuche, ein paar Sortieralgorithmen zu verstehen, aber ich habe Mühe, den Unterschied zwischen dem Blasensortierungs- und dem Einfügesortieralgorithmus zu erkennen.

Ich weiß, dass beide O (n ² ) sind, aber es scheint mir, dass die Blasensortierung nur den Maximalwert des Arrays für jeden Durchgang nach oben sprudelt, während die Einfügesortierung bei jedem Durchgang nur den niedrigsten Wert nach unten senkt. Tun sie nicht genau dasselbe, aber in verschiedene Richtungen?

Bei der Einfügungssortierung beginnt die Anzahl der Vergleiche / potenziellen Swaps bei Null und steigt jedes Mal an (dh 0, 1, 2, 3, 4, ..., n). Bei der Blasensortierung tritt jedoch dasselbe Verhalten auf, jedoch am Ende von die Sortierung (dh n, n-1, n-2, ... 0), da die Blasensortierung beim Sortieren nicht mehr mit den letzten Elementen verglichen werden muss.

Trotz alledem scheint es ein Konsens zu sein, dass die Einfügungssortierung im Allgemeinen besser ist. Kann mir jemand sagen warum?

Bearbeiten: Ich interessiere mich hauptsächlich für die Unterschiede in der Funktionsweise der Algorithmen, nicht so sehr für ihre Effizienz oder asymptotische Komplexität.

Bei der Blasensortierung in der i-ten Iteration haben Sie ni-1 innere Iterationen (n ^ 2) / 2 insgesamt, aber bei der Einfügungssortierung haben Sie maximal i Iterationen im i-ten Schritt, aber i / 2 im Durchschnitt, da Sie die innere Schleife stoppen können früher, nachdem Sie die richtige Position für das aktuelle Element gefunden haben. Sie haben also (Summe von 0 bis n) / 2, was (n ^ 2) / 4 insgesamt ist;

Aus diesem Grund ist die Einfügesortierung schneller als die Blasensortierung.

Sortieren durch Einfügen

Nach i Iterationen werden die ersten i Elemente geordnet.

In jeder Iteration wird das nächste Element durch den sortierten Abschnitt geblasen, bis es die richtige Stelle erreicht:

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

Die 4 wird in den sortierten Bereich gesprudelt

Pseudocode:

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

Blasensortierung

Nach i Iterationen sind die letzten i Elemente die größten und geordneten.

Durchsuchen Sie in jeder Iteration den unsortierten Abschnitt, um das Maximum zu ermitteln.

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

Die 5 wird aus dem unsortierten Bereich gesprudelt

Pseudocode:

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

Beachten Sie, dass typische Implementierungen vorzeitig beendet werden, wenn während einer der Iterationen der äußeren Schleife keine Swaps durchgeführt werden (da dies bedeutet, dass das Array sortiert ist).

Unterschied

Beim Einfügen werden Sortierelemente in den sortierten Abschnitt gesprudelt, während beim Blasensortieren die Maxima aus dem unsortierten Abschnitt gesprudelt werden.

Einen weiteren Unterschied habe ich hier nicht gesehen:

Die Blasensortierung hat 3 Wertzuweisungen pro Swap : Sie müssen zuerst eine temporäre Variable erstellen, um den Wert zu speichern, den Sie vorantreiben möchten (Nr. 1), und dann die andere Swap-Variable an die Stelle schreiben, an der Sie den Wert gerade gespeichert haben von (Nr. 2) und dann müssen Sie Ihre temporäre Variable an die Stelle anderer Stelle (Nr. 3) schreiben. Sie müssen dies für jeden Punkt tun - Sie möchten vorwärts gehen -, um Ihre Variable an den richtigen Punkt zu sortieren.

Mit der Einfügesortierung setzen Sie Ihre Variable in eine temporäre Variable und setzen dann alle Variablen 1 Stelle rückwärts vor diese Stelle, solange Sie die richtige Stelle für Ihre Variable erreichen. Das ergibt 1 Wertzuweisung pro Spot . Am Ende schreiben Sie Ihre temporäre Variable in die Stelle.

Das macht auch weit weniger Wertzuweisungen.

Dies ist nicht der stärkste Geschwindigkeitsvorteil, aber ich denke, es kann erwähnt werden.

Ich hoffe, ich habe mich verständlich ausgedrückt, wenn nicht, tut mir leid, ich bin kein gebürtiger Brite

Der Hauptvorteil der Einfügesortierung besteht darin, dass es sich um einen Online-Algorithmus handelt. Sie müssen nicht alle Werte am Start haben. Dies kann nützlich sein, wenn Daten aus dem Netzwerk oder einem Sensor verarbeitet werden.

Ich habe das Gefühl, dass dies schneller wäre als andere herkömmliche n log(n)Algorithmen. Denn die Komplexität würde n*(n log(n))zB darin bestehen, jeden Wert aus stream ( O(n)) zu lesen / speichern und dann alle Werte ( O(n log(n))) zu sortieren, was dazu führtO(n^2 log(n))

Im Gegenteil, mit Insert Sort müssen O(n)Werte aus dem Stream gelesen und O(n)an der richtigen Stelle platziert werden O(n^2). Ein weiterer Vorteil ist, dass Sie keine Puffer zum Speichern von Werten benötigen, sondern diese am endgültigen Ziel sortieren.

Die Blasensortierung ist nicht online (sie kann keinen Strom von Eingaben sortieren, ohne zu wissen, wie viele Elemente es geben wird), da sie nicht wirklich ein globales Maximum der sortierten Elemente verfolgt. Wenn ein Element eingefügt wird, müssen Sie das Sprudeln von vorne beginnen

Nun, die Blasensortierung ist nur dann besser als die Einfügungssortierung, wenn jemand nach Top-k-Elementen aus einer großen Liste von Zahlen sucht, dh bei der Blasensortierung nach k Iterationen erhalten Sie Top-k-Elemente. Nach k Iterationen in der Einfügesortierung wird jedoch nur sichergestellt, dass diese k Elemente sortiert sind.

Obwohl beide Sortierungen O (N ^ 2) sind. Die verborgenen Konstanten sind bei der Einfügungssortierung viel kleiner. Versteckte Konstanten beziehen sich auf die tatsächliche Anzahl der ausgeführten primitiven Operationen.

Wann hat die Einfügesortierung eine bessere Laufzeit?

1. Das Array ist fast sortiert. Beachten Sie, dass die Einfügesortierung in diesem Fall weniger Operationen ausführt als die Blasensortierung.
2. Das Array ist relativ klein: Einfügesortierung Sie verschieben Elemente, um das aktuelle Element zu platzieren. Dies ist nur dann besser als Blasensortierung, wenn die Anzahl der Elemente gering ist.

Beachten Sie, dass die Einfügungssortierung nicht immer besser ist als die Blasensortierung. Um das Beste aus beiden Welten zu erhalten, können Sie die Einfügungssortierung verwenden, wenn das Array klein ist, und wahrscheinlich die Sortierung (oder Quicksortierung) für größere Arrays zusammenführen.

Die Blasensortierung ist unter allen Umständen fast nutzlos. In Anwendungsfällen, in denen die Einfügesortierung möglicherweise zu viele Swaps enthält, kann die Auswahlsortierung verwendet werden, da sie weniger als N Swap-Zeiten garantiert. Da die Auswahlsortierung besser ist als die Blasensortierung, hat die Blasensortierung keine Anwendungsfälle.

Anzahl der Swaps in jeder Iteration

• Die Einfügesortierung führt höchstens 1 Austausch in jeder Iteration durch .
• Die Blasensortierung führt in jeder Iteration 0 bis n Swaps durch.

Zugriff auf sortierte Teile und Ändern

• Durch das Einfügen und Sortieren wird auf das sortierte Teil zugegriffen (und bei Bedarf geändert), um die richtige Position einer betrachteten Zahl zu finden.
• Bei der Optimierung greift die Blasensortierung nicht auf das zu, was bereits sortiert ist.

Online oder nicht

• Einfügesortierung ist online. Das bedeutet, dass die Einfügesortierung jeweils eine Eingabe vornimmt, bevor sie an der richtigen Position platziert wird. Es muss nicht nur vergleichen adjacent-inputs.
• Bubble-Sort ist nicht online. Es wird nicht jeweils ein Eingang betrieben. Es behandelt eine Gruppe von Eingaben (wenn nicht alle) in jeder Iteration. Blasensortierung nur vergleichen undadjacent-inputs in jeder Iteration tauschen .

Sortieren durch Einfügen:

1.In der Einfügung ist ein Sortierwechsel nicht erforderlich.

2. Die zeitliche Komplexität der Einfügungssortierung beträgt Ω (n) für den besten Fall und O (n ^ 2) für den schlechtesten Fall.

3.less Komplex im Vergleich zur Blasensortierung.

4.Beispiel: Bücher in die Bibliothek einlegen, Karten anordnen.

Blasensortierung: 1. Austausch der Blasensortierung erforderlich.

2. Die zeitliche Komplexität der Blasensortierung beträgt Ω (n) für den besten Fall und O (n ^ 2) für den schlechtesten Fall.

3. Komplexer im Vergleich zur Einfügesortierung.

Die Einfügungssortierung kann wie folgt fortgesetzt werden: " Suchen Sie nach dem Element, das sich an der ersten Position (dem Minimum) befinden soll, machen Sie Platz, indem Sie die nächsten Elemente verschieben, und setzen Sie es an die erste Position. Gut. Schauen Sie sich nun das Element an, das sich an der zweiten Position befinden soll." ... "und so weiter ...

Die Blasensortierung funktioniert anders und kann wie folgt fortgesetzt werden: " Solange ich zwei benachbarte Elemente in der falschen Reihenfolge finde, tausche ich sie aus. "