Bubblesort

Visualisierung von Bubblesort

Bubblesort (auch Sortieren durch Aufsteigen oder Austauschsortieren) ist ein Algorithmus, der vergleichsbasiert eine Liste von Elementen sortiert. Man vergleicht immer eine Zahl mit ihrem rechten Nachbarn. Ist der rechte Nachbar kleiner als die Zahl, so wird sie nach links verschoben. Nach dem ersten Durchgang ist die größte Zahl immer am Ende. Dieses Sortierverfahren arbeitet in-place, sortiert stabil und hat eine Laufzeit von <math>\Theta(n^2)</math> im schlimmsten Fall (Worst-Case) wie auch im durchschnittlichen Fall (Average-Case). Damit ist die Laufzeit asymptotisch nicht optimal. In der Praxis wird Bubblesort kaum eingesetzt, da andere Verfahren ein besseres Laufzeitverhalten haben. Der Algorithmus spielt allerdings in der Lehre eine Rolle, da er als einfach zu erklären bzw. zu demonstrieren gilt. Des Weiteren eignet sich der Algorithmus, um Techniken wie schrittweise Optimierungen, Laufzeit- bzw. Komplexitäts- und Korrektheitsanalyse einzuführen.

Prinzip

Datei:Bubble-sort-example-300px.gif

Bubblesort an einer Zahlenliste

In der Bubble-Phase wird die Eingabe-Liste von links nach rechts durchlaufen. Dabei wird in jedem Schritt das aktuelle Element mit dem rechten Nachbarn verglichen. Falls die beiden Elemente das Sortierkriterium verletzen, werden sie getauscht. Am Ende der Phase steht bei auf- bzw. absteigender Sortierung das größte bzw. kleinste Element der Eingabe am Ende der Liste.

Die Bubble-Phase wird solange wiederholt, bis die Eingabeliste vollständig sortiert ist. Dabei muss das letzte Element des vorherigen Durchlaufs nicht mehr betrachtet werden, da die restliche zu sortierende Eingabe keine größeren bzw. kleineren Elemente mehr enthält.

Je nachdem, ob auf- oder absteigend sortiert wird, steigen die größeren oder kleineren Elemente wie Blasen im Wasser (daher der Name) immer weiter nach oben, das heißt, an das Ende der Liste. Es werden stets zwei Zahlen miteinander in „Bubbles“ vertauscht.

Algorithmus

Um die Darstellung des Algorithmus zu vereinfachen, wird im Folgenden als Vergleichsrelation <math>></math> (größer als) verwendet. Wie bei jedem auf Vergleichen basierenden Sortierverfahren kann diese auch durch eine andere Relation ersetzt werden, die eine totale Ordnung definiert.

Der Algorithmus in seiner einfachsten Form als Pseudocode:

<syntaxhighlight lang="C"> bubbleSort(Array A)

 for (n = A.size; n > 1; n = n - 1) { // äußere Schleife
   for (i = 0; i < n - 1; i = i + 1) { // innere Schleife
     if (A[i] > A[i + 1]) {
       A.swap(i, i + 1)
     }
   } 
 }

</syntaxhighlight>

Die Eingabe ist in einem Array gespeichert. Die äußere Schleife verringert schrittweise die rechte Grenze für die Bubble-Phase, da nach jedem Bubblen an der rechtesten Position das größte Element der jeweils unsortierten Rest-Eingabe steht. In der inneren Schleife wird der noch nicht sortierte Teil des Feldes durchlaufen. Dabei werden zwei benachbarte Daten vertauscht, wenn sie in falscher Reihenfolge sind (also das Sortierkriterium verletzen).

Allerdings nutzt diese einfachste Variante nicht die Eigenschaft aus, dass nach einer Iteration, in der keine Vertauschungen stattfanden, auch in den restlichen Iterationen keine Vertauschungen mehr stattfinden. Der folgende Pseudocode berücksichtigt dies:

<syntaxhighlight lang="javascript" line="1"> bubbleSort2(Array A)

 n = A.size
 do { // äußere Schleife
   swapped = false
   for (i = 0; i < n - 1; i = i + 1) { // innere Schleife
     if (A[i] > A[i + 1]) {
       A.swap(i, i + 1)
       swapped = true
     }
   }
   n = n - 1
 } while (swapped)

</syntaxhighlight>

Die äußere Schleife durchläuft die zu sortierenden Daten, bis keine Vertauschungen mehr notwendig sind.

Beispiel

Eine Reihe von fünf Zahlen soll aufsteigend sortiert werden.

Die fett gedruckten Zahlen werden jeweils verglichen. Ist die linke größer als die rechte, so werden beide vertauscht; das Zahlenpaar ist dann blau markiert. Im ersten Durchlauf wandert somit die größte Zahl ganz nach rechts. Der zweite Durchlauf braucht somit die letzte und vorletzte Position nicht mehr zu vergleichen. → Dritter Durchlauf: kein Vergleich letzte/vorletzte/vorvorletzte…

