Bubble Sortare algoritm cu Python folosind List Example

Ce este a Bubble Sort?

Bubble Sortare este un algoritm de sortare folosit pentru a sorta elementele din listă în ordine crescătoare prin compararea a două valori adiacente. Dacă prima valoare este mai mare decât a doua valoare, prima valoare ocupă poziţia a doua, în timp ce a doua valoare ocupă poziţia primei valori. Dacă prima valoare este mai mică decât a doua valoare, atunci nu se efectuează nicio schimbare.

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 o sa inveti:

Implementarea Bubble Algoritm de sortare

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

Problema

O listă de articole este dată în ordine aleatorie și am dori să aranjam articolele într-o manieră ordonată

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

[21,6,9,33,3]

Soluția

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

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

[3,6,9,21,33]

Algoritm

Algoritmul de sortare cu 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) de făcut. Lungimea sa este lista minus unu

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

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

Pas 5) Întoarceți rezultatul când toate trecerile au fost făcute. Returnează rezultatele listei sortate

Pas 6) Algoritmul 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 folosind următorii pași

Pas 1) Creați o variabilă flag care monitorizează dacă a avut loc vreo schimbare în bucla interioară

Pas 2) Dacă valorile au schimbat poziții, continuați cu următoarea iterație

Pas 3) Dacă beneficiile nu 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 în vedere 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 arată lista nesortată

Reprezentare vizuala

Prima iterație

Pas 1)

Reprezentare vizuala

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

Reprezentare vizuala

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

Reprezentare vizuala

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

Pas 2)

Reprezentare vizuala

Se compară valorile 21 și 9.

Reprezentare vizuala

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

Reprezentare vizuala

Noua listă este acum ca mai sus

Pas 3)

Reprezentare vizuala

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

Reprezentare vizuala

Valoarea 33 este mai mare decât 21, deci nu are loc nicio schimbare.

Pas 4)

Reprezentare vizuala

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

Reprezentare vizuala

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

Reprezentare vizuala

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

Reprezentare vizuala

A treia iterație

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

Reprezentare vizuala

A patra iterație

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

Reprezentare vizuala

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

[6, 9, 21, 3, 33]

Explicarea codului

Explicația pentru Python Bubble Sortarea codului programului este după cum urmează

Explicarea codului

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 scoate nimic
  3. Pornește o buclă for care rulează algoritmul de sortare cu bule (n – 1) ori. Aceasta este bucla exterioară. Codul nu scoate 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 scoate 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. Asignează valoarea theSeq[j] unei variabile temporale tmp dacă condiția este evaluată ca adevărată. Codul nu scoate nimic
  8. Valoarea Seq[j + 1] este atribuită poziției Seq[j]. Codul nu scoate nimic
  9. Valoarea variabilei tmp este atribuită poziției theSeq[j + 1]. Codul nu scoate nimic
  10. Variabilei steag i se atribuie valoarea 1 pentru a indica faptul că a avut loc o schimbare. Codul nu scoate nimic
  11. Utilizează o instrucțiune if pentru a verifica dacă valoarea indicatorului variabilei este 0. Codul nu scoate 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
  • Funcționează foarte bine atunci când lista este deja sau aproape sortată
  • Nu necesită memorie extinsă.
  • Este ușor să scrieți 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 în aplicația reală.
  • Numărul de pași necesari pentru sortarea listei este de ordinul n2

Analiza complexității Bubble Sortare

Există trei tipuri de complexitate:

1) Sortați complexitatea

Complexitatea sortării este utilizată pentru a exprima cantitatea de timpi de execuție și spațiul necesar pentru sortarea listei. 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(n2)

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(n2)
  • Cel mai bun caz – acest lucru se întâmplă atunci când lista furnizată este deja sortată. Algoritmul realizează 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] ⊝(n2)

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 schimbarea valorilor. Prin urmare, are o complexitate spațială de O (1).

Rezumat

  • Algoritmul de sortare cu bule funcționează comparând două valori adiacente și schimbându-le dacă valoarea din stânga este mai mică decât valoarea din dreapta.
  • Implementarea unui algoritm de sortare cu bule este relativ simplă Python. Tot ce trebuie să utilizați sunt instrucțiunile pentru bucle și if.
  • Problema pe care o rezolvă algoritmul de sortare cu bule este de a lua o listă aleatorie de articole și de a o transforma într-o listă ordonată.
  • Algoritmul de sortare cu bule în structura de date funcționează cel mai bine atunci când lista este deja sortată, deoarece efectuează un număr minim de iterații.
  • Algoritmul de sortare cu bule nu funcționează bine atunci când lista este în ordine inversă.
  • Sortarea cu barbotare are o complexitate de timp de O (n2) și o complexitate spațială de O (1)
  • Algoritmul de sortare cu barbotare este cel mai potrivit pentru scopuri academice și nu pentru aplicațiile din lumea reală.
  • Sortarea cu bule optimizată face algoritmul mai eficient, omitând iterațiile inutile atunci când se verifică valorile care au fost deja sortate.