Sortare cu bule vs Sortare prin inserare
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 prin inserție este, de asemenea, un algoritm de sortare, care funcționează prin inserarea unui element în lista de intrare în poziția corectă într-o listă care este deja sortată. Acest proces este aplicat în mod repetat până când lista este sortată.
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 prin inserare?
Insertion sort este un alt algoritm de sortare, care operează prin inserarea unui element în lista de intrare în poziția corectă într-o listă (care este deja sortată). Acest proces este aplicat în mod repetat până când lista este sortată. În sortarea prin inserție, sortarea se efectuează pe loc. Prin urmare, după a treia iterație a algoritmului, primele i+1 intrări din listă vor fi sortate, iar restul listei vor fi nesortate. La fiecare iterație, primul element din partea nesortată a listei va fi luat și inserat în locul corect din secțiunea sortată a listei. Sortarea prin inserare are o complexitate medie de timp a cazului de O(n2). Din acest motiv, sortarea prin inserare nu este potrivită pentru sortarea listelor mari.
Care este diferența dintre sortarea cu bule și sortarea prin inserție?
Chiar dacă atât algoritmul de sortare cu bule, cât și algoritmul de sortare prin inserție au complexități medii de timp de caz de O(n2), sortarea cu bule este aproape tot timpul depășită de sortarea prin inserț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ă. De asemenea, există o variantă de sortare prin inserție numită sortarea shell, care are o complexitate de timp de O(n3/2), ceea ce ar permite să fie utilizat practic. În plus, sortarea prin inserare este foarte eficientă pentru sortarea listelor „aproape sortate”, în comparație cu sortarea cu bule.
