Sortowanie bąbelkowe

PerformanceEdit

Sortowanie bąbelkowe ma najgorszy przypadek i średnią złożoność О (n2), gdzie n to liczba sortowanych elementów. Większość praktycznych algorytmów sortowania ma znacznie lepszą najgorszy lub średnią złożoność, często O (n log n). Nawet inne algorytmy sortowania О (n2), takie jak sortowanie przez wstawianie, generalnie działają szybciej niż sortowanie bąbelkowe i nie są bardziej złożone. Dlatego sortowanie bąbelkowe nie jest praktycznym algorytmem sortowania.

Jedyną istotną zaletą sortowania bąbelkowego w porównaniu z większością innych algorytmów, nawet sortowania szybkiego, ale nie przez wstawianie, jest możliwość wykrycia, że lista jest posortowana. efektywnie jest wbudowany w algorytm. Gdy lista jest już posortowana (najlepszy przypadek), złożoność sortowania bąbelkowego wynosi tylko O (n). Z kolei większość innych algorytmów, nawet tych o lepszej średniej złożoności przypadków, wykonuje cały proces sortowania na zestawie, a zatem jest bardziej złożona. Jednak sortowanie przez wstawianie nie tylko ma tę zaletę, ale również działa lepiej na liście, która jest zasadniczo posortowana (z małą liczbą inwersji). Dodatkowo, jeśli takie zachowanie jest pożądane, można je w prosty sposób dodać do dowolnego innego algorytmu, sprawdzając listę przed uruchomieniem algorytmu.

Sortowania bąbelkowego należy unikać w przypadku dużych zbiorów. Nie będzie to efektywne w przypadku kolekcji w odwrotnej kolejności.

Rabbits and TurtlesEdit

Odległość i kierunek, w jakim elementy muszą się poruszać podczas sortowania, określają wydajność sortowania bąbelkowego, ponieważ elementy poruszają się w różnych kierunkach z różnymi prędkościami. Element, który musi przesunąć się w kierunku końca listy, może poruszać się szybko, ponieważ może brać udział w kolejnych zamianach. Na przykład największy element na liście wygra każdą zamianę, więc przesuwa się do posortowana pozycja w pierwszym przebiegu, nawet jeśli zaczyna się blisko początku. Z drugiej strony element, który musi poruszać się w kierunku początku listy, nie może poruszać się szybciej niż jeden krok na przebieg, więc elementy przesuwają się na początek bardzo powoli. Jeśli najmniejszy element znajduje się na końcu listy, przeniesienie go na początek zajmie n − 1. Doprowadziło to do tego, że te typy elementów zostały nazwane odpowiednio królikami i żółwiami, po postaciach z bajki Ezopa o Żółw i zając.

Różne podjęto wysiłki, aby wyeliminować żółwie, aby poprawić szybkość sortowania bąbelkowego. Sortowanie koktajlowe to dwukierunkowe sortowanie bąbelkowe, które przebiega od początku do końca, a następnie odwraca się, od końca do początku. Może dość dobrze poruszać żółwie, ale zachowuje złożoność O (n2) w najgorszym przypadku. Sortowanie grzebieniowe porównuje elementy oddzielone dużymi przerwami i może bardzo szybko przemieszczać żółwie, zanim przejdzie do mniejszych i mniejszych luk, aby wygładzić listę. Jego średnia prędkość jest porównywalna z szybszymi algorytmami, takimi jak szybkie sortowanie.

Przykład krok po krokuEdytuj

Weź tablicę liczb „5 1 4 2 8” i posortuj ją od najniższej liczba do największej liczby przy użyciu sortowania bąbelkowego. Na każdym kroku porównuje się elementy zapisane pogrubioną czcionką. Wymagane będą trzy przebiegi;

Pierwszy przebieg (5 1 4 2 8) → (1 5 4 2 8), tutaj algorytm porównuje pierwsze dwa elementy i zamienia od 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Zamień od 5 > 4 (1 4 5 2 8) → (1 4 2 5 8), Zamień od 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Teraz, ponieważ te elementy są już w kolejności (8 > 5), algorytm ich nie zamienia. Drugi przebieg (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Zamień od 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

Teraz tablica jest już posortowana, ale algorytm nie wie, czy jest kompletny . Algorytm potrzebuje jednego całego przebiegu bez żadnej zamiany, aby wiedzieć, że jest posortowany.