Ce este un sortare cu bule?
Bubble Sort este un algoritm de sortare folosit pentru a sorta elementele listei în ordine crescătoare prin compararea a două valori adiacente. Dacă prima valoare este mai mare decât a doua valoare, prima valoare ia a doua poziție de valoare, în timp ce a doua valoare ia prima poziție de valoare. Dacă prima valoare este mai mică decât a doua valoare, atunci nu se face 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 se numește de obicei o trecere. Numărul de treceri dintr-o sortare cu bule este egal cu numărul de elemente dintr-o listă minus una.
În acest tutorial de sortare cu bule în Python veți afla:
- Ce este un sortare cu bule?
- Implementarea algoritmului de sortare cu bule
- Algoritm de sortare cu bule optimizat
- Reprezentare vizuala
- Exemple Python
- Explicarea codului
- Avantajele sortării cu bule
- Sortare cu bule Dezavantaje
- Analiza complexității sortării cu bule
Implementarea algoritmului de sortare cu bule
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 prezentată în ordine aleatorie și am dori să aranjăm articolele în mod ordonat
Luați în considerare următoarea listă:
[21,6,9,33,3]
Soluția
Repetați lista comparând două elemente adiacente și schimbându-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 cu bule funcționează după cum urmează
Pasul 1) Obțineți numărul total de elemente. Obțineți numărul total de articole din lista dată
Pasul 2) Determinați numărul de treceri exterioare (n - 1) care trebuie efectuate. Lungimea sa este lista minus una
Pasul 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
Pasul 4) Repetați pasul 3 până treceți la pasul exterior (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 ascendentă corectă.
Pasul 5) Întoarceți rezultatul când toate trecerile au fost efectuate. Returnează rezultatele listei sortate
Pasul 6) Optimizați algoritmul
Evitați treceri 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 rupe bucla mai devreme.
Algoritm de sortare cu bule optimizat
În mod implicit, algoritmul pentru sortarea cu bule în 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 prin restul valorilor. Iterația este terminată, iar următoarea este inițiată până la finalizarea procesului, după cum se arată în exemplul de sortare cu bule de mai jos.
Optimizarea se face urmând pașii următori
Pasul 1) Creați o variabilă de semnalizare care monitorizează dacă a avut loc o schimbare în bucla interioară
Pasul 2) Dacă valorile au schimbat pozițiile, continuați cu următoarea iterație
Pasul 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 omite 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 repetă valorile atunci când le sortați
Următoarea imagine arată lista nesortată
Prima iterație
Pasul 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 ia poziția ocupată de 6 în timp ce 6 ia poziția care a fost ocupată de 21
Lista noastră modificată arată acum ca cea de mai sus.
Pasul 2)
Valorile 21 și 9 sunt comparate.
21 este mai mare decât 9, deci schimbăm pozițiile 21 și 9
Noua listă este acum ca mai sus
Pasul 3)
Valorile 21 și 33 sunt comparate pentru a o găsi pe cea mai mare.
Valoarea 33 este mai mare decât 21, deci nu are loc nici o schimbare.
Pasul 4)
Valorile 33 și 3 sunt comparate pentru a o găsi pe cea mai mare.
Valoarea 33 este mai mare decât 3, așa că le schimbăm pozițiile.
Lista sortată 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
Exemple Python
Următorul cod arată cum să implementăm algoritmul Bubble Sort în 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)
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 codul programului Python Bubble Sort este după cum urmează
AICI,
- Definește o funcție bubbleSort care acceptă un parametru theSeq. Codul nu afișează nimic.
- Obține lungimea matricei și atribuie valoarea unei variabile n. Codul nu afișează nimic
- Pornește o buclă for care rulează algoritmul de sortare cu bule (n - 1) ori. Aceasta este bucla exterioară. Codul nu afișează nimic
- Definește o variabilă de semnalizare care va fi utilizată pentru a determina dacă a avut loc sau nu un swap. Aceasta este în scopul optimizării. Codul nu afișează nimic
- Pornește bucla interioară care compară toate valorile din listă de la prima la ultima. Codul nu afișează nimic.
- Folosește instrucțiunea if pentru a verifica dacă valoarea din partea stângă este mai mare decât cea din partea dreaptă imediată. Codul nu afișează nimic.
- Atribuie valoarea Seq [j] unei variabile temporale tmp dacă condiția se evaluează la adevărat. Codul nu afișează nimic
- Valoarea Seq [j + 1] este atribuită poziției Seq [j]. Codul nu afișează nimic
- Valoarea variabilei tmp este alocată poziției Seq [j + 1]. Codul nu afișează nimic
- Variabilului semnalizator i se atribuie valoarea 1 pentru a indica faptul că a avut loc un swap. Codul nu afișează nimic
- Folosește o instrucțiune if pentru a verifica dacă valoarea steagului variabilei este 0. Codul nu generează nimic
- Dacă valoarea este 0, atunci numim instrucțiunea break care iese din bucla interioară.
- Returnează valoarea Seq după ce a fost sortată. Codul afișează lista sortată.
- Definește o variabilă el care conține o listă de numere aleatorii. Codul nu afișează nimic.
- Atribuie valoarea funcției bubbleSort unui rezultat variabil.
- Tipărește valoarea rezultatului variabilei.
Avantajele sortării cu bule
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ă scrieți codul pentru algoritm
- Cerințele de spațiu sunt minime în comparație cu alți algoritmi de sortare.
Sortare cu bule 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 în principal în scopuri academice și nu în aplicația din lumea reală.
- Numărul de pași necesari pentru sortarea listei este de ordinul n 2
Analiza complexității sortării cu bule
Există trei tipuri de complexitate:
1) Sortează complexitatea
Complexitatea sortării este utilizată pentru a exprima cantitatea de timp de execuție și spațiul necesar pentru a sorta lista. Sortarea cu bule face (n - 1) iterații pentru a sorta lista în care n este numărul total de elemente din listă.
2) Complexitatea timpului
Complexitatea temporală a sortării cu bule este O (n 2 )
Complexitățile de timp pot fi clasificate ca:
- Cel mai rău caz - aici lista furnizată este în ordine descrescătoare. Algoritmul efectuează numărul maxim de execuții care este exprimat ca [Big-O] O (n 2 )
- Cel mai bun caz - apare 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 - apare atunci când lista este în ordine aleatorie. Complexitatea medie este reprezentată ca [Big-theta] ⊝ (n 2 )
3) Complexitatea spațială
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ă cu Python. Tot ce trebuie să utilizați sunt pentru bucle și declarații if.
- Problema rezolvată de algoritmul de sortare a bulelor este luarea unei liste aleatorii de articole și transformarea acesteia într-o listă ordonată.
- Algoritmul de sortare a bulei în structura de date se comportă 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 bule are o complexitate temporală de O (n 2 ) și o complexitate spațială de O (1)
- Algoritmul de sortare bubbler este cel mai potrivit pentru scopuri academice și nu pentru aplicații din lumea reală.
- Sortarea cu bule optimizată face algoritmul mai eficient omitând iterațiile inutile la verificarea valorilor care au fost deja sortate.
