Sortowanie bąbelkowe (bubble sort)
Wprowadzenie
Sortowanie bąbelkowe (ang. Bubble sort) często bywa uważane za najprostszy sposób sortowania. Jest ono pierwszym algorytmem sortowania jaki jest przedstawiany początkującym programistom czy informatykom.
Jak się za pewne już domyślasz, ja wcale tak nie uważam. Nie dość, że sortowanie bąbelkowe jest trudniejsze do zrozumienia od sortowania przez wybór i sortowania przez wstawianie, jest też moim zdaniem trochę trudniejsze do efektywnego zaimplementowania.
Mimo wszystko warto poznać ten algorytm, zwłaszcza dlatego, że tak często można go napotkać w literaturze.
Sprecyzujmy warunki sortowania:
Dane: n elementów oznaczonych x[1], x[2], x[3], ..., x[n] oraz operator porównania
tych elementów, za pomocą którego możemy stwierdzić który z dwóch porównywanych elementów jest mniejszy, a który większy.
Wynik: n elementów uporządkowanych w taki sposób, że pierwszy element jest najmniejszy w sensie
operatora porównania elementów, a ostatni jest elementem największym w sensie tego samego operatora.
Algorytm w postaci listy kroków
- Zmiennej koniec przypisz n
- Zmiennej i przypisz 1, zmiennej k przypisz 0
-
Dopóki i<koniec wykonuj:
- Jeśli x[i]>x[i+1], to zamień te elementy miejscami oraz zmiennej k przypisz wartość zmiennej i
- Zwiększ zmienną i o 1
- Jeśli k>1, to zmiennej koniec przypisz k i wróć do kroku 2, natomiast jeśli k<=1, to zakończ algorytm
