WikiDer > Bubblesort

Bubblesort
Blasensortierung
Bubblesort bearbeitete Farbe

Blasensortierung, manchmal auch Austausch sortieren oder sinkende Art erwähnt, ist ein einfaches Sortieralgorithmus. Es ist ein einfacher Algorithmus, aber ineffizient. Es wird wegen seiner Einfachheit und einfachen Erklärung oft als Algorithmus-Darstellung verwendet. Der Name des Algorithmus kommt von der Analogie einer Blase in einer Flüssigkeit, die nach oben schwimmt, genau wie die größeren Elemente an der Spitze der Liste 'schwimmen'.

Operation

Ein Beispiel für Blasensortierung. Vergleichen Sie ausgehend vom Anfang der Reihe jedes benachbarte Zahlenpaar, vertauschen Sie sie, wenn die linke Zahl größer als die rechte ist, und verschieben Sie dann eine Position. Nachdem die gesamte Reihe beendet ist, muss bei der nächsten Wiederholung ein Element weniger sortiert werden, da die letzte Zahl sicherlich die höchste ist.

Bubblesort funktioniert so:

  • 1. Gehen Sie durch die Reihe von n zu sortierenden Elementen und vergleichen Sie jedes Element mit dem nächsten. Tauschen Sie beide aus, wenn sie in der falschen Reihenfolge sind. Gehen Sie dann einen Schritt nach oben.
  • 2. Gehen Sie die Reihe erneut durch, diesmal jedoch bis zum vorletzten Element, da das letzte Element das größte in der Reihe war.
  • 3. Auch hier, aber ignorieren Sie die letzten beiden Elemente.
  • 4. Mach weiter so.
  • n. Wieder, aber ignorieren Sie dann die letzten n-1 Zahlen.
  • n 1. Fertig.

Wir sehen die größeren Elemente sozusagen wie Luftblasen nach oben schweben. Der Algorithmus hat seinen Namen von dieser Metapher.

Bubblesort ist mit a Größenordnung, ziemlich ineffizient. Die effizientesten Sortieralgorithmen (wie zum Beispiel Zusammenführen, sortieren) haben einen Komplexitätsgrad von

Wenn Sie nachverfolgen, wie viele Verwechslungen bei jedem Durchlaufen der Liste gemacht wurden, können Sie vorzeitig aufhören, sobald keine Verwechslungen mehr erforderlich sind. Im praktischen Sinne kann dies eine Verbesserung gegenüber der theoretischen Laufzeit des Bubble-Sort-Algorithmus darstellen.

Implementierungen

Umsetzung in Visual Basic 6

PrivatgeländeSubFormular_Klick()trübeichAscheGanze ZahltrübevAscheBooleschestrübejaAscheganze ZahltrübetempAscheganze Zahltrübearr(4)AscheGanze Zahlarr(1)=31arr(2)=2252arr(3)=12arr(4)=41ich=1v=wahrTunwährendich<4Undv=wahrv=Falschja=1Tunwährendja<=4-ichwennarr(ja)>arr(ja1)danntemp=arr(ja)arr(ja)=arr(ja1)arr(ja1)=tempv=wahrEndewennja=ja1gehenich=ich1gehenMich.clszumich=1zu4druckenarr(ich)NächsterichEndeSub

Umsetzung in PHP

$v=wahr;$arr=Array(31,56,8,211);$Anzahl=Anzahl($arr)-1;zum($i=0;($i<$Anzahl)&&($v==wahr);$i){$v=falsch;zum($y=0;$y<($Anzahl-$i);$y){wenn($arr[$y]>$arr[$y1]){$Temp=$arr[$y];$arr[$y]=$arr[$y1];$arr[$y1]=$Temp;$v=wahr;}}}print_r($arr);?>

Effiziente Umsetzung in PHP

FunktionBubbleSort(&$arr,$asc=wahr){$iterationen=0;$len=Anzahl($arr);$i=0;$bestellt=falsch;$neuLen=$len;während(!$bestellt):$bestellt=wahr;zum($i=1;$i<$len;$i ):$iterationen;$a=$arr[$i-1];$b=$arr[$i];$comp=(schweben)((schweben)$a-(schweben)$b);wenn(($asc&&$comp>0)||(!$asc&&$comp<0)):$arr[$i-1]=$b;$arr[$i]=$a;$bestellt=falsch;$neuLen=$i;endif;endfor;$len=$neuLen;Endzeit;Rückkehr($iterationen);}$arr=Array(4,4,3,2,4,5,88,3,8448,43,2,0,480,334,1,0);$iterationen=BubbleSort($arr);Echo("es dauerte".$iterationen." Iterationen, um das Array zu sortieren.");print_r($arr);

