Bubble Algorytm sortowania za pomocą Python za pomocą przykładowej listy

Czym są sterowniki Bubble Sortować?

Bubble Sortuj to algorytm sortowania używany do sortowania elementów listy w kolejności rosnącej poprzez porównanie dwóch sąsiadujących wartości. Jeżeli pierwsza wartość jest większa od drugiej, pierwsza wartość zajmuje pozycję drugiej wartości, natomiast druga wartość zajmuje pierwszą pozycję wartości. Jeśli pierwsza wartość jest mniejsza niż druga, zamiana nie jest wykonywana.

Proces ten jest powtarzany, aż wszystkie wartości na liście zostaną porównane i w razie potrzeby zamienione. Każda iteracja jest zwykle nazywana passem. Liczba przebiegów w sortowaniu bąbelkowym jest równa liczbie elementów na liście minus jeden.

W tym Bubble Sortowanie Python Tutorial nauczysz się:

Wdrażanie Bubble Algorytm sortowania

Implementację 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ż poniższą listę:

[21,6,9,33,3]

rozwiązanie

Wykonaj iterację po liście, porównując dwa sąsiednie elementy i zamieniając je, jeśli pierwsza wartość jest wyższa niż druga.

Wynik powinien być następujący:

[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), które należy wykonać. Jego długość to lista minus jeden

Krok 3) Wykonaj wewnętrzne przejścia (n – 1) razy dla zewnętrznego przejścia 1. Uzyskaj wartość pierwszego elementu i porównaj ją z drugą wartością. Jeśli druga wartość jest mniejsza niż pierwsza, zamień pozycje

Krok 4) Powtarzaj kroki 3, aż dojdziesz do zewnętrznego przejścia (n – 1). Pobierz następny element na liście, a następnie powtórz proces 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 przebiegów. Zwróć wyniki posortowanej listy

Krok 6) Optymalizuj algorytm

Unikaj niepotrzebnych przebiegów wewnętrznych, jeśli lista lub sąsiednie wartości są już posortowane. Przykładowo, jeżeli podana lista zawiera już elementy posortowane rosnąco, to możemy wcześniej przerwać pętlę.

Zoptymalizowana Bubble Algorytm sortowania

Domyślnie algorytm sortowania bąbelkowego w Python porównuje wszystkie elementy na liście niezależnie od tego, czy lista jest już posortowana, czy nie. Jeśli dana 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 zostaje zakończona i rozpoczyna się następna, aż do zakończenia procesu, jak pokazano poniżej Bubble Przykład sortowania.

Optymalizacja odbywa się poprzez wykonanie następujących kroków

Krok 1) Utwórz zmienną flagową, która monitoruje, czy w pętli wewnętrznej nastąpiła jakakolwiek zamiana

Krok 2) Jeżeli wartości zamieniły się miejscami, przejdź do następnej iteracji

Krok 3) Jeżeli świadczenia nie zamieniły się pozycjami, zakończ pętlę wewnętrzną i kontynuuj pracę z 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

Na poniższej ilustracji przedstawiono, w jaki sposób sortowanie bąbelkowe przechodzi przez wartości podczas sortowania listy pięciu elementów.

Na poniższym obrazku pokazano nieposortowaną listę

Reprezentacja wizualna

Pierwsza iteracja

Krok 1)

Reprezentacja wizualna

Wartości 21 i 6 są porównywane, aby sprawdzić, która z nich jest większa od drugiej.

Reprezentacja wizualna

21 jest większe niż 6, więc 21 zajmuje pozycję zajmowaną przez 6, a 6 zajmuje pozycję zajmowaną przez 21

Reprezentacja wizualna

Nasza zmodyfikowana lista wygląda teraz jak powyższa.

Krok 2)

Reprezentacja wizualna

Porównuje się wartości 21 i 9.

Reprezentacja wizualna

21 jest większe niż 9, więc zamieniamy pozycje 21 i 9

Reprezentacja wizualna

Nowa lista wygląda teraz jak powyżej

Krok 3)

Reprezentacja wizualna

Wartości 21 i 33 są porównywane w celu znalezienia większej.

Reprezentacja wizualna

Wartość 33 jest większa niż 21, więc nie ma miejsca żadna zamiana.

Krok 4)

Reprezentacja wizualna

Wartości 33 i 3 są porównywane w celu znalezienia większej.

Reprezentacja wizualna

Wartość 33 jest większa od 3, więc zamieniamy ich miejscami.

Reprezentacja wizualna

Posortowana lista na końcu pierwszej iteracji jest taka sama jak ta powyżej

Druga iteracja

Nowa lista po drugiej iteracji wygląda następująco

Reprezentacja wizualna

Trzecia iteracja

Nowa lista po trzeciej iteracji wygląda następująco

Reprezentacja wizualna

Czwarta iteracja

Nowa lista po czwartej iteracji wygląda następująco

Reprezentacja wizualna

Python Przykłady

Poniższy kod pokazuje, jak zaimplementować Bubble Algorytm sortowania w Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

