Blasensortierung - Bubble sort

Blasensortierung
Bubblesort-edited-color.svg
Statische Visualisierung der Blasensortierung
Klasse Sortieralgorithmus
Datenstruktur Array
Worst-Case- Leistung Vergleiche, Tausch
Best-Case- Leistung Vergleiche, Tausch
Durchschnittliche Leistung Vergleiche, Tausch
Raumkomplexität im schlimmsten Fall gesamt, hilfs

Bubble-Sort , manchmal auch als sinkende Sortierung bezeichnet , ist ein einfacher Sortieralgorithmus , der wiederholt die Liste durchläuft, benachbarte Elemente vergleicht und sie vertauscht , wenn sie in der falschen Reihenfolge sind. Der Durchlauf der Liste wird wiederholt, bis die Liste sortiert ist. Der Algorithmus, bei dem es sich um eine Vergleichssortierung handelt , ist nach der Art benannt, wie kleinere oder größere Elemente an die Spitze der Liste "blasen".

Dieser einfache Algorithmus schneidet im realen Einsatz schlecht ab und wird hauptsächlich als Lehrmittel verwendet. Effizientere Algorithmen wie quicksort , timsort oder merge sort werden von den Sortierbibliotheken verwendet, die in gängige Programmiersprachen wie Python und Java integriert sind.

Analyse

Ein Beispiel für Blasensortierung. Vergleichen Sie vom Anfang der Liste aus jedes benachbarte Paar, tauschen Sie ihre Position, wenn sie nicht in der richtigen Reihenfolge sind (das letztere ist kleiner als das erstere). Nach jeder Iteration muss ein Element weniger (das letzte) verglichen werden, bis keine weiteren Elemente mehr zu vergleichen sind.

Leistung

Bubble Sort hat eine Worst-Case und durchschnittliche Komplexität О ( n 2 ), wobei n die Anzahl der Elemente , die sortiert werden. Die meisten praktischen Sortieralgorithmen haben eine wesentlich bessere Worst-Case- oder durchschnittliche Komplexität, oft 0 ( n  log  n ). Sogar andere О ( n 2 ) Sortieralgorithmen, wie Insertionsort , laufen im Allgemeinen schneller als Bubblesort und sind nicht komplexer. Daher ist Bubble-Sort kein praktischer Sortieralgorithmus.

Der einzige wesentliche Vorteil, den Bubblesort gegenüber den meisten anderen Algorithmen hat, sogar quicksort , aber nicht insert sort , besteht darin, dass die Fähigkeit, zu erkennen, dass die Liste effizient sortiert ist, in den Algorithmus integriert ist. Wenn die Liste bereits sortiert ist (bester Fall), beträgt die Komplexität der Blasensortierung nur O ( n ). Im Gegensatz dazu führen die meisten anderen Algorithmen, auch solche mit besserer durchschnittlicher Fallkomplexität , ihren gesamten Sortierprozess am Set durch und sind daher komplexer. Die Einfügungssortierung teilt jedoch nicht nur diesen Vorteil, sondern schneidet auch bei einer Liste besser ab, die im Wesentlichen sortiert ist (mit einer kleinen Anzahl von Inversionen ). Wenn dieses Verhalten gewünscht wird, kann es außerdem trivial zu jedem anderen Algorithmus hinzugefügt werden, indem die Liste überprüft wird, bevor der Algorithmus ausgeführt wird.

Kaninchen und Schildkröten

