Bubble Sortare algoritm cu Python folosind List Example

Ce este a Bubble Sort?

Bubble Sortare este un algoritm de sortare utilizat pentru a sorta elementele unei liste în ordine crescătoare, comparând două valori adiacente. Dacă prima valoare este mai mare decât a doua valoare, prima valoare ocupă poziția celei de-a doua valori, în timp ce a doua valoare ocupă poziția primei valori. Dacă prima valoare este mai mică decât a doua valoare, atunci nu există nicio schimbare.ping este gata.

Acest proces se repetă până când toate valorile dintr-o listă au fost comparate și schimbate dacă este necesar. Fiecare iterație este de obicei numită trecere. Numărul de treceri într-o sortare cu bule este egal cu numărul de elemente dintr-o listă minus unu.

În acest Bubble Sortare în Python tutorial Vei învăța problema pe care o rezolvă, forma sa optimizată, o prezentare vizuală pas cu pas, o metodă de lucru Python program și caracteristicile sale de performanță.

Implementarea Bubble Algoritm de sortare

Vom împărți implementarea în trei (3) etape, și anume problema, soluția și algoritmul pe care îl putem folosi pentru a scrie cod pentru orice limbaj de programare.

Problema

O listă de elemente este dată în ordine aleatorie și am dori să le aranjăm într-o manieră ordonată.

Luați în considerare următoarea listă:

[21, 6, 9, 33, 3]

Soluția

Iterează lista comparând două elemente adiacente și interschimbându-leping le dacă prima valoare este mai mare decât a doua valoare.

Rezultatul ar trebui să fie după cum urmează:

[3, 6, 9, 21, 33]

Algoritm

Algoritmul de sortare prin bule funcționează după cum urmează:

Pas 1) Obțineți numărul total de elemente. Obțineți numărul total de articole din lista dată.

Pas 2) Determinați numărul de treceri exterioare (n – 1) care trebuie efectuate. Lungimea sa este listă minus unu.

Pas 3) Efectuați treceri interioare (n – 1) de ori pentru trecerea externă 1. Obțineți valoarea primului element și comparați-o cu a doua valoare. Dacă a doua valoare este mai mică decât prima valoare, atunci inversați pozițiile.

Pas 4) Repetați pasul 3 până când ajungeți la pasul exterior (n – 1). Obțineți următorul element din listă, apoi repetați procesul efectuat la pasul 3 până când toate valorile au fost plasate în ordinea crescătoare corectă.

Pas 5) Returnează rezultatul când toate trecerile au fost efectuate. Returnează rezultatele listei sortate.

Pas 6) Algoritm de optimizare.

Evitați trecerile interioare inutile dacă lista sau valorile adiacente sunt deja sortate. De exemplu, dacă lista furnizată conține deja elemente care au fost sortate în ordine crescătoare, atunci putem întrerupe bucla mai devreme.

Optimizat Bubble Algoritm de sortare

În mod implicit, algoritmul pentru sortarea cu bule Python compară toate elementele din listă, indiferent dacă lista este deja sortată sau nu. Dacă lista dată este deja sortată, compararea tuturor valorilor este o pierdere de timp și resurse.

Optimizarea sortării cu bule ne ajută să evităm iterațiile inutile și să economisim timp și resurse.

De exemplu, dacă primul și al doilea element sunt deja sortate, atunci nu este nevoie să iterați restul valorilor. Iterația se încheie, iar următoarea este inițiată până când procesul este finalizat, așa cum se arată în mai jos Bubble Exemplu de sortare.

Optimizarea se face utilizând următorii pași:

Pas 1) Creați o variabilă flag care monitorizează dacă există vreun schimbping a avut loc în bucla interioară.

Pas 2) Dacă valorile și-au schimbat pozițiile, se continuă cu următoarea iterație.

Pas 3) Dacă valorile nu și-au schimbat pozițiile, terminați bucla interioară și continuați cu bucla exterioară.

O sortare optimizată cu bule este mai eficientă, deoarece execută doar pașii necesari și îi omite pe cei care nu sunt necesari.

Reprezentare vizuala

Având o listă de cinci elemente, următoarele imagini ilustrează modul în care sortarea cu bule iterează prin valori atunci când le sortează.

Următoarea imagine prezintă lista nesortată:

Prima iterație

Pas 1)

Valorile 21 și 6 sunt comparate pentru a verifica care dintre ele este mai mare decât cealaltă.

21 este mai mare decât 6, deci 21 ocupă poziția ocupată de 6, în timp ce 6 ocupă poziția care era ocupată de 21.

Lista noastră modificată arată acum ca cea de mai sus.

Pas 2)

Se compară valorile 21 și 9.

21 este mai mare decât 9, așa că inversăm pozițiile lui 21 și 9.

Noua listă este acum cea de mai sus.

Pas 3)

Valorile 21 și 33 sunt comparate pentru a găsi cea mai mare.

