Spisu treści:
Definicja - Co oznacza sortowanie bąbelkowe?
Sortowanie bąbelkowe to algorytm sortowania, który działa poprzez wielokrotne przechodzenie przez listy, które należy posortować, porównywanie każdej pary sąsiednich elementów i zamianę ich, jeśli są w niewłaściwej kolejności. Ta procedura przekazywania jest powtarzana, dopóki nie są wymagane żadne zamiany, co wskazuje, że lista jest posortowana. Sortowanie bąbelkowe ma swoją nazwę, ponieważ mniejsze elementy bąbelkują na początku listy.
Sortowanie bąbelkowe jest również określane jako sortowanie tonące lub sortowanie porównawcze.
Techopedia wyjaśnia Bubble Sort
Sortowanie bąbelkowe ma najgorszy przypadek i średnią złożoność O (n2), gdzie n jest liczbą posortowanych elementów. W przeciwieństwie do innych algorytmów sortowania, sortowanie bąbelkowe wykrywa, czy posortowana lista jest skutecznie wbudowana w algorytm. Wydajność sortowania bąbelkowego na już posortowanej liście wynosi O (n).
Pozycja elementów w sortowaniu bąbelkowym odgrywa ważną rolę w określaniu wydajności. Duże elementy na początku nie stanowią problemu, ponieważ można je łatwo zamieniać. Małe elementy pod koniec przesuwają się powoli na początek. Jako takie, te elementy nazywane są królikami i żółwiami.
Algorytm sortowania bąbelkowego można zoptymalizować, umieszczając większe elementy w końcowej pozycji. Po każdym przejściu wszystkie elementy po ostatniej zamianie są sortowane i nie trzeba ich sprawdzać ponownie, tym samym pomijając śledzenie zamienionych zmiennych.