Der Abstand und die Richtung, in der sich Elemente während der Sortierung bewegen müssen, bestimmen die Leistung der Blasensortierung, da sich die Elemente mit unterschiedlichen Geschwindigkeiten in unterschiedliche Richtungen bewegen. Ein Element, das sich zum Ende der Liste bewegen muss, kann sich schnell bewegen, da es an aufeinanderfolgenden Swaps teilnehmen kann. Zum Beispiel gewinnt das größte Element in der Liste jeden Tausch, so dass es beim ersten Durchgang an seine sortierte Position verschoben wird, selbst wenn es am Anfang beginnt. Andererseits kann sich ein Element, das sich zum Anfang der Liste bewegen muss, nicht schneller als einen Schritt pro Durchgang bewegen, sodass sich Elemente sehr langsam zum Anfang bewegen. Wenn das kleinste Element am Ende der Liste steht, braucht es n −1 Durchläufe, um es an den Anfang zu verschieben. Dies hat dazu geführt, dass diese Art von Elementen nach den Charakteren in Aesops Fabel von Die Schildkröte und der Hase Kaninchen bzw. Schildkröten genannt wurden .

Es wurden verschiedene Anstrengungen unternommen, um Schildkröten zu eliminieren, um die Geschwindigkeit der Blasensortierung zu verbessern. Cocktail-Sortierung ist eine bidirektionale Blasensortierung, die von Anfang bis Ende verläuft und sich dann selbst umkehrt, von Ende zu Anfang. Es kann Schildkröten ziemlich gut bewegen, aber es behält O(n 2 ) Worst-Case-Komplexität bei. Comb Sort vergleicht Elemente, die durch große Lücken getrennt sind, und kann Schildkröten extrem schnell bewegen, bevor sie zu immer kleineren Lücken übergehen, um die Liste zu glätten. Seine durchschnittliche Geschwindigkeit ist mit schnelleren Algorithmen wie Quicksort vergleichbar .

Schritt-für-Schritt-Beispiel

Nehmen Sie ein Array von Zahlen "5 1 4 2 8" und sortieren Sie das Array von der niedrigsten Zahl zur größten Zahl mit Bubble-Sort. In jedem Schritt werden fett geschriebene Elemente verglichen. Drei Pässe sind erforderlich;

Erster Pass
( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Hier vergleicht der Algorithmus die ersten beiden Elemente und vertauscht, da 5 > 1.
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Tausch seit 5 > 4
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Tausch seit 5 > 2
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Da diese Elemente bereits in Ordnung sind (8 > 5), vertauscht der Algorithmus sie nicht.
Zweiter Pass
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), Tausch seit 4 > 2
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Nun ist das Array bereits sortiert, aber der Algorithmus weiß nicht, ob es abgeschlossen ist. Der Algorithmus benötigt ein zusätzliches ganzes verstreichen , ohne jede Swap zu wissen es sortiert wird.

Dritter Pass
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Implementierung

Pseudocode-Implementierung

In Pseudocode kann der Algorithmus als (0-basiertes Array) ausgedrückt werden:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped
end procedure

Optimieren der Blasensortierung

Der Bubble-Sort-Algorithmus kann optimiert werden, indem beobachtet wird, dass der n- te Durchgang das n- te größte Element findet und an seinen endgültigen Platz bringt. Die innere Schleife kann also vermeiden, beim n- ten Mal die letzten n − 1 Elemente zu betrachten :

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                swapped := true
            end if
        end for
        n := n - 1
    until not swapped
end procedure

Ganz allgemein kann es vorkommen, dass in einem Durchgang mehr als ein Element an ihrer endgültigen Position platziert wird. Insbesondere werden nach jedem Durchlauf alle Elemente nach dem letzten Tausch sortiert und müssen nicht erneut geprüft werden. Dadurch können viele Elemente übersprungen werden, was im schlimmsten Fall zu einer Verbesserung der Vergleichszahl um etwa 50 % führt (obwohl keine Verbesserung der Swap-Zahlen) und sehr wenig Komplexität hinzufügt, da der neue Code die "ausgetauschte" Variable subsumiert:

Um dies in Pseudocode zu erreichen, kann Folgendes geschrieben werden:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        newn := 0
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                newn := i
            end if
        end for
        n := newn
    until n  1
end procedure

Alternative Modifikationen, wie z. B. das Sortieren von Cocktailshakern, versuchen, die Leistung des Blasensortierens zu verbessern, während die gleiche Idee des wiederholten Vergleichens und Austauschens benachbarter Elemente beibehalten wird.

