Quicksort: differenze tra le versioni

 
Se nello stesso vettore esistono degli elementi ripetuti, è possibile sistemarli nella prima scansione che viene effettuata tramite la versione di Bentley - Mc Illroy del 1993.
Questa versione prevede che, durante il processo di scansione (fase di partizionamento dell'algoritmo), gli elementi uguali al pivot vengano spostati immediatamente a fianco del pivot (a sinistra se provengono dalla parte sinistra, a destra se provengono dalla parte destra). In questo modo avrò tre partizioni, una con gli elementi minori del pivot, una con gli elementi uguali e una con gli elementi maggiori del pivot.
 
La complessità dell'algoritmo non viene modificata.
Utente anonimo