Co to jest sortowanie bąbelkowe?
Sortowanie bąbelkowe to algorytm sortowania używany do sortowania elementów listy w porządku rosnącym przez porównanie dwóch sąsiednich wartości. Jeśli pierwsza wartość jest wyższa niż druga wartość, pierwsza wartość zajmuje drugą pozycję wartości, podczas gdy druga wartość zajmuje pierwszą pozycję wartości. Jeśli pierwsza wartość jest niższa od drugiej, zamiana nie jest wykonywana.
Ten proces jest powtarzany, aż wszystkie wartości na liście zostaną porównane i zamienione, jeśli to konieczne. Każda iteracja jest zwykle nazywana przebiegiem. Liczba przebiegów w sortowaniu bąbelkowym jest równa liczbie elementów na liście minus jeden.
W tym samouczku Sortowanie bąbelków w Pythonie dowiesz się:
- Co to jest sortowanie bąbelkowe?
- Implementacja algorytmu sortowania bąbelkowego
- Zoptymalizowany algorytm sortowania bąbelkowego
- Reprezentacja wizualna
- Przykłady w Pythonie
- Objaśnienie kodu
- Zalety sortowania bąbelkowego
- Wady sortowania bąbelkowego
- Analiza złożoności sortowania bąbelkowego
Implementacja algorytmu sortowania bąbelkowego
Wdrożenie podzielimy na trzy (3) kroki, a mianowicie problem, rozwiązanie i algorytm, którego możemy użyć do napisania kodu dla dowolnego języka.
Problem
Lista pozycji jest podana w kolejności losowej, a my chcielibyśmy uporządkować pozycje w sposób uporządkowany
Rozważ następującą listę:
[21,6,9,33,3]
Rozwiązanie
Powtarzaj listę, porównując dwa sąsiednie elementy i zamieniając je, jeśli pierwsza wartość jest wyższa niż druga.
Wynik powinien wyglądać następująco:
[3,6,9,21,33]
Algorytm
Algorytm sortowania bąbelkowego działa w następujący sposób
Krok 1) Uzyskaj całkowitą liczbę elementów. Uzyskaj całkowitą liczbę elementów na podanej liście
Krok 2) Określ liczbę przejść zewnętrznych (n - 1) do wykonania. Jego długość to lista minus jeden
Krok 3) Wykonaj przejścia wewnętrzne (n - 1) razy dla przejścia zewnętrznego 1. Pobierz wartość pierwszego elementu i porównaj ją z wartością drugą. Jeśli druga wartość jest mniejsza niż pierwsza wartość, zamień pozycje
Krok 4) Powtórz krok 3 przejść, aż dojdziesz do przejścia zewnętrznego (n - 1). Pobierz następny element na liście, a następnie powtórz proces, który został wykonany w kroku 3, aż wszystkie wartości zostaną umieszczone we właściwej kolejności rosnącej.
Krok 5) Zwróć wynik po wykonaniu wszystkich przejść. Zwróć wyniki posortowanej listy
Krok 6) Zoptymalizuj algorytm
Unikaj niepotrzebnych wewnętrznych przebiegów, jeśli lista lub sąsiednie wartości są już posortowane. Na przykład, jeśli podana lista zawiera już elementy, które zostały posortowane w kolejności rosnącej, możemy wcześniej przerwać pętlę.
Zoptymalizowany algorytm sortowania bąbelkowego
Domyślnie algorytm sortowania bąbelkowego w Pythonie porównuje wszystkie elementy na liście, niezależnie od tego, czy lista jest już posortowana, czy nie. Jeśli podana lista jest już posortowana, porównywanie wszystkich wartości jest stratą czasu i zasobów.
Optymalizacja sortowania bąbelkowego pomaga nam uniknąć niepotrzebnych iteracji oraz zaoszczędzić czas i zasoby.
Na przykład, jeśli pierwszy i drugi element są już posortowane, nie ma potrzeby iteracji po pozostałych wartościach. Iteracja jest przerywana, a następna jest inicjowana do zakończenia procesu, jak pokazano w poniższym przykładzie sortowania bąbelkowego.
Optymalizację przeprowadza się, wykonując następujące kroki
Krok 1) Utwórz zmienną flagową, która monitoruje, czy w pętli wewnętrznej wystąpiła wymiana
Krok 2) Jeśli wartości zamieniły się pozycjami, przejdź do następnej iteracji
Krok 3) Jeśli korzyści nie zamieniły się pozycjami, zakończ pętlę wewnętrzną i kontynuuj pętlę zewnętrzną.
Zoptymalizowane sortowanie bąbelkowe jest bardziej wydajne, ponieważ wykonuje tylko niezbędne kroki i pomija te, które nie są wymagane.
Reprezentacja wizualna
Biorąc pod uwagę listę pięciu elementów, poniższe obrazy ilustrują, w jaki sposób sortowanie bąbelkowe iteruje po wartościach podczas ich sortowania
Poniższy obraz przedstawia nieposortowaną listę
Pierwsza iteracja
Krok 1)
Wartości 21 i 6 są porównywane, aby sprawdzić, która z nich jest większa od drugiej.
21 jest większe niż 6, więc 21 zajmuje pozycję zajmowaną przez 6, a 6 zajmuje pozycję zajmowaną przez 21
Nasza zmodyfikowana lista wygląda teraz jak powyższa.
Krok 2)
Porównuje się wartości 21 i 9.
21 jest większe niż 9, więc zamieniamy się pozycjami 21 i 9
Nowa lista jest teraz jak powyżej
Krok 3)
Wartości 21 i 33 są porównywane w celu znalezienia większej.
Wartość 33 jest większa niż 21, więc nie ma zamiany.
Krok 4)
Porównuje się wartości 33 i 3, aby znaleźć większą.
Wartość 33 jest większa niż 3, więc zamieniamy ich pozycjami.
Posortowana lista na końcu pierwszej iteracji jest podobna do powyższej
Druga iteracja
Nowa lista po drugiej iteracji jest następująca
Trzecia iteracja
Nowa lista po trzeciej iteracji jest następująca
Czwarta iteracja
Nowa lista po czwartej iteracji jest następująca
Przykłady w Pythonie
Poniższy kod pokazuje, jak zaimplementować algorytm sortowania bąbelkowego w języku Python.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
Wykonanie powyższego programu do sortowania bąbelkowego w Pythonie daje następujące wyniki
[6, 9, 21, 3, 33]
Objaśnienie kodu
Wyjaśnienie kodu programu Python Bubble Sort jest następujące
TUTAJ,
- Definiuje funkcję bubbleSort, która przyjmuje parametr theSeq. Kod nic nie wyświetla.
- Pobiera długość tablicy i przypisuje wartość do zmiennej n. Kod nic nie wyświetla
- Uruchamia pętlę for, która uruchamia algorytm sortowania bąbelkowego (n - 1) razy. To jest zewnętrzna pętla. Kod nic nie wyświetla
- Definiuje zmienną flagową, która będzie używana do określenia, czy nastąpiła zamiana, czy nie. Ma to na celu optymalizację. Kod nic nie wyświetla
- Rozpoczyna wewnętrzną pętlę, która porównuje wszystkie wartości na liście od pierwszej do ostatniej. Kod nic nie wyświetla.
- Używa instrukcji if, aby sprawdzić, czy wartość po lewej stronie jest większa niż wartość po prawej stronie. Kod nic nie wyświetla.
- Przypisuje wartość theSeq [j] do zmiennej czasowej tmp, jeśli warunek ma wartość true. Kod nic nie wyświetla
- WartośćSeq [j + 1] jest przypisana do pozycjiSeq [j]. Kod nic nie wyświetla
- Wartość zmiennej tmp jest przypisywana do pozycji theSeq [j + 1]. Kod nic nie wyświetla
- Zmiennej flag jest przypisywana wartość 1, aby wskazać, że nastąpiła zamiana. Kod nic nie wyświetla
- Używa instrukcji if, aby sprawdzić, czy wartość flagi zmiennej wynosi 0. Kod nic nie wyświetla
- Jeśli wartość wynosi 0, wywołujemy instrukcję break, która wychodzi z pętli wewnętrznej.
- Zwraca wartość theSeq po jego posortowaniu. Kod wyświetla posortowaną listę.
- Definiuje zmienną el, która zawiera listę liczb losowych. Kod nic nie wyświetla.
- Przypisuje wartość funkcji bubbleSort do wyniku zmiennej.
- Wyświetla wartość wyniku zmiennej.
Zalety sortowania bąbelkowego
Poniżej przedstawiono niektóre zalety algorytmu sortowania bąbelkowego
- Łatwo to zrozumieć
- Działa bardzo dobrze, gdy lista jest już lub prawie posortowana
- Nie wymaga dużej pamięci.
- Łatwo jest napisać kod algorytmu
- Wymagania dotyczące miejsca są minimalne w porównaniu z innymi algorytmami sortowania.
Wady sortowania bąbelkowego
Poniżej przedstawiono niektóre wady algorytmu sortowania bąbelkowego
- Nie działa dobrze podczas sortowania dużych list. Zajmuje zbyt dużo czasu i zasobów.
- Jest używany głównie do celów akademickich, a nie do aplikacji w świecie rzeczywistym.
- Liczba kroków wymaganych do sortowania listy jest rzędu n 2
Analiza złożoności sortowania bąbelkowego
Istnieją trzy rodzaje złożoności:
1) Sortuj złożoność
Złożoność sortowania służy do wyrażenia ilości czasu wykonania i miejsca potrzebnego do posortowania listy. Sortowanie bąbelkowe wykonuje (n - 1) iteracji, aby posortować listę, gdzie n jest całkowitą liczbą elementów na liście.
2) Złożoność czasowa
Złożoność czasowa sortowania bąbelkowego wynosi O (n 2 )
Złożoność czasową można podzielić na:
- Najgorszy przypadek - w tym przypadku podana lista jest w porządku malejącym. Algorytm wykonuje maksymalną liczbę wykonań wyrażoną jako [Big-O] O (n 2 )
- Najlepszy przypadek - ma to miejsce, gdy podana lista jest już posortowana. Algorytm wykonuje minimalną liczbę wykonań wyrażoną jako [Big-Omega] Ω (n)
- Średni przypadek - ma to miejsce, gdy lista jest w kolejności losowej. Średnia złożoność jest reprezentowana jako [Big-theta] ⊝ (n 2 )
3) Złożoność przestrzeni
Złożoność przestrzeni mierzy ilość dodatkowego miejsca potrzebnego do sortowania listy. Sortowanie bąbelkowe wymaga tylko jednego (1) dodatkowego miejsca na zmienną czasową używaną do zamiany wartości. Dlatego ma złożoność przestrzenną O (1).
Podsumowanie
- Algorytm sortowania bąbelkowego polega na porównaniu dwóch sąsiednich wartości i zamianie ich, jeśli wartość po lewej stronie jest mniejsza niż wartość po prawej stronie.
- Implementacja algorytmu sortowania bąbelkowego jest stosunkowo prosta w Pythonie. Wszystko, czego potrzebujesz, to pętle i instrukcje if.
- Problem, który rozwiązuje algorytm sortowania bąbelkowego, polega na pobieraniu losowej listy elementów i przekształcaniu jej w uporządkowaną listę.
- Algorytm sortowania bąbelkowego w strukturze danych działa najlepiej, gdy lista jest już posortowana, ponieważ wykonuje minimalną liczbę iteracji.
- Algorytm sortowania bąbelkowego nie działa dobrze, gdy lista jest w odwrotnej kolejności.
- Sortowanie bełkotowe ma złożoność czasową O (n 2 ) i złożoność przestrzenną O (1)
- Algorytm sortowania bełkotowego najlepiej nadaje się do celów akademickich, a nie do zastosowań w świecie rzeczywistym.
- Zoptymalizowane sortowanie bąbelkowe sprawia, że algorytm jest bardziej wydajny, pomijając niepotrzebne iteracje podczas sprawdzania wartości, które zostały już posortowane.