Verwenden

Blase sortieren. Die Liste wurde in einem kartesischen Koordinatensystem aufgetragen, wobei jeder Punkt ( x , y ) anzeigt, dass der Wert y bei Index x gespeichert ist . Dann würde die Liste nach dem Wert jedes Pixels nach Bubble-Sort sortiert werden. Beachten Sie, dass das größte Ende zuerst sortiert wird, wobei kleinere Elemente länger brauchen, um an ihre richtige Position zu gelangen.

Obwohl Bubble-Sort einer der am einfachsten zu verstehenden und zu implementierenden Sortieralgorithmen ist, bedeutet seine O ( n 2 ) -Komplexität, dass seine Effizienz bei Listen mit mehr als einer kleinen Anzahl von Elementen dramatisch abnimmt. Selbst unter einfachen O ( n 2 )-Sortieralgorithmen sind Algorithmen wie Insertion Sort in der Regel wesentlich effizienter.

Aufgrund seiner Einfachheit wird Bubble Sort oft verwendet, um einführenden Informatikstudenten das Konzept eines Algorithmus oder eines Sortieralgorithmus vorzustellen . Einige Forscher wie Owen Astrachan haben jedoch große Anstrengungen unternommen, um die Blasensortierung und ihre anhaltende Popularität in der Informatikausbildung zu verunglimpfen, und empfahlen, dass sie nicht einmal mehr gelehrt wird.

Die Jargon-Datei , die Bogosort bekanntlich als "den archetypischen [sic] pervers schrecklichen Algorithmus" bezeichnet, nennt Bubblesort auch "den generischen schlechten Algorithmus". Donald Knuth kam in The Art of Computer Programming zu dem Schluss, dass "die Bubble-Sorte nichts zu empfehlen scheint, außer einem eingängigen Namen und der Tatsache, dass er zu einigen interessanten theoretischen Problemen führt", von denen er einige dann diskutiert.

Bubble-Sort ist im schlimmsten Fall in der Laufzeit asymptotisch äquivalent zu Insert-Sort, aber die beiden Algorithmen unterscheiden sich stark in der Anzahl der erforderlichen Swaps. Experimentelle Ergebnisse wie die von Astrachan haben auch gezeigt, dass Insertion Sort selbst auf Zufallslisten deutlich besser abschneidet. Aus diesen Gründen vermeiden viele moderne Algorithmuslehrbücher die Verwendung des Bubble-Sort-Algorithmus zugunsten der Insertion-Sortierung.

Bubble Sort interagiert auch schlecht mit moderner CPU-Hardware. Es produziert mindestens doppelt so viele Schreibvorgänge wie Insertion Sort, doppelt so viele Cache-Misses und asymptotisch mehr Verzweigungs-Fehlvorhersagen . Experimente von Astrachan, die Strings in Java sortieren, zeigen, dass die Bubble-Sortierung ungefähr ein Fünftel so schnell ist wie eine Insertion-Sortierung und 70% so schnell wie eine Selection-Sortierung .

In der Computergrafik ist Bubble-Sort beliebt wegen seiner Fähigkeit, einen sehr kleinen Fehler (wie den Austausch von nur zwei Elementen) in fast sortierten Arrays zu erkennen und ihn mit nur linearer Komplexität (2 n ) zu beheben . Es wird beispielsweise in einem Polygon-Füllalgorithmus verwendet, bei dem Begrenzungslinien nach ihrer x- Koordinate an einer bestimmten Scanlinie (einer Linie parallel zur x- Achse) sortiert werden und sich mit zunehmendem y ihre Reihenfolge (zwei Elemente werden vertauscht) nur bei . ändert Schnittpunkte zweier Linien. Bubble-Sort ist ein stabiler Sortieralgorithmus, wie der Insertion-Sort.