Umsetzung in Java

ÖffentlichkeitLeereBubbleSort(int[]Eingang){intich,ja,vorübergehend;zum(ja=0;ja<Eingang.Länge;ja){zum(ich=1;ich<Eingang.Länge-ja;ich){wenn(Eingang[ich-1]>Eingang[ich]){vorübergehend=Eingang[ich];Eingang[ich]=Eingang[ich-1];Eingang[ich-1]=vorübergehend;}}}}

Umsetzung in C

"Input" ist das zu sortierende Array, "length" ist die Anzahl der Elemente im Array.

LeereBlase sortieren(intEingang[],intLänge){intich,ja,vorübergehend;zum(ja=0;ja<Länge;ja){zum(ich=1;ich<Länge-ja;ich){wenn(Eingang[ich-1]>Eingang[ich]){vorübergehend=Eingang[ich];Eingang[ich]=Eingang[ich-1];Eingang[ich-1]=vorübergehend;}}}}

Umsetzung in MATLAB

"x" ist das zu sortierende Array.

vorübergehend=0;zumja=1:Länge(X),zumich=1:Länge(X)-ja,wennX(ich)>X(ich1),vorübergehend=X(ich1);X(ich1)=X(ich);X(ich)=vorübergehend;EndeEndeEnde

Bereitstellung in C# (Csharp)

