Ta treść została automatycznie przetłumaczona z ukraińskiego.
Bubble Sort - to jeden z najprostszych algorytmów sortowania. Jego istota polega na porównywaniu sąsiednich elementów tablicy i zamienianiu ich miejscami, jeśli są w niewłaściwej kolejności. W ten sposób "najcięższy" element stopniowo "wypływa" na koniec tablicy, jak bąbelek w wodzie, stąd nazwa algorytmu.
Jak to działa prostymi słowami:
- Bierzemy tablicę liczb
- Porównujemy pierwszą liczbę z drugą
- Jeśli pierwsza jest większa od drugiej - zamieniamy je miejscami
- Przechodzimy do następnej pary i powtarzamy
- Powtarzamy cały proces kilka razy, aż tablica będzie posortowana
Przykład implementacji w języku 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)
Typu coś takiego zobaczycie w terminalu:
- swapped śledzi, czy były zmiany w bieżącej iteracji
- Jeśli w jednym przejściu nie było zmian - tablica jest posortowana i można się zatrzymać
- array[i], array[i+1] = array[i+1], array[i] zamienia miejscami dwa elementy
Bubble Sort jest prosty do zrozumienia, ale dla dużych tablic jest wolny, dlatego w praktycznych zadaniach często używa się szybszych algorytmów sortowania.