Variationen

  • Ungerade-gerade-Sortierung ist eine parallele Version von Bubble-Sort für Nachrichtenweiterleitungssysteme.
  • Pässe können von rechts nach links statt von links nach rechts erfolgen. Dies ist effizienter für Listen mit am Ende hinzugefügten unsortierten Elementen.
  • Cocktailshaker sortieren abwechselnd nach links und rechts.

Debatte um Namen

Blasensortierung wurde gelegentlich als "sinkende Sortierung" bezeichnet.

In Donald Knuths The Art of Computer Programming , Volume 3: Sorting and Searching beispielsweise stellt er in Abschnitt 5.2.1 'Sorting by Insertion' fest, dass [der Wert] sich auf das richtige Niveau einpendelt und dass diese Sortiermethode manchmal als Sieb- oder Versenktechnik bezeichnet .

Diese Debatte wird fortgeführt durch die Leichtigkeit, mit der man diesen Algorithmus aus zwei unterschiedlichen, aber gleichermaßen gültigen Perspektiven betrachten kann:

  1. Die größeren Werte können angesehen werden als schwerer und deshalb schrittweise zu sehen Enke zum Boden der Liste
  2. Die kleineren Werte könnten als leichter angesehen werden und sprudeln daher nach und nach an die Spitze der Liste.

In der Populärkultur

2007 fragte der ehemalige Google-Chef Eric Schmidt den damaligen Präsidentschaftskandidaten Barack Obama in einem Interview, wie man eine Million ganze Zahlen am besten sortieren kann ; Obama hielt einen Moment inne und antwortete: "Ich denke, die Art der Blase wäre der falsche Weg."

Anmerkungen

  1. ^ Cortesi, Aldo (27. April 2007). "Sortieralgorithmen visualisieren" . Abgerufen am 16. März 2017 .
  2. ^ "[JDK-6804124] (coll) Ersetzen Sie "modified mergesort" in java.util.Arrays.sort durch timsort - Java Bug System" . bugs.openjdk.java.net . Abgerufen 2020-01-11 .
  3. ^ Peters, Tim (2002-07-20). "[Python-Dev] Sortierung" . Abgerufen 2020-01-11 .
  4. ^ a b Astrachan, Owen (2003). "Bubble Sort: eine archäologische algorithmische Analyse" (PDF) . ACM SIGCSE-Bulletin . 35 (1): 1–5. doi : 10.1145/792548.611918 . ISSN  0097-8418 .
  5. ^ "Jargon, Knoten: bogo-sort" .
  6. ^ Donald Knuth . Die Kunst der Computerprogrammierung , Band 3: Sortieren und Suchen , Zweite Auflage. Addison-Wesley, 1998. ISBN  0-201-89685-0 . Seiten 106–110 in Abschnitt 5.2.2: Sortieren nach Austausch. „[A]obwohl die bei den Berechnungen verwendeten Techniken [zur Analyse der Blasensortierung] aufschlussreich sind, sind die Ergebnisse enttäuschend, da sie uns sagen, dass die Blasensortierung überhaupt nicht sehr gut ist. Verglichen mit der geraden Einfügung […], Blasensortierung erfordert ein komplizierteres Programm und dauert etwa doppelt so lange!" (Zitat aus der Erstausgabe, 1973.)
  7. ^ Schwarz, Paul E. (24. August 2009). "Blasensortierung" . Wörterbuch der Algorithmen und Datenstrukturen . Nationales Institut für Standards und Technologie . Abgerufen am 1. Oktober 2014 .
  8. ^ Lai Stirland, Sarah (2007-11-14). "Obama besteht sein Google-Interview" . Verkabelt . Abgerufen 2020-10-27 .
  9. ^ Barack Obama, Eric Schmidt (14. November 2007). Barack Obama | Kandidaten bei Google (Youtube). Mountain View, CA 94043 Der Googleplex: Gespräche bei Google. Die Veranstaltung findet um 23:20 Uhr statt. Archiviert vom Original (Video) am 7. September 2019 . Abgerufen am 18. September 2019 .CS1 Wartung: Standort ( Link )

Verweise

Externe Links