ÖffentlichkeitLeereBubbleSort(int[]t){intX;zum(intich=t.Länge-1;ich>=1;ich--){zum(intja=0;ja<t.Länge-1;ja  ){wenn(t[ja]>t[ja1]){X=t[ja];// den Inhalt von t[j] verfolgent[ja]=t[ja1];// Inhalt von t[j] wird kleiner Inhalt von t[j 1]t[ja1]=X;// Inhalt von t[j 1] wird der größere Inhalt des ursprünglichen t[j] oder damit x }}}}

Umsetzung in Python

Iterative Implementierung

Als Parameter wird die zu sortierende Zeile eingetragen.
(Update) Durch einen Offset können wir die Geschwindigkeit des iterativen Algorithmus erhöhen.
Die Länge der nächsten Iteration wird verkürzt. Dies kommt sowohl dem Platzverbrauch als auch dem Zeitverbrauch des Prozessors zugute
Wir wissen, dass nach jeder Iteration über die Liste das back-Element entfernt werden kann.
Auch die Verwendung von zwei for-Schleifen ist möglich, wie in den anderen Programmiersprachen ausführlich dargestellt.

defBlase sortieren(Warteschlange):Versatz=1währendwahr:#Endlosschleifegetauscht=FalschzumichimReichweite(len(Warteschlange)-Versatz):wennWarteschlange[ich]>Warteschlange[ich1]:Warteschlange[ich],Warteschlange[ich1]=Warteschlange[ich1],Warteschlange[ich]#Tauschengetauscht=wahrVersatz =1wennnichtgetauscht:#Schleife beenden, wenn alles am richtigen Platz istRückkehrWarteschlange

Iteratives Beispiel

Hier sortieren wir eine zufällige Reihe von Wörtern und geben jedes Mal an, welche zwei aufeinanderfolgenden Wörter vertauscht werden (d. h. vertauschen).

['Stoff','Grün','Esel','Fahrrad','Apfel','Baum','Zitrone']Tauschen(Grün,Esel)Tauschen(Grün,Fahrrad)Tauschen(Grün,Apfel)Tauschen(Grün,Baum)Tauschen(Grün,Zitrone)['Stoff','Esel','Fahrrad','Apfel','Baum','Zitrone','Grün']Tauschen(Fahrrad,Apfel)Tauschen(Fahrrad,Baum)Tauschen(Fahrrad,Zitrone)['Stoff','Esel','Apfel','Baum','Zitrone','Fahrrad','Grün']Tauschen(Esel,Apfel)Tauschen(Esel,Baum)Tauschen(Esel,Zitrone)['Stoff','Apfel','Baum','Zitrone','Esel','Fahrrad','Grün']Tauschen(Stoff,Apfel)Tauschen(Stoff,Baum)Tauschen(Stoff,Zitrone)['Apfel','Baum','Zitrone','Stoff','Esel','Fahrrad','Grün']

Iteratives Beispiel mit Offset

['Stoff','Grün','Esel','Fahrrad','Apfel','Baum','Zitrone']Tauschen(Grün,Esel)Tauschen(Grün,Fahrrad)Tauschen(Grün,Apfel)Tauschen(Grün,Baum)Tauschen(Grün,Zitrone)['Stoff','Esel','Fahrrad','Apfel','Baum','Zitrone']Tauschen(Fahrrad,Apfel)Tauschen(Fahrrad,Baum)Tauschen(Fahrrad,Zitrone)['Stoff','Esel','Apfel','Baum','Zitrone']Tauschen(Esel,Apfel)Tauschen(Esel,Baum)Tauschen(Esel,Zitrone)['Stoff','Apfel','Baum','Zitrone']Tauschen(Stoff,Apfel)Tauschen(Stoff,Baum)Tauschen(Stoff,Zitrone)['Apfel','Baum','Zitrone']!NEINSWAPSMEHR!=>Rückkehr['Apfel','Baum','Zitrone','Stoff','Esel','Fahrrad','Grün']

Rekursive Implementierung

Bubblesort hat die interessante Eigenschaft, dass bei jedem Schritt der größte Wert aus dem unsortierten Teil rückwärts 'bubble'.Der 'bubble back' wird von der Funktion bubUp behandelt. Das Blubbern wird durch den Tausch (Veränderung von zwei Elementen) verursacht. row[:1] gibt uns eine Liste, die nur das erste Element enthält. row[1:] gibt uns eine Liste aller nachfolgenden Elemente. Auf letzterem führen wir bubUp rekursiv erneut aus. Auf diese Weise reduzieren wir unsere Reihe systematisch, bis es nur noch ein Element in unserer Reihe gibt, nämlich das größte.

Die bub-Funktion über bubUp bläst das größte zurück, knallt das letzte (größte) der Reihe und setzt die Reihe ohne dieses letzte Element fort, bis es nur noch ein Element in der Reihe gibt, das das kleinste Element der ursprünglichen Reihe ist. 

defBlase sortieren(Warteschlange):defbub(Warteschlange):wennlen(Warteschlange)<=1:#Bedingungsfehler stoppenRückkehrWarteschlangesonst:Warteschlange=bubUp(Warteschlange)#Blase die größte nach hinten (und sortiere ein bisschen)letzte=[Warteschlange.Puppe()]#Entferne den größtenRückkehrbub(Warteschlange)letzte#Rekursiver AufrufdefbubUp(Warteschlange):wennlen(Warteschlange)<=1:#Stoppbedingung bubUpRückkehrWarteschlangesonst:wennWarteschlange[0]>Warteschlange[1]:Warteschlange[0],Warteschlange[1]=Warteschlange[1],Warteschlange[0]#Tauschen Sie das erste mit dem zweitenRückkehrWarteschlange[:1]bubUp(Warteschlange[1:])#Rekursiver Aufruf Rückkehrbub(Warteschlange)#Startbedingung für die Blasensortierung

Rekursives Beispiel

Die Ausgabe des obigen Codes in einer zufälligen Zeile.

['Zitrone','Baum','Esel','Apfel','Stoff','Fahrrad','Grün']Puppe(['Grün'])['Baum','Zitrone','Apfel','Stoff','Esel','Fahrrad']Puppe(['Fahrrad'])['Baum','Apfel','Zitrone','Stoff','Esel']Puppe(['Esel'])['Apfel','Baum','Zitrone','Stoff']Puppe(['Stoff'])['Apfel','Baum','Zitrone']Puppe(['Zitrone'])['Apfel','Baum']Puppe(['Baum'])['Apfel']['Apfel','Baum']['Apfel','Baum','Zitrone']['Apfel','Baum','Zitrone','Stoff']['Apfel','Baum','Zitrone','Stoff','Esel']['Apfel','Baum','Zitrone','Stoff','Esel','Fahrrad']['Apfel','Baum','Zitrone','Stoff','Esel','Fahrrad','Grün']

Siehe auch