Sortowanie bąbelkowe - Bubble sort

Sortowanie bąbelkowe

Wizualizacja statyczna sortowania bąbelkowego
Klasa	Algorytm sortowania
Struktura danych	Szyk
Wydajność w najgorszym przypadku	${\ Displaystyle O (n ^ {2})}$porównania, swapy${\ Displaystyle O (n ^ {2})}$
Wydajność w najlepszym przypadku	${\ Displaystyle O (n)}$porównania, swapy${\ Displaystyle O (1)}$
Średnia wydajność	${\ Displaystyle O (n ^ {2})}$porównania, swapy${\ Displaystyle O (n ^ {2})}$
Najgorsza złożoność przestrzeni	${\ Displaystyle O (n)}$całkowity, pomocniczy${\ Displaystyle O (1)}$

Sortowanie bąbelkowe , czasami określane jako sortowanie tonące , to prosty algorytm sortowania, który wielokrotnie przechodzi przez listę, porównuje sąsiednie elementy i zamienia je, jeśli są w złej kolejności. Przechodzenie przez listę jest powtarzane, dopóki lista nie zostanie posortowana. Algorytm, który jest sortowaniem porównawczym , nosi nazwę sposobu, w jaki mniejsze lub większe elementy „przeskakują” na górę listy.

Ten prosty algorytm słabo sprawdza się w rzeczywistych zastosowaniach i jest używany przede wszystkim jako narzędzie edukacyjne. Bardziej wydajne algorytmy, takie jak quicksort , timsort lub sortowanie przez scalanie są używane przez biblioteki sortujące wbudowane w popularne języki programowania, takie jak Python i Java.

Analiza

Przykład sortowania bąbelkowego. Zaczynając od początku listy porównaj każdą sąsiednią parę, zamień ich pozycje, jeśli nie są w odpowiedniej kolejności (ta druga jest mniejsza od poprzedniej). Po każdej iteracji potrzebny jest jeden element mniej (ostatni) do porównania, dopóki nie zostanie już więcej elementów do porównania.

Wydajność

