ORDINAMENTO RAPIDO E ORDINAMENTO UNITO

Ordinamento rapido è un algoritmo interno basato sulla strategia divide et impera. In questo:

L'array di elementi viene diviso ripetutamente in parti fino a quando non è più possibile dividerlo ulteriormente.
È anche noto come ordinamento dello scambio di partizioni .
Utilizza un elemento chiave (pivot) per partizionare gli elementi.
Una partizione di sinistra contiene tutti quegli elementi che sono più piccoli del pivot e una partizione di destra contiene tutti quegli elementi che sono più grandi dell'elemento chiave.

Quicksort Unisci ordinamento è un algoritmo esterno e basato sulla strategia divide et impera. In questo:

Gli elementi vengono divisi ripetutamente in due sotto-array (n/2) finché non rimane un solo elemento.
L'ordinamento di unione utilizza spazio di archiviazione aggiuntivo per l'ordinamento dell'array ausiliario.
L'ordinamento di unione utilizza tre array di cui due vengono utilizzati per archiviare ciascuna metà e il terzo esterno viene utilizzato per archiviare l'elenco ordinato finale unendo altri due e ciascun array viene quindi ordinato in modo ricorsivo.
Alla fine, tutti i sottoarray vengono uniti per creare una dimensione di elemento 'n' dell'array.

Tutorial su unione-ordinamento

Partizione degli elementi nell'array: nel merge sort, l'array è diviso in sole 2 metà (ovvero n/2). mentre in caso di ordinamento rapido, l'array viene suddiviso in qualsiasi rapporto. Non vi è alcuna costrizione a dividere la serie di elementi in parti uguali nell'ordinamento rapido. Complessità del caso peggiore: la complessità del caso peggiore dell'ordinamento rapido è O(n^2) poiché sono necessari molti confronti nella condizione peggiore. mentre nel merge sort, il caso peggiore e il caso medio hanno le stesse complessità O(n log n). Utilizzo con set di dati: l'ordinamento di unione può funzionare bene su qualsiasi tipo di set di dati indipendentemente dalle sue dimensioni (grandi o piccole). mentre l'ordinamento rapido non può funzionare bene con set di dati di grandi dimensioni. Requisiti di spazio di archiviazione aggiuntivo: l'ordinamento di unione non è attivo perché richiede spazio di memoria aggiuntivo per archiviare gli array ausiliari. mentre l'ordinamento rapido è attivo in quanto non richiede spazio di archiviazione aggiuntivo. Efficienza: l'ordinamento di unione è più efficiente e funziona più velocemente dell'ordinamento rapido in caso di dimensioni di array o set di dati maggiori. mentre l'ordinamento rapido è più efficiente e funziona più velocemente dell'ordinamento mediante unione in caso di dimensioni di array o set di dati inferiori. Metodo di ordinamento: L'ordinamento rapido è un metodo di ordinamento interno in cui i dati vengono ordinati nella memoria principale. mentre il merge sort è un metodo di ordinamento esterno in cui i dati da ordinare non possono essere ospitati nella memoria e necessitano di memoria ausiliaria per l'ordinamento. Stabilità: l'ordinamento di unione è stabile poiché due elementi con lo stesso valore appaiono nello stesso ordine nell'output ordinato come lo erano nell'array non ordinato di input. mentre l'ordinamento rapido è instabile in questo scenario. Ma può essere reso stabile utilizzando alcune modifiche al codice. Preferito per: l'ordinamento rapido è preferito per gli array. mentre l'ordinamento Unisci è preferito per gli elenchi collegati. Località di riferimento: Quicksort mostra una buona località della cache e questo rende Quicksort più veloce del merge sort (in molti casi come nell'ambiente di memoria virtuale).

Base per il confronto	Ordinamento rapido	Unisci ordinamento
La partizione degli elementi nell'array	La suddivisione di una serie di elementi avviene in qualsiasi rapporto, non necessariamente divisa a metà.	Nel merge sort, l'array è diviso solo in 2 metà (cioè n/2).
Complessità del caso peggiore	O(n^2)	O(logn)
Funziona bene	Funziona bene su array più piccoli	Funziona bene su qualsiasi dimensione di array
Velocità di esecuzione	Funziona più velocemente di altri algoritmi di ordinamento per set di dati di piccole dimensioni come l'ordinamento di selezione ecc	Ha una velocità costante su dati di qualsiasi dimensione
Requisiti di spazio di archiviazione aggiuntivi	Meno (sul posto)	Altro (non sul posto)
Efficienza	Inefficiente per array più grandi	Più efficiente
Metodo di ordinamento	Interno	Esterno
Stabilità	Non stabile	Stabile
Preferito per	per gli array	per elenchi collegati

Località di riferimento	Bene	povero
Lavoro importante	Il lavoro principale è partizionare l'array in due sottoarray prima di ordinarli ricorsivamente.	Il lavoro principale è combinare i due sottoarray dopo averli ordinati in modo ricorsivo.
Divisione dell'array	La divisione di un array in sotto-array può essere bilanciata o meno poiché l'array è partizionato attorno al perno.	La divisione di un array in sottoarray è sempre equilibrata poiché divide l'array esattamente a metà.
Metodo	L'ordinamento rapido è un metodo di ordinamento sul posto.	L'ordinamento di unione non è un metodo di ordinamento sul posto.
Fusione	Quicksort non necessita della fusione esplicita dei sottoarray ordinati; piuttosto i sottoarray sono stati riorganizzati correttamente durante il partizionamento.	Merge sort esegue l'unione esplicita di sottoarray ordinati.
Spazio	Quicksort non richiede spazio aggiuntivo nell'array.	Per l'unione di sottoarray ordinati, è necessario un array temporaneo con dimensioni pari al numero di elementi di input.