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ąsiednich wartości. Jeśli pierwsza wartość jest wyższa od drugiej, pierwsza wartość zajmuje pozycję drugiej, a druga wartość zajmuje pozycję pierwszej. Jeśli pierwsza wartość jest niższa od drugiej, zamiana nie jest wykonywana.ping skończone.

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 poznasz problem, który rozwiązuje, jego zoptymalizowaną formę, wizualny przewodnik krok po kroku, działający Python programu i jego charakterystyki wydajności.

Wdrażanie Bubble Algorytm sortowania

Podzielimy implementację na trzy (3) kroki, a mianowicie problem, rozwiązanie i algorytm, którego możemy użyć do napisania kodu w dowolnym języku.

Problem

Lista elementów jest podana w kolejności losowej, chcemy ułożyć elementy w sposób uporządkowany.

Rozważ poniższą listę:

[21, 6, 9, 33, 3]

rozwiązanie

Przejrzyj listę, porównując dwa sąsiadujące elementy i zamieniając je miejscamiping je, jeśli pierwsza wartość jest wyższa od drugiej.

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) Pobierz całkowitą liczbę elementów. Pobierz całkowitą liczbę elementów na podanej liście.

Krok 2) Określ liczbę przejść zewnętrznych (n – 1) do wykonania. Ich długość wynosi 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 drugą wartością. Jeśli druga wartość jest mniejsza od pierwszej, zamień pozycje.

Krok 4) Powtarzaj kroki 3, aż dojdziesz do ostatniego kroku (n – 1). Pobierz kolejny element z listy, a następnie powtórz proces z kroku 3, aż wszystkie wartości zostaną umieszczone w prawidłowej kolejności rosnącej.

Krok 5) Zwróć wynik po wykonaniu wszystkich przejść. Zwróć wyniki posortowanej listy.

Krok 6) Optymalizacja algorytmu.

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 występuje jakakolwiek zamianaping wystąpiło w pętli wewnętrznej.

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

Krok 3) Jeżeli wartości nie zamieniły się miejscami, zakończ pętlę wewnętrzną i kontynuuj wykonywanie pętli zewnętrznej.

Zoptymalizowane sortowanie bąbelkowe jest bardziej wydajne, ponieważ wykonuje tylko niezbędne kroki i pomija te, które nie są wymagane.

Reprezentacja wizualna

Mając listę pięciu elementów, poniższe obrazy ilustrują, w jaki sposób sortowanie bąbelkowe iteruje po wartościach podczas 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 od 6, więc 21 zajmuje pozycję zajmowaną przez 6, podczas gdy 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 miejscami 21 i 9.

Nowa lista wygląda teraz tak 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 zamianyping ma miejsce.

Krok 4)

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

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

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

Druga iteracja

Nowa lista po drugiej iteracji przedstawia się następująco:

Trzecia iteracja

Nowa lista po trzeciej iteracji przedstawia się następująco:

Czwarta iteracja

Nowa lista po czwartej iteracji przedstawia się następująco:

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 daje następujące wyniki:

[3, 6, 9, 21, 33]

Code Wyjaśnienie

Wyjaśnienie dot Python BubblKod programu e Sort jest następujący:

TUTAJ,

1. Definiuje funkcję bubbleSort, która akceptuje parametr theSeq. Kod nic nie wyświetla.
2. Pobiera długość tablicy i przypisuje wartość zmiennej n. Kod nie zwraca niczego.
3. Uruchamia pętlę for, która wykonuje algorytm sortowania bąbelkowego (n – 1) razy. To jest pętla zewnętrzna. Kod nie zwraca żadnego wyniku.
4. Definiuje zmienną flagową, która będzie używana do określenia, czy nastąpiła zamiana. Służy to celom optymalizacyjnym. Kod nie generuje żadnych wyników.
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 czasowej tmp, jeśli warunek zostanie oceniony jako prawdziwy. Kod nie zwraca niczego.
8. Wartość Seq[j + 1] jest przypisywana do pozycji Seq[j]. Kod nie zwraca niczego.
9. Wartość zmiennej tmp jest przypisywana do pozycji theSeq[j + 1]. Kod nie zwraca niczego.
10. Zmiennej flagi przypisana jest wartość 1, co oznacza, że ​​nastąpiła zamiana. Kod nie generuje żadnych wyników.
11. Używa instrukcji if, aby sprawdzić, czy wartość zmiennej flag wynosi 0. Kod nie wyprowadza niczego.
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ż posortowana lub prawie posortowana.
• Nie wymaga dużej pamięci.
• Łatwo jest napisać kod algorytmu.
• 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.
• Używa się go głównie w celach akademickich i nie w praktyce.
• Liczba kroków wymaganych do posortowania listy jest rzędu n².

Analiza złożoności Bubble Sortuj

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

1) Sortuj złożoność

Złożoność sortowania służy do wyrażania czasu wykonania i przestrzeni potrzebnej do posortowania listy. Sortowanie bąbelkowe wykonuje (n – 1) iteracji, aby posortować listę, gdzie n to całkowita liczba elementów na liście.

2) Złożoność czasowa

Złożoność czasowa sortowania bąbelkowego wynosi O(n²).

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(n²).
• 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] ⊝(n²).

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 na zmienną czasową używaną do zamiany.ping wartości. Dlatego ma złożoność przestrzenną O(1).

FAQ