Perché il mergesort è considerato "la strada da percorrere" quando si ordinano gli elenchi e non Quicksort? Ho sentito questo in una conferenza che ho visto online e l'ho visto in un paio di siti web.Perché il mergesort è migliore per gli elenchi collegati?
Una delle principali fonti di efficienza in quicksort è locality of reference, in cui l'hardware del computer è ottimizzato in modo che l'accesso alle posizioni di memoria vicine sia tendenzialmente più rapido dell'accesso alle posizioni di memoria sparse nella memoria. La fase di partizionamento in quicksort ha in genere una località eccellente, poiché accede a elementi di array consecutivi vicino al fronte e al retro. Di conseguenza, quicksort tende a funzionare molto meglio di altri algoritmi di ordinamento come heapsort anche se spesso ha all'incirca lo stesso numero di confronti e swap, poiché nel caso di heapsort gli accessi sono più dispersi.
Inoltre, quicksort è in genere molto più veloce di altri algoritmi di ordinamento perché funziona sul posto, senza la necessità di creare alcun array ausiliario per contenere valori temporanei. Rispetto a qualcosa come merge sort, questo può essere un enorme vantaggio perché il tempo richiesto per allocare e deallocare gli array ausiliari può essere notevole. Il funzionamento sul posto migliora anche la località di Quicksort.
Quando si lavora con elenchi collegati, nessuno di questi vantaggi si applica necessariamente. Poiché le celle di elenco collegate sono spesso disperse nella memoria, non vi è alcun bonus di località per accedere alle celle adiacenti delle liste collegate. Di conseguenza, uno degli enormi vantaggi prestazionali di quicksort viene consumato. Allo stesso modo, i vantaggi del working in place non si applicano più, poiché l'algoritmo dell'elenco collegato di merge sort non ha bisogno di spazio di memoria ausiliaria aggiuntivo.
Detto questo, quicksort è ancora molto veloce nelle liste collegate. Unisci ordinamento tende a essere più veloce perché divide in modo più uniforme gli elenchi a metà e fa meno lavoro per iterazione per eseguire un'unione rispetto al passaggio di partizionamento.
Spero che questo aiuti!
Nell'ultima riga del 3 ° paragrafo hai scritto "Allo stesso modo, i vantaggi del working in place non si applicano più, poiché l'algoritmo dell'elenco collegato di merge sort non ha bisogno di spazio di memoria ausiliaria aggiuntivo.". Perché non ha bisogno dello spazio di archiviazione ausiliario? – Geek
@Geek Probabilmente avrei dovuto dire "l'algoritmo della lista collegata di merge sort non ha bisogno di ** O (n) ** spazio di memoria ausiliaria". L'algoritmo di unione standard basato su array richiede di allocare spazio di archiviazione aggiuntivo nel corso di un'unione perché gli elementi devono essere spostati. Nell'ordinamento delle unioni con elenchi concatenati, è possibile spostare elementi senza allocare un array esterno semplicemente ricollegandoli. – templatetypedef
Il costo di find() è più dannoso per quicksort di mergesort.
L'ordinamento di unione esegue più operazioni "a corto raggio" sui dati, rendendolo più adatto per le liste collegate, mentre quicksort funziona meglio con la struttura di dati ad accesso casuale.
Cosa intendi con 'find()'? – templatetypedef
Ricerca di voci nella struttura dati. Per una linea collegata si sta sempre avanzando/riavvolgendo, come la riproduzione di un nastro. –
Non è necessario utilizzare la funzione di partizione ad accesso casuale utilizzata sugli array per quicksort nel caso dell'elenco collegato. È possibile suddividere l'elenco collegato eseguendo un iterazione attraverso l'elenco e distribuendo ciascun elemento in uno dei tre elenchi: un elenco "minore di", un elenco "maggiore di" e un "elenco uguale", quindi ricorrendo agli ultimi due. Hai ragione che la partizione standard è lenta, ma questo non rende intrinsecamente lento il quicksort della lista collegata. – templatetypedef
Verificare questo http://stackoverflow.com/questions/497794/quicksort-slower-than-mergesort –