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

nessun oggetto della modifica
m (Bot: Sostituzione automatica (-[[Categoria:Ottimizzare C++|Ottimizzare C++/Tecniche generali di ottimizzazione/ +[[Categoria:Ottimizzare C++|))
Nessun oggetto della modifica
=== Countingsort ===
 
'''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 alcuni casi è più veloce anche per range più grandi, fino a 50 N.
 
'''Se devi solo dividere una sequenza in due gruppi in base a un criterio, usa un algoritmo di partizionamento, invece di uno di ordinamento.'''
 
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)).
 
=== Partizionamento e ordinamento stabili ===
'''Se devi partizionare o ordinare una sequenza per cui non è richiesto di mantenere l'ordine delle entità equivalenti, non usare un algoritmo stabile.'''
 
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>.
 
=== Partizionamento d'ordine ===
'''Se devi solo individuare i primi N elementi di una sequenza, o l'N-esimo elemento di una sequenza, usa un algoritmo di partizionamento d'ordine, invece di un ordinamento.'''
 
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)).
 
=== Statistica d'ordine ===
'''Se devi solo ordinare i primi N elementi di una sequenza, usa un algoritmo di statistica d'ordine, invece di un algoritmo di ordinamento.'''
 
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.
 
[[Categoria:Ottimizzare C++|Ordinamento]]
{{Avanzamento|75100%|2325 maggio 2008}}
323

contributi