Differenza tra Ordina veloce e Ordina unisci

• 2019

Gli algoritmi di ordinamento e unione rapida sono basati sull'algoritmo divide and conquer che funziona in modo abbastanza simile. La differenza precedente tra l'ordinamento rapido e l'unione è che nell'ordinamento rapido l'elemento di pivot viene utilizzato per l'ordinamento. D'altra parte, unire l'ordinamento non usa l'elemento pivot per eseguire l'ordinamento.

Entrambe le tecniche di ordinamento, l'ordinamento rapido e l'ordinamento di unione sono basate sul metodo divide and conquer in cui l'insieme di elementi viene diviso e quindi combinato dopo il riarrangiamento. L'ordinamento rapido di solito richiede più confronti rispetto all'ordinamento di unione per l'ordinamento di un grande insieme di elementi.

Grafico comparativo

Base per il confronto	Ordinamento rapido	Unisci ordinamento
Partizionamento degli elementi nella matrice	La suddivisione di un elenco di elementi non è necessariamente divisa in metà.	La matrice è sempre divisa in metà (n / 2).
Peggiore complessità del caso	O (n2)	O (n log n)
Funziona bene	Array più piccolo	Funziona bene in qualsiasi tipo di array.
Velocità	Più veloce di altri algoritmi di ordinamento per set di dati di piccole dimensioni.	Velocità costante in tutti i tipi di serie di dati.
Ulteriori requisiti di spazio di archiviazione	Di meno	Di Più
Efficienza	Inefficiente per array più grandi.	Più efficiente.
Metodo di smistamento	Interno	Esterno

Definizione di Ordinamento rapido

L'ordinamento rapido è un algoritmo di ordinamento utilizzato in modo pervasivo in quanto è veloce per gli array corti. L'insieme degli elementi è diviso in parti ripetutamente finché non è possibile dividerlo ulteriormente. L'ordinamento rapido è anche conosciuto come scambio di partizioni . Utilizza un elemento chiave (noto come pivot) per il partizionamento degli elementi. Una partizione contiene quegli elementi che sono più piccoli dell'elemento chiave. Un'altra partizione contiene quegli elementi che sono maggiori dell'elemento chiave. Gli elementi sono ordinati in modo ricorsivo.

Supponiamo che A sia un array A [1], A [2], A [3], ...... .., A [n] di n numero che devono essere ordinati. L'algoritmo di ordinamento rapido comprende i seguenti passaggi.

1. Il primo elemento o qualsiasi elemento casuale selezionato come chiave, assume chiave = A (1).
2. Il puntatore "basso" è posizionato sul secondo e il puntatore "su" è posizionato sull'ultimo elemento dell'array, ovvero basso = 2 e alto = n;
3. Coerentemente, incrementa il puntatore "basso" di una posizione fino al tasto (A [basso]>).
4. Costantemente, decrementa il puntatore "su" di una posizione fino a (A [su] <= tasto).
5. Se è superiore a uno scambio basso A [basso] con A [su].
6. Ripetere i passaggi 3, 4 e 5 fino a quando la condizione del passaggio 5 non riesce (ovvero su <= basso), quindi scambiare A [su] con il tasto.
7. Se gli elementi a sinistra della chiave sono più piccoli della chiave e gli elementi a destra della chiave sono maggiori della chiave, la matrice viene suddivisa in due sottoschemi.
8. La procedura sopra riportata viene applicata ripetutamente ai sottoarray fino a quando l'intero array non viene ordinato.

Vantaggi e svantaggi

Possiede un buon comportamento nel caso medio. La complessità del tempo di esecuzione dell'ordinamento rapido è buona, è più veloce di algoritmi come l'ordinamento di bolle, l'ordinamento di inserimento e l'ordinamento di selezione. Tuttavia, è complesso e molto ricorsivo, e questo è il motivo per cui non è adatto a grandi matrici.

Definizione di Merge Sort

Unisci ordinamento è un algoritmo esterno che si basa anche sulla strategia divide e conquista. Gli elementi vengono suddivisi in matrici secondarie (n / 2) ancora e ancora fino a quando non viene lasciato un solo elemento, il che riduce significativamente il tempo di ordinamento. Usa spazio aggiuntivo per la memorizzazione dell'array ausiliario. Unisci ordina utilizza tre array in cui due vengono utilizzati per la memorizzazione di ciascuna metà e il terzo viene utilizzato per memorizzare l'elenco ordinato finale. Ogni array viene quindi ordinato in modo ricorsivo. Alla fine, i sottoarray sono uniti per renderlo n dimensione dell'elemento dell'array. L'elenco è sempre diviso in solo metà (n / 2) dissimile da ordinamento rapido.

Sia A l'array di n numero di elementi da ordinare A [1], A [2], ........., A [n]. L'ordinamento di fusione segue i passaggi indicati.

1. Dividere l'array A in circa 2 array di sub-ordinati ordinati, il che significa che gli elementi in (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) i sotto-array devono essere ordinati.
2. Combina ogni coppia di coppie per ottenere l'elenco dei sottotitoli ordinati di dimensione 4; anche gli elementi nei sottoarray sono ordinati in ordine (A [1], A [2], A [3], A [4]), ......, (A [k-1], A [k], A [k + 1], A [k + 2]), ......., (A [n-3], A [n-2], A [n-1], A [n]).
3. Il passaggio 2 viene ripetutamente eseguito finché non vi è una sola matrice ordinata di dimensione n.

Vantaggi e svantaggi

L'algoritmo di unisci sort esegue la stessa identica e precisa maniera indipendentemente dal numero di elementi coinvolti nell'ordinamento. Funziona bene anche con il set di dati di grandi dimensioni. Tuttavia, consuma gran parte della memoria.

Differenze chiave tra Ordina veloce e Ordina unisci

1. Nell'ordinamento di unione, l'array deve essere diviso in due sole metà (es. N / 2). Per quanto riguarda, in modo rapido, non vi è alcuna costrizione a dividere la lista in elementi uguali.
2. La complessità del caso peggiore di ordinamento rapido è O (n2) in quanto richiede parecchie comparazioni nella peggiore condizione. Al contrario, l'unisci sort ha lo stesso caso peggiore e la complessità del caso medio, ovvero O (n log n).
3. Unisci sort può funzionare bene su qualsiasi tipo di set di dati, sia esso grande o piccolo. Al contrario, l'ordinamento rapido non può funzionare bene con dataset di grandi dimensioni.
4. L'ordinamento rapido è più veloce dell'ordinamento di fusione in alcuni casi, ad esempio per i piccoli set di dati.
5. L'ordinamento unione richiede spazio di memoria aggiuntivo per memorizzare gli array ausiliari. D'altra parte, l'ordinamento rapido non richiede molto spazio per l'archiviazione extra.
6. Unisci sort è più efficiente di un ordinamento rapido.
7. L'ordinamento rapido è un metodo di ordinamento interno in cui i dati da ordinare vengono regolati alla volta nella memoria principale. Al contrario, l'unire sort è un metodo di ordinamento esterno in cui i dati che devono essere ordinati non possono essere sistemati nella memoria nello stesso momento e alcuni devono essere mantenuti nella memoria ausiliaria.

Conclusione

L'ordinamento rapido è più rapido, ma in alcune situazioni è inefficiente e comporta anche paragoni rispetto all'unione di tipo merge. Sebbene l'unisci merge richiede meno confronti, ha bisogno di uno spazio di memoria aggiuntivo di 0 (n) per memorizzare l'array extra mentre l'ordinamento rapido richiede lo spazio di O (log n).