Recomandat, 2022

Alegerea Editorului

Diferența dintre sortarea și clasarea selecției cu bule

Sortarea este una dintre sarcinile majore în programele de calculator în care elementele unei matrice sunt aranjate într-o anumită ordine. Sortare face căutarea mai ușoară. Tipul de sortare a sortimentelor și sortarea selecției sunt algoritmii de sortare care pot fi diferențiați prin metodele pe care le folosesc pentru sortare. Modulul cu bule schimbă în esență elementele, în timp ce sortarea selecției efectuează sortarea prin selectarea elementului.

O altă diferență considerabilă între cele două este faptul că sortarea bulelor este un algoritm stabil în timp ce sortarea selecției este un algoritm instabil. Un algoritm este considerat a fi stabil elementul cu aceeași cheie care apare în aceeași ordine în care s-au întâmplat înainte de sortare în listă sau matrice. În general, cei mai stabili și rapizi algoritmi folosesc memorie suplimentară.

Diagramă de comparație

Bazele de comparațieBubble sort
Selecția sortimentului
De bazăElementul adiacent este comparat și înlocuitCel mai mare element este selectat și înlocuit cu ultimul element (în cazul ordinii ascendente).
Cel mai bun complexitate de timpPe)O (n2)
EficienţăIneficaceCreșterea eficienței în comparație cu sortarea cu bule
GrajddaNu
MetodăschimbulSelecţie
VitezăÎncetRapid comparativ cu sortarea cu bule

Definiția Bubble Sort

Tipul de tip "bubble" este cel mai simplu algoritm iterativ care funcționează prin compararea fiecărui element sau element cu elementul de lângă el și schimbarea acestuia dacă este necesar. Cuvintele simple compară primul și al doilea element al listei și o schimbă dacă nu se află în afara ordinii. În mod similar, al doilea și al treilea element sunt comparate și schimbate, iar această comparare ș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 numărul de elemente dintr-o matrice. Cel mai mare element ar fi în poziția n după prima repetare. După fiecare repetare, numărul de comparații scade, iar la ultima iterație are loc doar o singură comparație.

Acest algoritm este cel mai lent algoritm de sortare. Cea mai bună complexitate a cazului (atunci când lista este în ordine) a sorții Bubble este de ordin n ( O (n) ), iar complexitatea celui mai rău caz este O (n2) . În cel mai bun caz, este de ordinul n, deoarece doar compară elementele și nu le schimbă. Această tehnică necesită, de asemenea, spațiu suplimentar pentru stocarea variabilei temporare.

Definiția selecție Sortare

Tipul de selecție a obținut performanțe ușor mai bune și este eficient decât algoritmul de sortare a bulelor. Să presupunem că dorim să aranjăm o matrice în ordine ascendentă, atunci funcționează prin găsirea celui mai mare element și schimbarea acestuia cu ultimul element și repetând următorul proces pe sub-arrays până la ordonarea întregii liste.

În sortarea selecției, matricea sortată și nesortată nu face nicio diferență și consumă o ordine de n2 ( O (n2) ) atât în ​​cel mai bun, cât și în cel mai rău caz de complexitate. Selecția de sortare este mai rapidă decât cea de tip Bubble.

Diferențe cheie între sortarea și selecția tipului de bule

  1. În sortarea bulelor, fiecare element și elementul său adiacent sunt comparate și schimbate dacă este necesar. Pe de altă parte, selecția de sortare funcționează selectând elementul și schimbând elementul respectiv cu ultimul element. Elementul selectat ar putea fi cel mai mare sau cel mai mic în funcție de ordine, de exemplu, ascendent sau descendent.
  2. Cea mai gravă complexitate a cazului este aceeași în ambii algoritmi, adică O (n2), dar cea mai bună complexitate este diferită. Tipul de tip bubble are o ordine de timp, în timp ce sortarea de selecție consumă o ordine de n2 timp.
  3. Tipul de tip "bubble" este un algoritm stabil, prin contrast, sortarea selecției este instabilă.
  4. Algoritmul de sortare a selecției este rapid și eficient în comparație cu sortarea bulelor, care este foarte lentă și ineficientă.

Concluzie

Algoritmul de sortare a algoritmului de tip "bubble" este considerat cel mai simplu și ineficient algoritm, dar algoritmul de selecție a selecției este eficient în comparație cu sortarea cu bule. De asemenea, tipul de tip Bubble consumă spațiu suplimentar pentru stocarea variabilei temporare și are nevoie de mai multe swap-uri.

Top