Diferența dintre sortarea bulelor și sortarea selecției
Conţinut
Sortarea este una dintre sarcinile majore ale programelor de calculator în care elementele unui tablou sunt aranjate într-o anumită ordine. Sortarea facilitează căutarea. Sortarea bulelor și sortarea selecției sunt algoritmi de sortare care pot fi diferențiați prin metodele pe care le utilizează pentru sortare. Sortarea cu bule schimbă în esență elementele în timp ce sortarea de selecție efectuează sortarea selectând elementul.
O altă diferență considerabilă între cele două este că sortarea cu bule este un algoritm stabil, în timp ce sortarea de selecție este un algoritm instabil. Un algoritm este considerat a fi constant elementele cu aceeași cheie care au apărut în aceeași ordine în care au apărut înainte de a sorta în listă sau tablou. În general, majoritatea algoritmilor stabili și rapizi folosesc memorie suplimentară.
- Diagramă de comparație
- Definiție
- Diferențele cheie
- Concluzie
Diagramă de comparație
| Baza de comparație | Sort de bule | Sortare de selecție |
|---|---|---|
| De bază | Elementul alăturat este comparat și schimbat | Cel mai mare element este selectat și schimbat cu ultimul element (în caz de ordine crescătoare). |
| Complexitatea timpului cel mai bun | Pe) | Pe2) |
| Eficienţă | Ineficace | Eficiență îmbunătățită comparativ cu tipul de bule |
| Grajd | da | Nu |
| Metodă | schimbul | Selecţie |
| Viteză | Încet | Rapid în comparație cu sortul cu bule |
Definiția Bubble Sort
Sort de bule este cel mai simplu algoritm iterativ care operează prin compararea fiecărui element sau element cu elementul de lângă acesta și schimbarea acestora, dacă este nevoie. În cuvinte simple, comparează primul și al doilea element al listei și îl schimbă, cu excepția cazului în care acestea nu sunt în ordine. În mod similar, al doilea și al treilea element sunt comparate și schimbate, iar această comparație și schimbare continuă până la sfârșitul listei. Numărul de comparații din prima iterație este n-1 unde n este elementele numerice dintr-un tablou. Cel mai mare element ar fi pe poziția a noua după prima iterație. Și după fiecare iterație, numărul de comparații scade și în sfârșit, iterarea are loc doar o comparație.
Acest algoritm este cel mai lent algoritm de sortare. Cea mai bună complexitate a cazurilor (atunci când lista este în ordine) a tipului Bubble este de ordinul n (Pe)), iar complexitatea dintre cele mai grave cazuri este Pe2). În cel mai bun caz, este de ordin n, deoarece comparează elementele și nu le schimbă. Această tehnică necesită, de asemenea, spațiu suplimentar pentru stocarea variabilei temporare.
Definiția Selection Sort
Sortare de selecție a obținut performanțe puțin mai bune și este eficient decât algoritmul de sortare a bulelor. Să presupunem că dorim să aranjăm un tablou în ordine crescătoare, apoi acesta funcționează găsind cel mai mare element și schimbând-l cu ultimul element și repetăm următorul proces în sub-tablouri până când se listează întreaga listă.
- În sortul cu bule, fiecare element și elementul său adiacent este comparat și schimbat dacă este necesar. Pe de altă parte, sortarea selecției funcționează prin selectarea elementului și schimbarea acelui element cu ultimul element. Elementul selectat poate fi cel mai mare sau cel mai mic în funcție de ordine adică, crescător sau descendent.
- Complexitatea dintre cele mai grave cazuri este aceeași atât în algoritmi, adică O (n2), dar cea mai bună complexitate este diferită. Sortul cu bule are o ordine de n timp, în timp ce sortarea de selecție consumă o ordine de n2 timp.
- Sortarea cu bule este un algoritm stabil, în schimb, sortarea de selecție este instabilă.
- Algoritmul de sortare a selecției este rapid și eficient, în comparație cu sortarea cu bule, care este foarte lent și ineficient.
Concluzie
Algoritmul de sortare a bulelor este considerat cel mai simplu și ineficient algoritm, dar algoritmul de sortare a selecției este eficient în comparație cu sortarea bulelor. Sortul cu bule consumă, de asemenea, spațiu suplimentar pentru stocarea variabilei temporare și are nevoie de mai multe schimburi.
