Blasensortierung erklärt

Genau wie die Art und Weise, wie Blasen vom Boden eines Glases aufsteigen, ist die Blasensortierung ein einfacher Algorithmus, der eine Liste sortiert, sodass entweder niedrigere oder höhere Werte nach oben sprudeln können. Der Algorithmus durchläuft eine Liste, vergleicht benachbarte Werte und tauscht sie aus, wenn sie nicht in der richtigen Reihenfolge vorliegen.

Mit einer Worst-Case-Komplexität von O (n ^ 2) ist die Blasensortierung im Vergleich zu anderen Sortieralgorithmen wie Quicksort sehr langsam. Der Vorteil ist, dass es einer der am einfachsten zu verstehenden und von Grund auf neu zu codierenden Sortieralgorithmen ist.

Beispiel:

let arr = [4, 2, 6, 3, 9]; let sorted = false while(!sorted) { sorted = true for(var i = 0; i < arr.length; i++) { if(arr[i] < arr[i - 1]) { let temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; sorted = false; } } }

Gehen Sie zuerst die Liste durch:

  • Beginnend [4, 2, 6, 3, 9]vergleicht der Algorithmus die ersten beiden Elemente im Array 4 und 2. Er tauscht sie aus, weil 2 <4:[2, 4, 6, 3, 9]
  • Es werden die nächsten beiden Werte 4 und 6 verglichen. Da 4 <6, sind diese bereits in Ordnung, und der Algorithmus fährt fort: [2, 4, 6, 3, 9]
  • Die nächsten beiden Werte werden ebenfalls vertauscht, da 3 <6: [2, 4, 3, 6, 9]
  • Die letzten beiden Werte 6 und 9 sind bereits in Ordnung, sodass der Algorithmus sie nicht austauscht.

Zweiter Durchgang durch die Liste:

  • 2 <4, sodass keine Positionen getauscht werden müssen: [2, 4, 3, 6, 9]
  • Der Algorithmus tauscht die nächsten beiden Werte aus, da 3 <4: [2, 3, 4, 6, 9]
  • Kein Tausch als 4 <6: [2, 3, 4, 6, 9]
  • Wieder 6 <9, so dass kein Tausch stattfindet: [2, 3, 4, 6, 9]

Die Liste ist bereits sortiert, aber der Blasensortierungsalgorithmus erkennt dies nicht. Vielmehr muss ein vollständiger Durchlauf durch die Liste durchgeführt werden, ohne dass Werte ausgetauscht werden müssen, um zu wissen, dass die Liste sortiert ist.

Dritter Durchgang durch die Liste:

  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]

Die Blasensortierung ist eindeutig weit vom effizientesten Sortieralgorithmus entfernt. Trotzdem ist es einfach, den Kopf herumzureißen und sich selbst umzusetzen.

Gießen Sie sich jetzt ein kaltes, sprudelndes Getränk ein - Sie haben es verdient.