Sortowanie bąbelkowe

Co to jest sortowanie bąbelkowe?

Sortowanie bąbelkowe to prosty algorytm sortowania tablicy, który polega na wielokrotnym porównywaniu sąsiednich elementów i zamienianiu ich miejscami, jeśli są w złej kolejności.

Nazwa pochodzi od tego, że największe elementy stopniowo „wypływają” na koniec tablicy jak bąbelki.

Zasada działania

Dla sortowania rosnącego algorytm:
- porównuje pierwszy element z drugim,
- jeśli pierwszy jest większy od drugiego, zamienia je miejscami,
- przechodzi do kolejnej pary sąsiednich elementów,
- po jednym pełnym przejściu największy element znajduje się na końcu tablicy,
- powtarza proces dla pozostałej części tablicy.

Przykład

Tablica:

[5, 2, 4, 1]

Po porównaniach i zamianach największe wartości przesuwają się w prawo:

[2, 4, 1, 5]
[2, 1, 4, 5]
[1, 2, 4, 5]

Przykład w JavaScript

let tab = [5, 2, 4, 1];

for (let i = 0; i < tab.length - 1; i++) {
  for (let j = 0; j < tab.length - 1 - i; j++) {
    if (tab[j] > tab[j + 1]) {
      let temp = tab[j];
      tab[j] = tab[j + 1];
      tab[j + 1] = temp;
    }
  }
}

console.log(tab); // [1, 2, 4, 5]

Cechy algorytmu

• jest łatwy do zrozumienia i implementacji,
• działa wolno dla dużych zbiorów danych,
• ma złożoność czasową zwykle O(n²),
• sortuje dane przez zamianę sąsiednich elementów.

Na egzaminie warto zapamiętać: porównywanie sąsiednich elementów + zamiana miejscami = sortowanie bąbelkowe.