Dieser Inhalt wurde automatisch aus dem Ukrainischen übersetzt.
Bubble Sort - ist einer der einfachsten Sortieralgorithmen. Sein Wesen besteht darin, benachbarte Elemente eines Arrays zu vergleichen und sie zu vertauschen, wenn sie in der falschen Reihenfolge stehen. So "steigt" das "schwierigste" Element allmählich ans Ende des Arrays, wie eine Blase im Wasser, daher der Name des Algorithmus.
Wie es einfach funktioniert:
- Wir nehmen ein Array von Zahlen
- Wir vergleichen die erste Zahl mit der zweiten
- Wenn die erste größer ist als die zweite - tauschen wir sie
- Wir gehen zum nächsten Paar über und wiederholen
- Wir wiederholen den gesamten Prozess mehrere Male, bis das Array sortiert ist
Beispiel einer Implementierung in Ruby:
def bubble_sort(array)
n = array.length
loop do
swapped = false
(n-1).times do |i|
if array[i] > array[i+1]
array[i], array[i+1] = array[i+1], array[i]
swapped = true
end
end
break unless swapped
end
array
end
numbers = [5, 2, 9, 1, 5, 6]
sorted_numbers = bubble_sort(numbers)
So etwas werdet ihr im Terminal sehen:
- swapped verfolgt, ob es Änderungen im aktuellen Durchgang gab
- Wenn es in einem Durchgang keine Änderungen gab - ist das Array sortiert und man kann aufhören
- array[i], array[i+1] = array[i+1], array[i] tauscht zwei Elemente
Bubble Sort ist einfach zu verstehen, aber für große Arrays ist er langsam, daher werden für praktische Aufgaben oft schnellere Sortieralgorithmen verwendet.