Valoarea 33 este mai mare decât 21, deci nu există schimb.ping preia.

Pas 4)

Valorile 33 și 3 sunt comparate pentru a găsi cea mai mare.

Valoarea 33 este mai mare decât 3, așa că le schimbăm pozițiile.

Lista sortată de la sfârșitul primei iterații este ca cea de mai sus.

A doua iterație

Noua listă după a doua iterație este următoarea:

A treia iterație

Noua listă după a treia iterație este următoarea:

A patra iterație

Noua listă după a patra iterație este următoarea:

Python Exemple

Următorul cod arată cum se implementează Bubble Sortați algoritmul 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)

Executarea programului de sortare cu bule de mai sus în Python produce următoarele rezultate:

[3, 6, 9, 21, 33]

Code Explicație

Explicația pentru Python BubblCodul programului de sortare e este următorul:

AICI,

1. Definește o funcție bubbleSort care acceptă un parametru theSeq. Codul nu scoate nimic.
2. Obține lungimea matricei și atribuie valoarea unei variabile n. Codul nu afișează nimic.
3. Pornește o buclă for care rulează algoritmul de sortare cu bule (n – 1) ori. Aceasta este bucla externă. Codul nu generează nimic.
4. Definește o variabilă flag care va fi utilizată pentru a determina dacă a avut loc sau nu o schimbare. Acest lucru este în scopuri de optimizare. Codul nu afișează nimic.
5. Pornește bucla interioară care compară toate valorile din listă de la prima la ultima. Codul nu scoate nimic.
6. Utilizează instrucțiunea if pentru a verifica dacă valoarea din partea stângă este mai mare decât cea din partea dreaptă imediată. Codul nu scoate nimic.
7. Atribuie valoarea lui theSeq[j] unei variabile temporale tmp dacă condiția este evaluată ca adevărată. Codul nu afișează nimic.
8. Valoarea lui Seq[j + 1] este atribuită poziției lui Seq[j]. Codul nu afișează nimic.
9. Valoarea variabilei tmp este atribuită poziției theSeq[j + 1]. Codul nu afișează nimic.
10. Variabilei flag i se atribuie valoarea 1 pentru a indica faptul că a avut loc o schimbare. Codul nu afișează nimic.
11. Folosește o instrucțiune if pentru a verifica dacă valoarea variabilei flag este 0. Codul nu afișează nimic.
12. Dacă valoarea este 0, atunci numim instrucțiunea break care iese din bucla interioară.
13. Returnează valoarea Seq după ce a fost sortat. Codul scoate lista sortată.
14. Definește o variabilă el care conține o listă de numere aleatoare. Codul nu scoate nimic.
15. Atribuie valoarea funcției bubbleSort unui rezultat variabil.
16. Imprimă valoarea rezultatului variabilei.

Bubble fel de avantaje

Următoarele sunt câteva dintre avantajele algoritmului de sortare cu bule:

• Este ușor de înțeles.
• Se comportă foarte bine atunci când lista este deja sau aproape sortată.
• Nu necesită memorie extinsă.
• Este ușor să scrii codul pentru algoritm.
• Cerințele de spațiu sunt minime în comparație cu alți algoritmi de sortare.

Bubble sort Dezavantaje

Următoarele sunt câteva dintre dezavantajele algoritmului de sortare cu bule:

• Nu funcționează bine atunci când sortați liste mari. Este nevoie de prea mult timp și resurse.
• Este folosit mai ales în scopuri academice și nu pentru aplicații în lumea reală.
• Numărul de pași necesari pentru sortarea listei este de ordinul n².

Analiza complexității Bubble Sortare

Există trei tipuri de complexitate:

1) Sortați complexitatea

Complexitatea sortării este utilizată pentru a exprima timpul și spațiul de execuție necesare pentru a sorta lista. Sortarea cu bule face (n – 1) iterații pentru a sorta lista, unde n este numărul total de elemente din listă.

2) Complexitatea timpului

Complexitatea temporală a sortării cu bule este O(n²).

Complexitățile de timp pot fi clasificate astfel:

• Cel mai rău caz – aici este lista furnizată în ordine descrescătoare. Algoritmul realizează numărul maxim de execuții care este exprimat ca [Big-O] O(n²).
• Cel mai bun caz – aceasta se întâmplă atunci când lista furnizată este deja sortată. Algoritmul efectuează numărul minim de execuții, care este exprimat ca [Big-Omega] Ω(n).
• Caz mediu – acest lucru se întâmplă atunci când lista este în ordine aleatorie. Complexitatea medie este reprezentată ca [Big-theta] ⊝(n²).

3) Complexitatea spațiului

Complexitatea spațiului măsoară cantitatea de spațiu suplimentar necesară pentru sortarea listei. Sortarea cu bule necesită doar un (1) spațiu suplimentar pentru variabila temporală utilizată pentru swap.ping valori. Prin urmare, are o complexitate spațială de O(1).

Întrebări frecvente