requisiti di iteratore di ordinamento rapido

Question

tl; dr: È possibile implementare quicksort su una lista doppiamente collegata in modo efficiente? La mia comprensione prima di pensarci era, no, non è così.

L'altro giorno ho avuto l'opportunità di considerare i requisiti degli iteratori per gli algoritmi di ordinamento di base. Le unità base (N²) sono abbastanza semplici.

• Ordinamento di bolle - 2 iteratori di inoltro funzionano bene, uno dopo l'altro.
• Ordinamento inserzione - eseguiranno 2 iteratori bidirezionali. Uno per l'elemento out-of-order, uno per il punto di inserimento.
• Selezione sort - Un po 'più complicato ma gli iteratori in avanti possono fare il trucco.

Quicksort

L'introsort_loop in std :: sort (come nella GNU libreria/CV standard (1994)/Silicon Graphics (1996)) richiede di essere random_access.

__introsort_loop(_RandomAccessIterator __first, 
     _RandomAccessIterator __last, 
     _Size __depth_limit, _Compare __comp) 

Come mi sono aspettato.

Ora, a un'ispezione più ravvicinata, non riesco a trovare il vero motivo per richiederlo per quicksort. L'unica cosa che richiede esplicitamente random_access_iterators è la chiamata std::__median che richiede il calcolo dell'elemento intermedio. Il quicksort regolare, vaniglia non corrisponde a calcola la mediana.

Il partizionamento consiste in un assegno

if (!(__first < __last)) 
    return __first; 

Non

davvero un assegno utile per bidirectionals. Tuttavia si dovrebbe essere in grado di sostituire questo con un assegno nel precedente viaggio partizionamento (da sinistra a destra/destra a sinistra) con un semplice stato di

if (__first == __last) this_partitioning_is_done = true; 

È possibile implementare quicksort abbastanza efficiente utilizzando iteratori solo bidirezionali ? La profondità ricorsiva può ancora essere protetta.

NB. Non ho ancora tentato un'implementazione effettiva.

Answer 1

tl; dr: Sì

Come dici tu, il problema è quello di trovare l'elemento di rotazione, che è l'elemento in mezzo, trovando questo con accesso casuale prende O (1), trovando con gli iteratori bidirezionali richiedono O (n) (operazioni n/2, per la precisione). Tuttavia, in ogni passaggio devi creare contenitori secondari, rispettivamente a sinistra ea destra contenenti numeri sempre più piccoli. È qui che si svolge il lavoro principale di ordinamento rapido, giusto?

Ora, quando si costruiscono i sub contenitori (per la fase di ricorsione) il mio approccio sarebbe quello di creare un iteratore h che punta al rispettivo elemento frontale.Ora ogni volta che si sceglie un elemento successivo per andare al contenitore secondario, è sufficiente avanzare h ogni secondo. Questo avrà il punto h per l'elemento pivot una volta che sei pronto per scendere al nuovo passo di ricorsione.

Devi solo trovare il primo pivot che non ha importanza, perché O (n log n + n/2) = O (n log n).

In realtà questo è solo un ottimizzare l'autonomia, ma non ha alcun impatto sulla complessità, a causa sia di eseguire iterazioni sulla lista una volta (per mettere ogni valore nel rispettivo contenitore di sub) o due volte (per trovare il perno e poi mettere ogni valore nel rispettivo sotto-contenitore) è lo stesso: O (2n) = O (n).
È semplicemente una questione di tempo di esecuzione (non di complessità).

Answer 2

Sono necessari iteratori di accesso casuale perché in genere si desidera selezionare l'elemento di pivot dal centro dell'elenco. Se si sceglie il primo o l'ultimo elemento come pivot, gli iteratori bidirezionali sono sufficienti, ma Quicksort degenera su O (n^2) per gli elenchi preordinati.

Answer 3

Non c'è alcun problema con l'implementazione della strategia di ordinamento rapido in un elenco collegato in doppia connessione. (Penso che possa essere facilmente adattato anche a un elenco collegato singolarmente). L'unico posto nel tradizionale algoritmo di ordinamento rapido che dipende dal requisito di accesso casuale è la fase di configurazione che utilizza qualcosa di "difficile" per selezionare l'elemento di pivot. In realtà tutti questi "trucchi" non sono altro che una semplice euristica che può essere sostituita con metodi sequenziali praticamente altrettanto efficaci.

Ho implementato l'ordinamento rapido per le liste collegate prima. Non c'è niente di speciale in questo, devi solo prestare molta attenzione al corretto ricollegamento dell'elemento. Come probabilmente comprenderete, gran parte del valore degli algoritmi di ordinamento delle liste deriva dal fatto che è possibile riordinare gli elementi tramite ricollegando, invece di scambio di valori esplicito. Non solo potrebbe essere più veloce, ma anche (e spesso - più importante) preserva la validità valoriale dei riferimenti esterni che potrebbero essere allegati agli elementi della lista.

P.S. Tuttavia, direi che per gli elenchi concatenati l'algoritmo di merge sort sortisce un'implementazione molto più elegante, che ha prestazioni altrettanto buone (a meno che non si abbia a che fare con alcuni casi che funzionano meglio con l'ordinamento rapido in modo specifico).