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

Jump to navigation Jump to search
m
Riportate modifiche da en.wikibooks
m (Riportate modifiche da en.wikibooks)
 
 
L'algoritmo ''counting 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 contenente un numero di valori non oltresuperiore 2al doppio di N valori(cioè quando vale <code>M <= 2 * N</code>), questo algoritmo può essere notevolmente più veloce di [[w:Quick_sort|''quick sort'']].
In alcuni casi è più veloce anche per range più grandi, fino a 50 N.
 
Questo algoritmo può essere usato anche per un ordinamento parziale; per esempio, se la chiave è un intero compreso tra zero e un miliardo, si può ordinare solamente in base al byte più significativo della chiave, così da ottenere un ordine tale per cui per ogni n vale la formula <math>a_n < a_{n + 1} + 256*256*256. </math>
=== Partizionamento e ordinamento stabili ===
 
'''Se devi partizionare ooppure 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 ununo di 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)).
323

contributi

Menu di navigazione