55 07 78 12 42 1. Durchlauf 07 55 78 12 42 07 55 78 12 42 07 55 12 78 42 Letzter Vergleich 07 55 12 42 78 2. Durchlauf 07 55 12 42 78 07 12 55 42 78 Letzter Vergleich 07 12 42 55 78 3. Durchlauf 07 12 42 55 78 Letzter Vergleich 07 12 42 55 78 4. Durchlauf + Letzter Vergleich 07 12 42 55 78 Fertig sortiert.

Komplexität

Datei:Bubblesort Animation.gif

Beispiel, wie Bubblesort eine Liste sortiert. Die Listenelemente werden durch Balken dargestellt. Die x-Achse gibt an, wo sich ein Element in der Liste befindet; die Höhe gibt an, wie groß ein Element ist. Ein Frame entspricht einem Durchlauf.
(Animation starten)

Ungünstigster Fall

Bubblesort hat die Laufzeit <math> \mathcal{O}(n^2) </math> für Listen der Länge <math>n</math>. Im Falle der umgekehrt sortierten Liste <math>(n, n-1, \dotsc, 2, 1)</math> werden maximal <math>\tfrac{n\cdot (n-1)}{2}</math> viele Vertauschungen ausgeführt: um das erste (und größte) Element <math>n</math> ganz nach rechts zu bewegen, werden <math>n-1</math> Vertauschungen vorgenommen. Allgemein: Die Bewegung des <math>k</math>-ten Elements an die Stelle <math>n</math> wird durch <math>n-k</math> Vertauschungen vollzogen. Aufsummieren über alle <math>k</math> ergibt im Ganzen <math> \tfrac{1}{2}(n^2-n)\in\mathcal{O}(n^2)</math> Vertauschungen. Da nur Paare vertauscht werden, die auch vorher verglichen wurden, benötigt der Algorithmus auch mindestens ebenso viele Vergleiche. Betrachtet man den Pseudocode des Algorithmus, so sieht man leicht ein, dass keine der Anweisungen öfter als <math>\tfrac{1}{2}(n^2-n)</math> -mal ausgeführt werden kann, also ist dies auch die bestmögliche untere Schranke.

Bester Fall

Bei einer bereits sortierten Liste wird Bubblesort die Liste nur einmal durchgehen, d. h., es gibt nur einen Durchgang, um festzustellen, dass die Liste bereits sortiert ist, weil keine benachbarten Elemente vertauscht werden mussten. Daher benötigt Bubblesort <math> \mathcal{O}(n) </math> Schritte, um eine bereits sortierte Liste zu bearbeiten.

Falls die Elemente der Liste bereits nah den Stellen sind, die sie nach der Sortierung bekommen sollen, ist die Laufzeit erheblich besser als <math> \mathcal{O}(n^2) </math>.

Durchschnittlicher Fall

Die erwartete Anzahl der Vergleiche für eine zufällig gewählte Permutation der Liste <math>(1, 2, \dotsc, n)</math> ist

<math>\frac{1}{2}\left(n^2-n\cdot \ln n - (\gamma+\ln(2) - 1)\cdot n \right)+\mathcal O(\sqrt{n})</math>,

wobei <math>\gamma</math> die Euler-Mascheroni-Konstante bezeichnet; die erwartete Anzahl der Vertauschungen beträgt <math>\tfrac{1}{4}(n^2-n)</math>.<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0201896850}} | {{bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 108–109
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ =

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

}}

