Sortarea cu bule este un algoritm simplu care este folosit pentru a sorta un set dat de n elemente furnizate sub formă de matrice cu n număr de elemente. Bubble Sort compară toate elementele unul câte unul și le sortează pe baza valorilor lor.
Dacă tabloul dat trebuie să fie sortat în ordine crescătoare, atunci sortarea cu bulă va începe prin compararea primului element al tabloului cu cel de-al doilea element, dacă primul element este mai mare decât cel de-al doilea element, va schimba ambele elemente și apoi va trece la compararea celui de-al doilea și al treilea element, și așa mai departe. n elemente, atunci trebuie să repetăm acest proces de n-1 ori.
Este cunoscut sub numele de sortare cu bule, deoarece cu fiecare iterație completă, cel mai mare element din matricea dată, se ridică spre ultimul loc sau cel mai înalt indice, la fel ca o bulă de apă care se ridică până la suprafața apei.
Sortarea are loc parcurgând toate elementele unul câte unul și comparându-le cu elementul adiacent și schimbându-le dacă este necesar.
NOTĂ: Dacă nu sunteți familiarizat cu Sortarea în structura datelor, ar trebui să Mai întâi aflați ce este sortarea să știți despre elementele de bază ale sortării.
Implementarea algoritmului de sortare cu bule
Urmează pașii implicați în sortarea cu bule (pentru sortarea unei matrice date în ordine crescătoare):
- Începând cu primul element (index = 0), comparați elementul curent cu următorul element al tabloului.
- Dacă elementul curent este mai mare decât elementul următor din matrice, schimbați-le.
- Dacă elementul curent este mai mic decât elementul următor, treceți la elementul următor. Repetați Pasul 1.
Să considerăm o matrice cu valori {5, 1, 6, 2, 4, 3}
Mai jos, avem un reprezentare picturală a modului în care sortarea cu bule va sorta matricea dată.
Așa cum putem vedea în reprezentarea de mai sus, după prima iterație, 6 este plasat la ultimul index, care este poziția corectă pentru aceasta.
În mod similar după a doua iterație, 5 va fi la al doilea ultim index și așa mai departe.
Timpul pentru a scrie codul pentru sortarea cu bule:
Deși logica de mai sus va sorta o matrice nesortată, totuși algoritmul de mai sus nu este eficient deoarece, conform logicii de mai sus, for loop va continua să se execute timp de 6 iterații chiar dacă matricea este sortată după a doua iterație.
Deci, putem optimiza în mod clar algoritmul nostru.
Algoritmul de sortare cu bule optimizat
Pentru a ne optimiza balonul algoritmul de sortare, putem introduce un flag pentru a monitoriza dacă elementele sunt schimbate în interiorul buclei interne for.
Prin urmare, în bucla for interioară, verificăm dacă schimbarea elementelor are loc sau nu, de fiecare dată.
Dacă pentru o anumită iterație, nu a fost necesară nici o schimbare place, înseamnă că matricea a fost sortată și putem sări din bucla for, în loc să executăm toate iterațiile.
Să considerăm o matrice cu valori {11, 17, 18, 26, 23}
Mai jos, avem o reprezentare picturală a modului în care sortarea cu bule optimizată va sorta matricea dată.
După cum putem vedea, în prima iterație a avut loc schimbarea, de aceea am actualizat valoarea flag la 1, ca urmare, execuția intră din nou în bucla for. Dar în a doua iterație, nu va avea loc nici o schimbare, prin urmare valoarea flag va rămâne 0, iar execuția va ieși din buclă.
În codul de mai sus, în funcția bubbleSort, dacă pentru ciclu complet unic de j iterație (buclă interioară for), nu are loc nici o schimbare, apoi flag va rămâne 0 și apoi vom ieși din buclele for, deoarece tabloul a fost deja sortat.
Analiza complexității sortării cu bule
În sortarea cu bule, n-1 se vor face comparații în prima trecere, n-2 în a doua trecere, n-3 în a treia trecere și așa mai departe. Deci numărul total de comparații va fi,
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1 Suma = n (n- 1) /2i.e O (n2)
Prin urmare, complexitatea în timp a sortării cu bule este O (n2).
Principalul avantaj al sortării cu bule este simplitatea algoritmului.
Complexitatea spațiului pentru Sortarea cu bule este O (1), deoarece este necesar doar un singur spațiu de memorie suplimentar, adică pentru variabila temp.
De asemenea, cea mai bună complexitate a timpului de caz va fi O (n), atunci când lista este deja sortată.
Urmează complexitatea de timp și spațiu pentru algoritmul Sortare cu bule.
Acum că am învățat algoritmul de sortare Bubble, puteți verifica și acești algoritmi de sortare și aplicațiile acestora:
- Sortare prin inserare
- Sortare prin selecție
- Sortare rapidă
- Sortare combinată
- Sortare în grămadă
- Sortare în numărare
