sortare

Sortare, în informatică, este procesul de aranjare a elementelor unei colecții într-o ordine determinată de un criteriu, de obicei crescător sau descrescător. Criteriile pot fi valorile elementelor sau proprietăți asociate acestora, iar ordinea poate fi numerică, lexicografică sau bazată pe alte reguli. Sortarea este o operație fundamentală în prelucrarea datelor, facilitând interogări, citire și agregări, precum și pregătirea datelor pentru alte algoritmi.

Există două tipuri generale de sortare: comparativă și non-comparativă. În sortarea comparativă, elementele sunt comparate între ele pentru a determina ordinea, iar complexeitatea tipică este O(n log n) în medie pentru algoritmi ca mergesort, heapsort și quicksort (cu variante rapide). Quicksort poate avea timp în cel mai rău caz O(n^2). În sortarea non-comparativă, cum ar fi counting sort, radix sort sau bucket sort, se bazează pe distribuția valorilor și poate avea complexitate liniară în funcție de parametri, dar necesită condiții specifice ale datelor.

Proprietăți importante ale sortării includ stabilitatea (reținerea ordinii relative a elementelor egale) și dacă sortarea este realizată in-place sau necesită spațiu suplimentar. Alegerea algoritmului depinde de mărimea dataset-ului, limitările de memorie, necesitatea stabilității și natura valorilor.

Aplicații obișnuite includ organizarea datelor în baze de date, pregătirea listelor pentru interogări sau afișare, împachetarea datelor pentru algoritmi următori și optimizarea performanțelor aplicațiilor ce operează cu colecții mari de valori.