Sortare cu bule vs Sortare prin selecție
Bubble sort este un algoritm de sortare care funcționează prin parcurgerea listei pentru a fi sortată în mod repetat în timp ce compară perechi de elemente adiacente. Dacă o pereche de elemente este în ordinea greșită, acestea sunt schimbate pentru a le plasa în ordinea corectă. Această traversare se repetă până când nu sunt necesare alte schimburi. Sortarea selecției este, de asemenea, un algoritm de sortare, care începe prin a găsi elementul minim din listă și a-l schimba cu primul element. Acest proces se repetă pentru restul listei, plasând elementele schimbate în ordine.
Ce este sortarea cu bule?
Bubble sort este un algoritm de sortare care funcționează prin parcurgerea listei pentru a fi sortată în mod repetat în timp ce compară perechi de elemente adiacente. Dacă o pereche de elemente este în ordinea greșită, acestea sunt schimbate pentru a le plasa în ordinea corectă. Această traversare se repetă până când nu sunt necesare alte schimburi (ceea ce înseamnă că lista este sortată). Deoarece elementele mai mici din listă ajung în partea de sus pe măsură ce o bula iese la suprafață, i se dă numele de sortare a bulelor. Sortarea cu bule este un algoritm de sortare foarte simplu, dar are o complexitate medie a timpului de caz de O(n2) atunci când sortați o listă cu n elemente. Din acest motiv, sortarea cu bule nu este potrivită pentru sortarea listelor cu un număr mare de elemente. Dar, datorită simplității sale, sortarea cu bule este predată în timpul introducerilor la algoritmi.
Ce este sortarea selecției?
Selection sort este, de asemenea, un alt algoritm de sortare care începe prin a găsi elementul minim din listă și a-l schimba cu primul element. Apoi elementul minim este găsit din restul listei (de la al doilea element până la ultimul element din listă) și schimbat cu al doilea element. Acest proces se repetă pentru restul listei prin plasarea elementelor schimbate în ordine. Deci, în sortarea prin selecție, la orice pas al algoritmului, lista este împărțită în două părți în care o parte conține elemente sortate, iar ceal altă parte conține elemente nesortate. Pe măsură ce algoritmul continuă, lista sortată crește de la stânga la dreapta. Sortarea selecției are, de asemenea, o complexitate medie a timpului de caz de O(n2). Prin urmare, nu este potrivit pentru sortarea listelor mari.
Care este diferența dintre sortarea cu bule și sortarea selecției?
Chiar dacă atât algoritmul de sortare cu bule, cât și algoritmul de sortare prin selecție au complexități medii de timp de caz de O(n2), sortarea cu bule este aproape întotdeauna depășită de sortarea prin selecție. Acest lucru se datorează numărului de schimburi necesare celor doi algoritmi (sortarea cu bule necesită mai multe schimburi). Dar, datorită simplității sortării cu bule, dimensiunea codului său este foarte mică. Stabilitatea este o altă diferență între acești doi algoritmi. Un algoritm de sortare stabil este un algoritm de sortare care păstrează ordinea înregistrărilor dacă lista conține elemente cu o valoare egală. În acest sens, sortarea prin selecție nu este un algoritm stabil, în timp ce sortarea cu bule este un algoritm stabil.
