Contenuto

• Tabella di comparazione
• Definizione di Ordinamento rapido
• Definizione di Merge Sort
• Conclusione

Gli algoritmi di ordinamento rapido e di tipo merge si basano sull'algoritmo divide and conquer che funziona in modo abbastanza simile. La differenza precedente tra l'ordinamento rapido e unisci è che nell'ordinamento rapido l'elemento pivot viene utilizzato per l'ordinamento. D'altra parte, unisci ordinamento non utilizza l'elemento pivot per eseguire l'ordinamento.

Entrambe le tecniche di ordinamento, ordinamento rapido e unione sono costruite 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'unione dell'ordinamento per l'ordinamento di un ampio set di elementi.

1. 1. Tabella di comparazione
   2. Definizione
   3. Differenze chiave
   4. Conclusione

Tabella di comparazione

Base per il confronto	Ordinamento rapido	Unisci ordinamento
Partizionamento degli elementi nell'array	La divisione di un elenco di elementi non è necessariamente divisa a metà.	L'array è sempre diviso a metà (n / 2).
Peggiore complessità del caso	Su2)	O (n registro n)
Funziona bene su	Matrice più piccola	Funziona bene in qualsiasi tipo di array.
Velocità	Più veloce di altri algoritmi di ordinamento per piccoli set di dati.	Velocità costante in tutti i tipi di set di dati.
Requisiti di spazio di archiviazione aggiuntivi	Di meno	Di Più
Efficienza	Inefficiente per array più grandi.	Più efficiente.
Metodo di ordinamento	Interno	Esterno

Definizione di Ordinamento rapido

Ordinamento rapido è un algoritmo di ordinamento pervasivo in quanto è veloce per gli array brevi. L'insieme degli elementi viene suddiviso in parti ripetutamente fino a quando non è possibile dividerlo ulteriormente. L'ordinamento rapido è anche noto come ordinamento di scambio di partizioni. Utilizza un elemento chiave (noto come pivot) per partizionare gli 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, A, A, …… .., A 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 key = A (1).
2. Il puntatore "basso" è posizionato sul secondo e il puntatore "su" è posizionato sull'ultimo elemento dell'array, ovvero basso = 2 e su = n;
3. Coerentemente, incrementare il puntatore "basso" di una posizione fino a (tasto A>).
4. Costantemente, decrementa il puntatore "su" di una posizione fino a (tasto A <=).
5. Se su è maggiore dell'interscambio basso A con A.
6. Ripetere i passaggi 3,4 e 5 fino a quando la condizione nel passaggio 5 non riesce (ovvero su <= basso), quindi scambiare A 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, l'array viene suddiviso in due sotto-array.
8. La procedura sopra descritta viene ripetutamente applicata 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, ovvero è più veloce di algoritmi come ordinamento a bolle, ordinamento per inserzione e ordinamento per selezione. Tuttavia, è complesso e molto ricorsivo, questo è il motivo per cui non è adatto per array di grandi dimensioni.

Definizione di Merge Sort

Unisci ordinamento è un algoritmo esterno che si basa anche sulla strategia di divisione e conquista. Gli elementi vengono suddivisi in sotto-array (n / 2) più e più volte fino a quando rimane solo un elemento, il che riduce significativamente il tempo di ordinamento. Utilizza memoria aggiuntiva per la memorizzazione dell'array ausiliario. Unisci ordinamento utilizza tre array in cui due vengono utilizzati per la memorizzazione di ogni metà e il terzo viene utilizzato per memorizzare l'elenco ordinato finale. Ogni array viene quindi ordinato in modo ricorsivo. Alla fine, i sottoarray vengono uniti per renderlo n dimensione degli elementi dell'array. L'elenco è sempre diviso in metà (n / 2) dissimile dall'ordinamento rapido.

Sia A la matrice di n numero di elementi da ordinare A, A, ………, A. L'ordinamento di unione segue i passaggi indicati.

1. Dividere l'array A in circa 2 array secondari ordinati per 2, il che significa che gli elementi nei sottoarray (A, A), (A, A), (A, A), (A, A) devono essere in ordine.
2. Combina ciascuna coppia di coppie per ottenere l'elenco dei sottoquarti ordinati di dimensione 4; anche gli elementi nei sottoarrays sono in ordine, (A, A, A, A), ……, (A, A, A, A), ……. (A, A, A, A).
3. Il passaggio 2 viene ripetutamente eseguito fino a quando esiste un solo array ordinato di dimensioni n.

   

Vantaggi e svantaggi

L'algoritmo di ordinamento unione funziona esattamente nello stesso modo e preciso indipendentemente dal numero di elementi coinvolti nell'ordinamento. Funziona bene anche con un set di dati di grandi dimensioni. Tuttavia, consuma gran parte della memoria.

1. Nell'ordinamento di tipo merge, l'array deve essere diviso in sole due metà (ovvero n / 2). Al contrario, in rapido ordine, non vi è alcuna costrizione a dividere l'elenco in elementi uguali.
2. La complessità del caso peggiore dell'ordinamento rapido è O (n²) in quanto richiede molti più confronti nelle peggiori condizioni. Al contrario, unire l'ordinamento presenta lo stesso caso peggiore e complessità del caso medio, ovvero O (n log n).
3. Unisci ordinamento 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 set di dati di grandi dimensioni.
4. L'ordinamento rapido è più veloce rispetto all'unione dell'ordinamento in alcuni casi, ad esempio per piccoli set di dati.
5. Unisci ordinamento richiede spazio di memoria aggiuntivo per memorizzare gli array ausiliari. D'altro canto, l'ordinamento rapido non richiede molto spazio per ulteriore spazio di archiviazione.
6. Unire l'ordinamento è più efficiente dell'ordinamento rapido.
7. L'ordinamento rapido è un metodo di ordinamento interno in cui i dati da ordinare vengono regolati contemporaneamente nella memoria principale. Al contrario, l'ordinamento di tipo merge è un metodo di ordinamento esterno in cui i dati da ordinare non possono essere sistemati contemporaneamente nella memoria e alcuni devono essere conservati nella memoria ausiliaria.

Conclusione

L'ordinamento rapido è casi più veloci, ma è inefficiente in alcune situazioni ed esegue anche molti confronti rispetto all'unione ordinamento. Sebbene l'ordinamento unificato richieda un confronto minore, richiede uno spazio di memoria aggiuntivo di 0 (n) per memorizzare l'array aggiuntivo, mentre l'ordinamento rapido richiede spazio di O (log n).