Algorytmy / Home / Sortowanie

Sortowanie bąbelkowe

Spis odnośników

Sortowanie bąbelkowe – prosty algorytm sortujący

#Sortowanie bąbelkowe (ang. bubble sort) to jeden z najprostszych algorytmów sortujących, często omawiany na początku nauki programowania. Choć nie jest najwydajniejszy, warto go poznać, aby zrozumieć podstawy algorytmów sortujących. Na czym polega sortowanie bąbelkowe?

Opis działania Sortowania Bąbelkowego

Zasada działania
Sortowanie bąbelkowe to #algorytm, który porównuje sąsiednie elementy listy i zamienia je miejscami, jeśli są w złej kolejności. Proces ten powtarza się, aż cała lista będzie posortowana. Największe wartości „wypływają” na powierzchnię, podobnie jak bąbelki w wodzie – stąd nazwa.
Kroki algorytmu

Przechodź przez listę element po elemencie.
Porównuj sąsiednie elementy.
Jeśli pierwszy element jest większy niż drugi, zamień je miejscami.
Powtarzaj proces, aż lista będzie uporządkowana.

Przykład
Dla listy [5, 2, 9, 1, 5]:
- Porównaj 5 i 2 → zamień, lista to [2, 5, 9, 1, 5].
- Porównaj 5 i 9 → bez zmian.
- Porównaj 9 i 1 → zamień, lista to [2, 5, 1, 9, 5].
- Porównaj 9 i 5 → zamień, lista to [2, 5, 1, 5, 9].
- Kolejne przejścia wykonują dalsze zamiany, aż cała lista będzie posortowana.
Złożoność obliczeniowa
Sortowanie bąbelkowe ma złożoność czasową O(n²), co oznacza, że nie jest wydajne dla dużych zbiorów danych. Każdy element musi być porównany z wieloma innymi, co sprawia, że algorytm ten działa wolniej niż inne, bardziej zaawansowane techniki, takie jak quicksort czy mergesort.
Zastosowania
Ze względu na swoją prostotę, sortowanie bąbelkowe jest wykorzystywane głównie do celów edukacyjnych. W rzeczywistych projektach używa się bardziej efektywnych algorytmów, jednak sortowanie bąbelkowe doskonale nadaje się do nauki i eksperymentów z prostymi strukturami danych.

Implementacje Sortowania Bąbelkowego w różnych językach

Implementacja Sortowania Bąbelkowego w #Python

1
2
3
4
5
6
7
8
9
10
11
12

def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr

# Przykład użycia:
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Posortowana lista:", sorted_arr)

Kod Sortowania Bąbelkowego w #JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13

Implementacja Sortowania Bąbelkowego w #Pascal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

program BubbleSort;

procedure BubbleSort(var arr: array of Integer; n: Integer);
var
i, j, temp: Integer;
begin
for i := 0 to n - 1 do
for j := 0 to n - i - 2 do
if arr[j] > arr[j + 1] then
begin
temp := arr[j];
arr[j] := arr[j + 1];
arr[j + 1] := temp;
end;
end;

var
arr: array[1..7] of Integer = (64, 34, 25, 12, 22, 11, 90);
n, i: Integer;
begin
n := Length(arr);
BubbleSort(arr, n);

Write('Posortowana lista: ');
for i := 1 to n do
Write(arr[i], ' ');
end.

Implementacja #Sortowania Bąbelkowego w #PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

<?php
function bubbleSort($arr) {
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}

// Przykład użycia:
$arr = array(64, 34, 25, 12, 22, 11, 90);
$sorted_arr = bubbleSort($arr);
echo "Posortowana lista: " . implode(", ", $sorted_arr);
?>

Podsumowując, sortowanie bąbelkowe to idealny #algorytm na początek przygody z programowaniem, ponieważ pomaga zrozumieć podstawy sortowania i optymalizacji. Jednak w praktyce, dla większych zbiorów danych, warto sięgnąć po bardziej zaawansowane techniki.