Sortarea

Sortarea, în sens informatic, este procesul de aranjare a elementelor dintr-o colecție într-o ordine definită, de obicei crescătoare sau descrescătoare. Scopul sortării este să faciliteze accesul, căutarea și procesarea datelor prin organizarea acestora după o cheie sau un criteriu comun. Sortarea poate fi stabilă sau instabilă; stabilitatea înseamnă că elementele egale păstrează ordinea relativă dintre ele, în timp ce în sortările instabile acest lucru nu este garantat. De asemenea, poate fi efectuată in-place (fără spațiu suplimentar semnificativ) sau cu spațiu suplimentar, și poate ține de o sortare comparativă sau non-comparativă, în funcție de dacă se bazează pe ordinea dintre elemente.

Algoritmi comuni de sortare includ sortările simple, cum ar fi bubble sort, insertion sort și selection sort, utile pentru seturi mici sau pentru înțelegerea principiilor; precum și sortări eficiente pentru volume mari de date, cum ar fi merge sort, quicksort și heap sort. Sortările non-comparative, cum ar fi counting sort și radix sort, pot atinge complexitatea liniară în condiții speciale despre datele de intrare. Complexitatea temporală variază: în general, algoritmii de sortare eficienți au timp mediu O(n log n), în timp ce sortările simple pot avea O(n^2). Alegerea algoritmului depinde de mărimea datelor, distribuția valorilor, cerințele de stabilitate și de resursele de memorie. În istorie, contribuții semnificative au fost aduse de dezvoltatori precum von Neumann (merge sort) și Hoare (quicksort) în timpul evoluției informaticii.