| {{#if:||{{#if:{{#invoke:URIutil|plainISBN|0201896850}}|Der BibISBN-Eintrag [[Vorlage:BibISBN/{{#invoke:URIutil|plainISBN|0201896850}}]] ist nicht vorhanden. Bitte prüfe die ISBN und lege ggf. einen {{#ifeq:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}|Bubblesort|{{#switch:{{{LINK}}}|JA=|NEIN=}}}}[[[:Vorlage:Neuer Abschnitt/URL]] neuen Eintrag] an.|Die angegebene ISBN „0201896850“ ist fehlerhaft. Bitte prüfe und korrigiere die ISBN.}}{{#ifeq: 0 | 0 | }}}}}}</ref>

Abgrenzung

Auch wenn Bubblesort nicht asymptotisch optimal ist, kann ein Einsatz für kleine Eingaben in Frage kommen, da für kleine <math>n</math> die konstanten Laufzeitfaktoren eines Sortieralgorithmus dominieren, welche bei Bubblesort klein sind. Ein Anwendungsfall wäre die Verwendung von Bubblesort innerhalb eines rekursiv arbeitenden Sortierverfahrens, um die Anzahl an Rekursionen zu verringern.

Wenn die Elemente eines Feldes oder einer Liste (bis zu einer bestimmten Anzahl) mit einer hohen Wahrscheinlichkeit schon sortiert sind, eignet sich Bubblesort, da dies der Best-Case ist, in dem der Algorithmus eine lineare Laufzeit hat. Im Gegensatz dazu haben andere effiziente Sortierverfahren, wie z. B. Quicksort, oder asymptotisch optimale Verfahren, wie beispielsweise Mergesort, einen Best-Case von <math>\mathcal{O}(n\log n)</math>.

Unter diesem Aspekt konkurriert Bubblesort mit Insertionsort, dessen Best-Case eine schon sortierte Folge ist und welches die gleiche Komplexität wie Bubblesort aufweist (wie auch im Average- und Worst-Case). Für beide Sortierverfahren gilt: Sie sind stabil und arbeiten in-place. Je nach Implementation hat Insertionsort jedoch geringere konstante Laufzeitfaktoren als Bubblesort.

Hasen und Schildkröten

Die Position der Elemente vor dem Sortieren ist entscheidend für den Sortieraufwand von Bubblesort. Große Elemente zu Beginn wirken sich nicht negativ aus, da sie schnell nach hinten getauscht werden; kleine Elemente am Ende bewegen sich jedoch nur langsam nach vorn. Deshalb bezeichnet man die schnell getauschten Elemente als Hasen und die langsamen als Schildkröten.

Combsort (oder auch Gapsort genannt) ist der schnellste auf Bubblesort beruhende Algorithmus. Im Unterschied zu Bubblesort werden hier weit voneinander entfernt liegende Elemente miteinander verglichen und vertauscht, um das Dilemma von langsam wandernden Elementen zu vermeiden. Seine Laufzeit liegt im Worst-Case ebenso bei <math>\mathcal{O}(n^2)</math> und im Best-Case bei <math>\mathcal{O}(n\log \sqrt{n})</math> (Bubblesort: <math>\mathcal{O}(n)</math>). Damit erreicht Combsort im Worst- und im Best-Case die gleiche Komplexität wie Quicksort.

Cocktailsort (oder auch Shakersort genannt) ist ein alternierender Sortieralgorithmus, der die Elemente von der linken zur rechten Seite und von der rechten zur linken Seite wandern lässt. Damit wird ebenso dem Problem von nur langsam nach vorn wandernden Elementen entgegengewirkt. Aufgrund der Alternierung wird dieser Algorithmus auch Bidirectional-Bubblesort genannt. Im Worst-Case liegt seine Laufzeit, wie die von Bubblesort, in <math>\mathcal{O}(n^2)</math>.

Oyelami O.M. veröffentlichte im Jahr 2009 eine optimierte Version von Bubblesort, welche den Worst-Case für umgekehrt sortierte Felder/Listen vermeidet. Aufgrund der damit einhergehenden Sortierung über Distanz ist der von ihm verwendete Algorithmus nicht mehr stabil. In Anlehnung an das obige „bubbleSort3“ wird nachfolgend ein optimierter „bidirektionaler Bubblesort“ mittels „papyrus script function“ veranschaulicht. Float[] a ist dabei beispielhaft der Zeiger auf ein Array mit Fließkommazahlen. Die beiden integer-Parameter stellen den flexiblen Sortierbereich für das Array dar (Startwert „L“, Endwert „R“). Angenommen das Array hat 99 Elemente und beginnt bei 0, dann muss L=0 und R=98 gesetzt werden, um es vollständig zu sortieren.

<syntaxhighlight lang="C"> void sortByBubble3(float a[], int L, int R) {

 float X; // pivot element
 float f; // temp element for swap
 int m;   // last swap position
 int i;   // counter

 // round 1: suggested by Oyelami
 i = L;
 m = R;
 while (i < m) {    // to avoid worst-case by using an array sorted in reverse order
   X = a[i];
   f = a[m];
   if (X > f) {
     a[m] = X;
     a[i] = f;
   }
   i = i + 1;
   m = m - 1;
 }

 // round 2: optimized bi-directional BubbleSort
 while (L < R) {
   X = a[L];
   m = L - 1;       // init "m" out of sorting range related to Left bound
   i = L + 1;
   while (i <= R) { // -- BottomUp loop -- sorts to maximum at the end
     f = a[i];
     if (X <= f) {
       X = f;       // no exchange: set "pivot" to follower element
     } else {
       a[i] = X;    // \ swap two elements
       m = i - 1;   // - update "last swap" position
       a[m] = f;    // / and keep current "pivot" for next comparison
     }
     i = i + 1;
   }
   R = R - 1;
   if (R > m) {
     if (L < m) {
       R = m;       // shrink the Right bound as much as possible
     } else {
       R = L;       // no swap last time, break the loop!
     }
   }
   X = a[R];
   m = R + 1;       // init "m" out of sorting range related to Right bound
   i = R - 1;
   while (i >= L) { // -- TopDown loop -- sorts to minimum on start
     f = a[i];
     if (X >= f) {
       X = f;       // no exchange: set "pivot" to follower element
     } else {
       a[i] = X;    // \ swap two elements
       m = i + 1;   // - update "last swap" position
       a[m] = f;    // / and keep current "pivot" for next comparison
     }
     i = i - 1;
   }
   L = L + 1;
   if (L < m) {
     if (R > m) {
       L = m;
     } else {
       L = R;       // no swap last time, break the loop!
     }
   }
 }

} </syntaxhighlight>

Literatur

{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0262032937}}

| {{bibISBN/{{#invoke:URIutil|plainISBN|0262032937}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0262032937}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 38
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ =

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

}}

| {{#if:||{{#if:{{#invoke:URIutil|plainISBN|0262032937}}|Der BibISBN-Eintrag [[Vorlage:BibISBN/{{#invoke:URIutil|plainISBN|0262032937}}]] ist nicht vorhanden. Bitte prüfe die ISBN und lege ggf. einen {{#ifeq:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0262032937}}|Bubblesort|{{#switch:{{{LINK}}}|JA=|NEIN=}}}}[[[:Vorlage:Neuer Abschnitt/URL]] neuen Eintrag] an.|Die angegebene ISBN „0262032937“ ist fehlerhaft. Bitte prüfe und korrigiere die ISBN.}}{{#ifeq: 0 | 0 | }}}}}}

{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}

| {{bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 106–110
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ =

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

}}

| {{#if:||{{#if:{{#invoke:URIutil|plainISBN|0201896850}}|Der BibISBN-Eintrag [[Vorlage:BibISBN/{{#invoke:URIutil|plainISBN|0201896850}}]] ist nicht vorhanden. Bitte prüfe die ISBN und lege ggf. einen {{#ifeq:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|0201896850}}|Bubblesort|{{#switch:{{{LINK}}}|JA=|NEIN=}}}}[[[:Vorlage:Neuer Abschnitt/URL]] neuen Eintrag] an.|Die angegebene ISBN „0201896850“ ist fehlerhaft. Bitte prüfe und korrigiere die ISBN.}}{{#ifeq: 0 | 0 | }}}}}}

Weblinks

[{{canonicalurl:Commons:Category:{{#if:Bubble sort|Bubble sort|Bubblesort}}|uselang=de}} Commons: {{#if:Bubblesort|Bubblesort|{{#if:Bubble sort|Bubble sort|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if:

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if: Bubble sort

   | {{#ifeq: {{#invoke:Str|left|bubble sort|9}} 
       | category:

| FEHLER: Ohne Category: angeben!}}}}

Vorlage:Wikidata-Registrierung

Sammlung von Bubblesort-Implementierungen (Wikibooks)
<templatestyles src="Webarchiv/styles.css" />{{#if:20220927233612

      | {{#ifeq: 20220927233612 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes | {{#invoke:WLink|getEscapedTitle|Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes}} | {{#invoke:Webarchiv|getdomain|https://www.schnatterente.net/software/bubble-sort-volkstanz}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20220927233612}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes | {{#invoke:WLink|getEscapedTitle|Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes}} | {{#invoke:Webarchiv|getdomain|https://www.schnatterente.net/software/bubble-sort-volkstanz}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20220927233612}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes | {{#invoke:WLink|getEscapedTitle|Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes}} | {{#invoke:Webarchiv|getdomain|https://www.schnatterente.net/software/bubble-sort-volkstanz}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes | {{#invoke:WLink|getEscapedTitle|Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes}} | {{#invoke:Webarchiv|getdomain|https://www.schnatterente.net/software/bubble-sort-volkstanz}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes | {{#invoke:WLink|getEscapedTitle|Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes}} | {{#invoke:Webarchiv|getdomain|https://www.schnatterente.net/software/bubble-sort-volkstanz}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes | {{#invoke:WLink|getEscapedTitle|Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes}} | {{#invoke:Webarchiv|getdomain|https://www.schnatterente.net/software/bubble-sort-volkstanz}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20220927233612|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|https://www.schnatterente.net/software/bubble-sort-volkstanz}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes
    | {{#if: {{#invoke:WLink|isBracketedLink|Bubblesort, einfach erklärt anhand eines ungarischen Volkstanzes}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|https://www.schnatterente.net/software/bubble-sort-volkstanz%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|https://www.schnatterente.net/software/bubble-sort-volkstanz%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|https://www.schnatterente.net/software/bubble-sort-volkstanz }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}

Improving the performance of bubble sort (PDF)

Einzelnachweise

no:Sorteringsalgoritme#Boblesortering