Sortowanie bąbelkowe ma najgorszy przypadek i średnią złożoność О ( n ² ), gdzie n to liczba sortowanych elementów. Większość praktycznych algorytmów sortowania ma znacznie lepszą złożoność najgorszego przypadku lub średnią, często O ( n  log  n ). Nawet inne algorytmy sortowania О ( n ² ), 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 quicksort , ale nie sortowaniem przez wstawianie , jest to, że w algorytmie wbudowana jest możliwość wykrycia, że ​​lista jest posortowana efektywnie. Gdy lista jest już posortowana (w najlepszym przypadku), złożoność sortowania bąbelkowego wynosi tylko O ( n ). W przeciwieństwie do tego większość innych algorytmów, nawet tych o lepszej złożoności średniej wielkości , wykonuje cały proces sortowania na zbiorze, a zatem jest bardziej złożona. Jednak sortowanie przez wstawianie nie tylko ma tę zaletę, ale także działa lepiej na liście, która jest w znacznym stopniu posortowana (mająca niewielką 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.

Króliki i żółwie

Odległość i kierunek, o jaki 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 przemieścić się na koniec 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ą wymianę, więc przesuwa się do swojej posortowanej pozycji przy 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ż o jeden krok na przejście, więc elementy poruszają się w kierunku początku bardzo powoli. Jeśli najmniejszy element znajduje się na końcu listy, przeniesienie go na początek zajmie n- 1 przebiegów. Doprowadziło to do tego, że tego typu elementy zostały nazwane odpowiednio królikami i żółwiami, na cześć postaci z bajki Ezopa o Żółwie i zająca .

Podjęto różne wysiłki w celu wyeliminowania żółwi, aby poprawić szybkość sortowania pęcherzyków. Sortowanie koktajlowe to dwukierunkowe sortowanie bąbelkowe, które przebiega od początku do końca, a następnie odwraca się, przechodząc od końca do początku. Potrafi dość dobrze przenosić żółwie, ale zachowuje złożoność O(n ² ) w najgorszym przypadku. Sortowanie grzebieniowe porównuje elementy oddzielone dużymi odstępami i może bardzo szybko przenosić żółwie przed przejściem do coraz mniejszych odstępów w celu wygładzenia listy. Jego średnia prędkość jest porównywalna z szybszymi algorytmami, takimi jak quicksort .

Przykład krok po kroku

Weź tablicę liczb „5 1 4 2 8” i posortuj tablicę od najmniejszej do największej liczby za pomocą sortowania bąbelkowego. Na każdym kroku porównywane są elementy napisane pogrubioną czcionką . Potrzebne będą trzy przepustki;

Pierwszy przejazd

( 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 porządku (8 > 5), algorytm ich nie zamienia.

Drugi przejazd

( 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 zakończona. Algorytm potrzebuje jednego dodatkowego całego przebiegu bez żadnej wymiany, aby wiedzieć, że jest posortowany.

Trzeci przejazd

( 1 2 4 5 8) → ( 1 2 4 5 8)

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8 ) → (1 2 4 5 8 )

Realizacja

Implementacja pseudokodu

W pseudokodzie algorytm może być wyrażony jako tablica oparta na 0:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped
end procedure

Optymalizacja sortowania bąbelków

Algorytm sortowania bąbelkowego można zoptymalizować, obserwując, że n- ty przebieg znajduje n- ty największy element i umieszcza go na swoim ostatnim miejscu. Tak więc wewnętrzna pętla może uniknąć patrzenia na ostatnie n − 1 elementów podczas uruchamiania po raz n- ty:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                swapped := true
            end if
        end for
        n := n - 1
    until not swapped
end procedure

Mówiąc ogólnie, może się zdarzyć, że w jednym przejściu więcej niż jeden element zostanie umieszczony w swojej końcowej pozycji. W szczególności po każdym przejściu sortowane są wszystkie elementy po ostatniej wymianie i nie trzeba ich ponownie sprawdzać. Pozwala to pominąć wiele elementów, co w najgorszym przypadku daje 50% poprawę w liczbie porównań (choć nie ma poprawy w liczbie wymiany) i dodaje bardzo niewiele złożoności, ponieważ nowy kod obejmuje zmienną „zamienioną”:

Aby to osiągnąć w pseudokodzie, można napisać:

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        newn := 0
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                newn := i
            end if
        end for
        n := newn
    until n ≤ 1
end procedure

Alternatywne modyfikacje, takie jak sortowanie w shakerze do koktajli, próbują poprawić wydajność sortowania bąbelkowego, zachowując ten sam pomysł wielokrotnego porównywania i zamiany sąsiednich elementów.

Posługiwać się

Sortowanie bąbelkowe. Lista została wykreślona w kartezjańskim układzie współrzędnych, przy czym każdy punkt ( x , y ) wskazuje, że wartość y jest przechowywana w indeksie x . Następnie lista zostanie posortowana według sortowania bąbelkowego według wartości każdego piksela. Zwróć uwagę, że największy koniec jest sortowany jako pierwszy, a mniejsze elementy potrzebują więcej czasu, aby przenieść się na właściwe pozycje.

Chociaż sortowanie bąbelkowe jest jednym z najprostszych algorytmów sortowania do zrozumienia i implementacji, jego złożoność O ( n ² ) oznacza, że ​​jego wydajność dramatycznie spada na listach zawierających więcej niż małą liczbę elementów. Nawet wśród prostych algorytmów sortowania O ( n ² ) algorytmy takie jak sortowanie przez wstawianie są zwykle znacznie bardziej wydajne.

Ze względu na swoją prostotę sortowanie bąbelkowe jest często używane do wprowadzenia pojęcia algorytmu lub algorytmu sortowania dla początkujących studentów informatyki . Jednak niektórzy badacze, tacy jak Owen Astrachan, dołożyli wszelkich starań, aby zdyskredytować sortowanie bąbelkowe i jego nieustanną popularność w edukacji informatycznej, zalecając, aby nawet nie nauczać tego.

Pliku żargonu , który znakomicie rozmowy bogosort „archetypowych [sic] przewrotnie okropny algorytm”, wzywa również bubble sort „ogólny zły algorytm”. Donald Knuth w The Art of Computer Programming stwierdził, że „rodzaj bąbelkowy wydaje się nie mieć nic, co by go polecało, poza chwytliwą nazwą i faktem, że prowadzi do pewnych interesujących problemów teoretycznych”, z których niektóre następnie omawia.

Sortowanie bąbelkowe jest asymptotycznie równoważne w czasie działania z sortowaniem przez wstawianie w najgorszym przypadku, ale oba algorytmy znacznie różnią się liczbą koniecznych zamian. Wyniki eksperymentalne, takie jak wyniki Astrachan, również wykazały, że sortowanie przez wstawianie działa znacznie lepiej nawet na losowych listach. Z tych powodów wiele współczesnych podręczników algorytmicznych unika używania algorytmu sortowania bąbelkowego na rzecz sortowania przez wstawianie.

Sortowanie bąbelkowe również słabo współdziała z nowoczesnym sprzętem procesora. Tworzy co najmniej dwa razy więcej zapisów niż sortowanie przez wstawianie, dwa razy więcej chybień w pamięci podręcznej i asymptotycznie więcej błędnych prognoz gałęzi . Eksperymenty z sortowaniem ciągów Astrachan w Javie pokazują, że sortowanie bąbelkowe jest w przybliżeniu jedną piątą szybkością sortowania przez wstawianie i 70% szybkością sortowania przez wybór .

W grafice komputerowej sortowanie bąbelkowe jest popularne ze względu na jego zdolność do wykrywania bardzo małych błędów (takich jak zamiana tylko dwóch elementów) w prawie posortowanych tablicach i naprawiania ich z liniową złożonością (2 n ). Na przykład jest używany w algorytmie wypełniania wielokątów, w którym linie ograniczające są sortowane według ich współrzędnej x na określonej linii skanowania (linia równoległa do osi x ) i przy zwiększaniu y ich kolejność zmienia się (dwa elementy są zamieniane) tylko o przecięcia dwóch linii. Sortowanie bąbelkowe to stabilny algorytm sortowania, taki jak sortowanie przez wstawianie.

Wariacje

• Sortowanie nieparzyste-parzyste to równoległa wersja sortowania bąbelkowego dla systemów przekazywania wiadomości.
• Podania mogą być od prawej do lewej, a nie od lewej do prawej. Jest to bardziej efektywne w przypadku list z nieposortowanymi elementami dodanymi na końcu.
• Sortowanie shakera do koktajli zmienia się naprzemiennie w lewo i w prawo.

Debata nad nazwą

Sortowanie bąbelkowe jest czasami określane jako „sortowanie tonące”.

Na przykład w The Art of Computer Programming , Tom 3: Sorting and Searching Donalda Knutha w rozdziale 5.2.1 „Sortowanie przez wstawianie” stwierdza, że ​​[wartość] „ustabilizuje się na właściwym poziomie” i że ta metoda sortowania czasami nazywana techniką przesiewania lub zatapiania .

Ta debata jest utrwalana przez łatwość, z jaką można rozpatrywać ten algorytm z dwóch różnych, ale równie ważnych perspektyw:

1. Te większe wartości mogą być traktowane jako cięższy i dlatego widać stopniowe zlewu do dołu listy
2. Te mniejsze wartości mogą być traktowane jako lżejszy i dlatego widać stopniowe bańki się na górze listy.

W kulturze popularnej

W 2007 roku były dyrektor generalny Google, Eric Schmidt, zapytał podczas rozmowy kwalifikacyjnej kandydata na prezydenta Baracka Obamę, jak najlepiej posortować milion liczb całkowitych ; Obama przerwał na chwilę i odpowiedział: „Myślę, że sortowanie bańki byłoby złą drogą”.

Uwagi

Bibliografia

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN  0-262-03293-7 . Problem 2-2, s.40.
• Sortowanie w obecności przewidywania gałęzi i pamięci podręcznych
• Podstawy struktur danych Ellis Horowitz, Sartaj Sahni i Susan Anderson-Freed ISBN  81-7371-605-6
• Owena Astrachan . Sortowanie bąbelków: archeologiczna analiza algorytmiczna

Zewnętrzne linki

• Marcina, Davida R. (2007). „Animowane algorytmy sortowania: sortowanie bąbelkowe” . Zarchiwizowane od oryginału 03.03.2015. – demonstracja graficzna
• „Sortowanie bąbelków Lafore'a” . (Animacja apletu Java)
• Sekwencja OEIS A008302 (Tabela (statystyki) liczby permutacji [n], które wymagają k zamiany par podczas sortowania)