Quando l'ordinamento unione è preferito su Ordinamento rapido?

Question

L'ordinamento rapido è molto meglio dell'ordinamento di unione in molti casi. Tuttavia, quando sono i casi in cui unire l'ordinamento potrebbe essere una soluzione migliore rispetto all'ordinamento rapido?

Ad esempio, l'ordinamento di unione funziona meglio di un ordinamento rapido quando i dati non possono essere caricati in memoria contemporaneamente. Ci sono altri casi?

MODIFICA: Risposte all'elenco di domande duplicate suggerito tutti i vantaggi dell'ordinamento rapido sull'ordinamento di unione. Sto chiedendo qui i possibili casi e le applicazioni che utilizzando l'unione di ordinamento in sarebbe vantaggioso rispetto all'utilizzo di ordinamento rapido.

Answer 1

Probabilmente dovrei iniziare dicendo che sia quicksort che mergesort possono funzionare bene se non è possibile inserire tutto in memoria contemporaneamente. È possibile implementare quicksort scegliendo un pivot, quindi trasferendo gli elementi dal disco in memoria e scrivendo gli elementi in uno di due file diversi in base a come tale elemento si confronta con il pivot. Se si utilizza una coda con priorità doppia, è possibile farlo in modo ancora più efficiente inserendo il numero massimo di elementi possibili nella memoria contemporaneamente.

Altri hanno menzionato il vantaggio che il mergesort è il caso peggiore O (n log n), che è sicuramente vero. Detto questo, puoi facilmente modificare quicksort per produrre l'algoritmo introsort, un ibrido tra quicksort, insertion sort e heapsort, che è il caso peggiore O (n log n) ma mantiene la velocità di quicksort nella maggior parte dei casi.

Potrebbe essere utile capire perché quicksort è in genere più veloce di un mergesort, poiché se si comprendono i motivi è possibile trovare rapidamente alcuni casi in cui il mergesort è un chiaro vincitore. Quicksort solito è meglio che mergesort per due ragioni:

1. Quicksort ha una migliore frazione di riferimento rispetto Mergesort, il che significa che gli accessi effettuati in quicksort sono di solito più veloce rispetto ai corrispondenti accessi in mergesort.

2. Quicksort utilizza la peggiore memoria O (log n) (se implementata correttamente), mentre mergesort richiede O (n) memoria a causa del sovraccarico di fusione.

C'è uno scenario, però, dove questi vantaggi scompaiono. Supponiamo di voler ordinare un elenco di elementi collegati. Gli elementi della lista collegata sono sparsi per tutta la memoria, quindi il vantaggio (1) scompare (non esiste una località di riferimento). In secondo luogo, le liste collegate possono essere unite con solo overhead di spazio O (1) invece di overhead di spazio O (n), quindi il vantaggio (2) scompare. Di conseguenza, di solito scoprirai che il mergesort è un algoritmo superiore per l'ordinamento di liste concatenate, poiché fa meno confronti totali e non è suscettibile di una scarsa scelta di pivot.

Spero che questo aiuti!

Answer 2

Quicksort è nel caso medio O (n log n), ma ha il peggior caso di O (n^2). Mergesort è sempre O (n log n). Oltre al caso peggiore asintotico e al carico di memoria del mergesort, non riesco a pensare ad un altro motivo.

Scenari quando il Quicksort è peggio di mergesort:

1. array è già ordinato.
2. Tutti gli elementi nella matrice sono uguali.
3. L'array è ordinato nell'ordine inverso.

Prendere mergesort su quicksort se non si sa nulla dei dati.

Answer 3

merge sort ha un limite superiore garantito di O (N log N). L'ordinamento rapido ha anche questo limite, ma è molto più alto: è O (N). Quando hai bisogno di un limite superiore garantito per la tempistica del tuo codice, usa l'ordinamento di merge su un ordinamento rapido.

Ad esempio, se si scrive codice per un sistema in tempo reale che si basa sull'ordinamento, l'unione di ordinamento sarebbe una scelta migliore.

Answer 4

Un singolo vantaggio più importante di unire l'ordinamento su un ordinamento rapido è la sua stabilità: gli elementi confrontati uguali mantengono l'ordine originale.

Answer 5

1. MergeSort è stabile in base alla progettazione, gli elementi uguali mantengono il loro ordine originale.
2. MergeSort è adatto per l'implementazione parallela (multithreading).
3. MergeSort utilizza (circa il 30%) meno confronti di QuickSort. Questo è un vantaggio spesso trascurato, perché un confronto può essere piuttosto costoso (ad esempio quando si confrontano diversi campi di righe del database).

Answer 6

1. merge sort peggiore caso la complessità è O (nlogn), mentre Breve caso Ordina peggiore è O (n^2).
2. Merge Sort è un ordinamento stabile che significa che lo stesso elemento in un array mantiene le rispettive posizioni originali l'uno rispetto all'altro.