Wykonanie powyższego programu sortowania bąbelkowego w Python generuje następujące wyniki

[6, 9, 21, 3, 33]

Objaśnienie kodu

Wyjaśnienie dot Python Bubble Kod programu sortowania jest następujący

Objaśnienie kodu

TUTAJ,

  1. Definiuje funkcję bubbleSort, która akceptuje parametr theSeq. Kod nic nie wyświetla.
  2. Pobiera długość tablicy i przypisuje wartość do zmiennej n. Kod nic nie wyświetla
  3. Uruchamia pętlę for, która uruchamia algorytm sortowania bąbelkowego (n – 1) razy. To jest pętla zewnętrzna. Kod nic nie wyświetla
  4. 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
  5. Rozpoczyna wewnętrzną pętlę, która porównuje wszystkie wartości na liście od pierwszej do ostatniej. Kod nie generuje niczego.
  6. Używa instrukcji if do sprawdzenia, czy wartość po lewej stronie jest większa niż wartość po prawej stronie. Kod nic nie wyświetla.
  7. Przypisuje wartość Seq[j] do zmiennej tymczasowej tmp, jeśli warunek ma wartość true. Kod nic nie wyświetla
  8. Wartość Seq[j + 1] jest przypisana do pozycji Seq[j]. Kod nic nie wyświetla
  9. Wartość zmiennej tmp przypisana jest do pozycji theSeq[j + 1]. Kod nic nie wyświetla
  10. Zmiennej flagi przypisuje się wartość 1, aby wskazać, że miała miejsce zamiana. Kod nic nie wyświetla
  11. Używa instrukcji if do sprawdzenia, czy wartość flagi zmiennej wynosi 0. Kod nie generuje żadnych wyników
  12. Jeśli wartość wynosi 0, wywołujemy instrukcję break, która wychodzi z wewnętrznej pętli.
  13. Zwraca wartość Seq po jej posortowaniu. Kod generuje posortowaną listę.
  14. Definiuje zmienną el, która zawiera listę liczb losowych. Kod nie wyprowadza niczego.
  15. Przypisuje wartość funkcji bubbleSort do wyniku zmiennej.
  16. Drukuje wartość wyniku zmiennej.

Bubblzalety sortowania

Oto 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.
  • Napisanie kodu algorytmu jest łatwe
  • Wymagania dotyczące miejsca są minimalne w porównaniu do innych algorytmów sortowania.

Bubble sort Wady

Poniżej przedstawiono niektóre wady algorytmu sortowania bąbelkowego

  • Nie radzi sobie dobrze z sortowaniem dużych list. Zajmuje to zbyt dużo czasu i zasobów.
  • Jest używany głównie do celów akademickich, a nie do zastosowań w świecie rzeczywistym.
  • Liczba kroków wymaganych do posortowania listy jest rzędu n2

Analiza złożoności Bubble Sortuj

Istnieją trzy rodzaje złożoności:

1) Sortuj złożoność

Złożoność sortowania jest używana do wyrażania ilości czasu wykonania i przestrzeni potrzebnej 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(n2)

Złożoności czasowe można podzielić na:

  • Najgorszy przypadek – w tym miejscu podana lista jest uporządkowana malejąco. Algorytm wykonuje maksymalną liczbę wykonań wyrażoną jako [Big-O] O(n2)
  • Najlepszy przypadek – dzieje się tak, gdy podana lista jest już posortowana. Algorytm wykonuje minimalną liczbę wykonań, która jest wyrażona jako [Big-Omega] Ω(n)
  • Przeciętny przypadek – dzieje się tak, gdy lista jest w losowej kolejności. Średnia złożoność jest reprezentowana jako [Big-theta] ⊝(n2)

3) Złożoność kosmiczna

Złożoność przestrzenna mierzy ilość dodatkowej przestrzeni potrzebnej do sortowania listy. Sortowanie bąbelkowe wymaga tylko jednej (1) dodatkowej przestrzeni dla zmiennej czasowej używanej do zamiany wartości. Dlatego ma złożoność przestrzenną O (1).

Podsumowanie

  • Algorytm sortowania bąbelkowego działa poprzez porównanie dwóch sąsiednich wartości i zamianę ich, jeśli wartość po lewej stronie jest mniejsza niż wartość po prawej stronie.
  • Implementacja algorytmu sortowania bąbelkowego jest stosunkowo prosta dzięki Python. Jedyne, czego potrzebujesz, to pętle for i instrukcje if.
  • Problem rozwiązywany przez algorytm sortowania bąbelkowego polega na przekształceniu losowej listy elementów w listę uporządkowaną.
  • 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 metodą bubblera ma złożoność czasową O (n2) i złożoność przestrzenną O (1)
  • Algorytm sortowania bąbelkowego najlepiej nadaje się do celów akademickich, a nie do zastosowań w świecie rzeczywistym.
  • Zoptymalizowane sortowanie bąbelkowe zwiększa efektywność algorytmu, pomijając niepotrzebne iteracje podczas sprawdzania wartości, które zostały już posortowane.