Sortare cu bule este considerat unul dintre cei mai simpli algoritmi de sortare care funcționează schimbând în mod repetat elementele adiacente dacă acestea sunt în ordinea greșită. Cu un algoritm de sortare cu bule, veți putea vedea că cel mai mare element (presupunând că sortăm de la cel mai mic la cel mai mare) va „bula” până în partea de sus a listei sau a matricei.

Exemplu:
Să presupunem că vrem să sortăm o listă sau o matrice de elemente în ordine crescătoare (de la cea mai mică la cea mai mare): List = (3,1,2)

Deoarece nu a avut loc nicio schimbare, acest lucru ne spune că matricea este deja sortate în ordine crescătoare!

Cel mai bun caz

Acum să încercăm din nou același algoritm, dar de data aceasta folosind scenariul cel mai bun caz, care este atunci când elementele sunt deja sortate în ordine ( ascendent) ne-ar plăcea.

Întrucât nu s-a produs nicio schimbare, am terminat, iar algoritmul a făcut doar 2 comparații și numărul de elemente din matricea pe care o vom numi n = 3. Deci, putem vedea că pentru n elementele în care cel mai bun caz al algoritmilor va lua doar comparații n-1, n-1 = O (n)

Procedura sau algoritmul pe care l-am folosit este mai jos:

Acest algoritm folosește un flag pentru a spune dacă elementele au fost schimbate sau nu , care permite ca algoritmul de sortare a bulei să fie cel mai bun caz O (n) în loc de O (n²) ca o altă implementare a sortării cu bule.

Algoritmul de mai sus
Cel mai grav caz = O (n²) > Cel mai bun caz = O (n)

Să aruncăm o privire la o implementare diferită a algoritmului de sortare cu bule:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

Algoritmul de mai sus
Cel mai grav caz = O (n²)
Cel mai bun caz = O (n²)

Cel mai grav caz

Să sortăm o matrice sau o listă = (3,2,1) acesta ar fi cel mai rău caz în care lista este în ordinea complet opusă decât cea dorită (în ordine crescătoare) folosind algoritmul de mai sus.

Prima trecere:
(3,2,1) – > Comparați elementele 3 & 2
(2,3 , 1) – > Swap 3 & 2 din 2 < 3
( 2,3,1) – > Comparați elementele 3 & 1
(2,1,3) – > Schimbați 1 & 3 din moment ce 1 < 3

A doua trecere:
(2,1,3) – > Comparați elementele 2 & 1
(1,2,3) – > Swap 2 & 1 din moment ce 1 < 2
(1,2,3) – > Comparați elements 2 & 3
(1,2,3) – > Nu este nevoie de SWAPPING din 2 < 3

Acum am terminat de parcurs ambele bucle, astfel încât matricea trebuie să fie sortată în ordine crescătoare.

Observați că am făcut 4 comparații în al doilea exemplu de mai sus și numărul de elemente din matrice pe care îl vom numi ‘n’ = 3, deci numărul comparațiilor făcute este (n-1) ² și (n-1) ² = O (n²)

De asemenea, o carte minunată pentru a vă pregăti pentru interviuri de codare / programare se numește crăparea interviului de codare. Vă va ajuta să vă familiarizați cu algoritmii de sortare și rezolvarea problemelor, așa că asigurați-vă că verificați!

Vă mulțumim că ați citit acest articol și sper să vă fie de ajutor tuturor! Continuați învățarea și, dacă doriți mai multe videoclipuri cu analize algoritmice, vă rugăm să vizitați și să vă abonați la canalele mele YouTube (randerson112358 & compsci112358)

mai mult conținut / videoclipuri despre analiza și programarea algoritmului:

Canal YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Website:

Tutoriale video despre relația de recurență:

Tutorial video despre analiza algoritmului:

Twitter: