Ottimizzare C++/Tecniche generali di ottimizzazione/Ordinamento: differenze tra le versioni

'''Per ordinare un insieme di dati in base a una chiave intera avente un range limitato, usa l'algoritmo [[Implementazioni_di_algoritmi/Counting_sort|countingsort''counting sort'']].'''

L'algoritmo ''countingsortcounting sort'' ha complessità O(N+M), dove N è il numero di elementi da ordinare e M è il range delle chiavi di ordinamento, cioè la differenza tra la chiave massima e la chiave minima.

Nel caso in cui si vogliano ordinare N elementi la cui chiave è un numero intero appartenente a un intervallo di non oltre 2 N valori, questo algoritmo può essere notevolmente più veloce di quicksort[[w:Quick_sort|''quick sort'']].

In STL c'è l'algoritmo ''<code>std::partition''</code>, che è più veloce dell'algoritmo ''<code>std::sort''</code>, in quanto ha complessità O(N) invece di O(N log(N)).

In STL c'è l'algoritmo di partizionamento ''<code>std::stable_partition''</code>, che è leggermente più lento dell'algoritmo ''<code>std::partition''</code>; e c'è l'algoritmo di ordinamento ''<code>std::stable_sort''</code>, che è leggermente più lento dell'algoritmo ''<code>std::sort''</code>.

In STL c'è l'algoritmo ''<code>std::nth_element''</code>, che, pur essendo leggermente più lento dell'algoritmo ''<code>std::stable_partition''</code>, è notevolmente più veloce dell'algoritmo ''<code>std::sort''</code>, in quanto ha complessità O(N) invece di O(N log(N)).

In STL ci sono gli algoritmi ''<code>std::partial_sort''</code> e ''<code>std::partial_sort_copy''</code>, che, pur essendo più lenti dell'algoritmo ''<code>std::nth_element''</code>, sono tanto più veloci dell'algoritmo <code>std::sort</code> quanto più è breve la sequenza parziale da ordinare rispetto a quella totale.

{{Avanzamento|75100%|2325 maggio 2008}}