Qual è la differenza tra Quicksort e Unisci Ordina

Il differenza principale tra quicksort e merge sort è che il quicksort ordina gli elementi confrontando ciascun elemento con un elemento chiamato pivot mentre l'unione di ordinamento divide l'array in due sottoarray ancora e ancora finché non viene lasciato un elemento.

L'ordinamento è il metodo per organizzare i dati in un ordine particolare. Quando si organizzano i dati, è possibile considerare l'ordine numerico o lessicografico. L'ordinamento aiuta a cercare e ad accedere agli elementi dei dati più velocemente e più rapidamente. Ci sono vari algoritmi di ordinamento e quicksort e merge sort sono due di questi.

Aree chiave coperte

1. Cos'è Quicksort
     - Definizione, Funzionalità
2. Cos'è l'ordine di unione
     - Definizione, Funzionalità
3. Qual è la differenza tra Quicksort e Unisci Ordina
     - Confronto tra le principali differenze

Parole chiave

Algoritmo, Matrice, Unisci Ordina, Quicksort

Cos'è Quicksort

Quicksort è un algoritmo interno che utilizza la "tecnica divide et impera". È anche chiamato una sorta di scambio di partizioni. Usa un elemento chiave chiamato pivot per confrontare e partizionare gli elementi dell'array. Gli elementi con un valore inferiore rispetto al pivot si posizionano sul lato sinistro del pivot mentre gli elementi con un valore maggiore del pivot si spostano sul lato destro del pivot. La sezione sinistra è chiamata la partizione sinistra e la sezione destra è chiamata la partizione corretta.

Figura 1: Quicksort

Fare riferimento all'esempio seguente.

36 34 43 11 15 20 28 45 27 32

Considerare 32 come il perno e considerare 36 e 27. Le condizioni 36 < pivot, 27 > il perno è falso Pertanto, possiamo scambiare questi due valori. Ora la lista è la seguente.

27 34 43 11 15 20 28 45 36 32

Considera i valori 34 e 45. Se si considera 34 < pivot, the condition is false. Similarly, 45 > la condizione di pivot è vera. Ora possiamo passare da 45 a 28. Consideriamo il 34 e il 28. 34 < pivot is false and 28 > pivot è falso. Pertanto, possiamo scambiare 34 e 28.

27 28 43 11 15 20 34 45 36 32

Considerare 43 e 20. 43 < pivot is false. 20 > pivot è falso. Pertanto, possiamo scambiare i due numeri. Ora la lista è la seguente.

27 28 20 11 15 43 34 45 36 32

Consideriamo ora l'11 e il 15. 11 < pivot is true. We can consider 15. It is less than 32. It is the overlapping point, and we can place 32 as follows.

27 28 20 11 15 32 43 34 45 36 

Ora i numeri sul lato sinistro del perno sono più piccoli del perno e il lato destro del perno è maggiore del perno. Possiamo applicare quicksort alle partizioni sinistra e destra per ordinare l'intero elenco.

Cos'è l'ordine di unione

Unisci ordinamento è un algoritmo esterno che utilizza la "tecnica divide et impera". Divide l'array in due sezioni. Ordina ogni array e li combina insieme per formare l'array ordinato. L'ordinamento unione richiede ulteriore spazio di archiviazione per ordinare l'array ausiliario.

Considera il seguente esempio.

Figura 2: Unisci Ordina

Possiamo dividere l'array in due sezioni. Ora ci sono due array come segue.

38 27 43 3 9 82 10

Considerate 38 27 43 3. Possiamo dividerlo nuovamente in due array. Sono 38 27 e 43 3. 38 27 si divide in 38 e 27 mentre 43 3 si divide in 43 e 3. L'ordinamento 38 e 27 dà 27 38. L'ordinamento 43 3 dà 3 43. Ora è possibile combinare 27 38 e 3 43 Dopo averli ordinati, otteniamo un array come 3 27 38 43. 

Allo stesso modo, consideriamo 9 82 10. Possiamo dividerlo nuovamente in due array. Sono 9 82 e 10. 9 82 divide in 9 e 82. Inoltre, vi è il numero 10 nell'altra matrice. 9 e 82 ordinano come 9 82. Quindi, questa matrice e matrice con valore 10 combina e fornisce 9 10 e 82.

Infine, 3 27 38 43 e 9 10 82 si combinano per fornire l'array ordinato.

Differenza tra Quicksort e Merge Sort

Definizione

Quicksort è un efficiente algoritmo di ordinamento, che funge da metodo sistematico per posizionare gli elementi di un array in ordine. Al contrario, merge sort è un efficiente, per tutti gli scopi, algoritmi di ordinamento basati sul confronto. Quindi, questa è la differenza fondamentale tra quicksort e merge sort.

Funzionalità

In primo luogo, la funzionalità è la principale differenza tra quicksort e merge sort. Quicksort ordina gli elementi confrontando ogni elemento con il pivot mentre l'unione di ordinamento divide l'array in due subarray (n / 2) ancora e ancora finché non viene lasciato un elemento.

Applicazione

Inoltre, mentre quicksort è adatto per piccoli array, unisci lavori di ordinamento per qualsiasi tipo di array.

Velocità

Un'altra differenza tra quicksort e merge sort è che quicksort funziona più velocemente per i piccoli set di dati mentre l'unisci sort funziona a velocità costante per tutti i set di dati.

Spazio richiesto

Inoltre, lo spazio richiesto è anche una differenza importante tra quicksort e merge sort. Quicksort richiede uno spazio minimo rispetto all'unione di fusione.  

Efficienza

Inoltre, quicksort non è efficiente per gli array di grandi dimensioni, ma l'unisci sort è più efficiente di quicksort. Quindi, questa è un'altra differenza tra quicksort e merge sort.

Conclusione

In sintesi, la differenza principale tra quicksort e merge sort è che il quicksort ordina gli elementi confrontando ciascun elemento con un elemento chiamato pivot mentre l'ordinamento di merge divide l'array in due sottoarray ancora e ancora fino a quando non viene lasciato un elemento.

Riferimento:

1. Algoritmo Quicksort | Parte 2, Education 4u, 15 marzo 2018, disponibile qui.
2. Unisci Ordina Esempio, Istruzione 4u, 15 marzo 2018, disponibile qui.

Cortesia dell'immagine:

1. "Quicksort-diagram" di Znupi - Opera propria (dominio pubblico) tramite Commons Wikimedia
2. "Unisci algoritmo di ordinamento" di Vineet Kumar di Wikipedia in inglese - Trasferito da en.wikipedia a Commons di Eric Bauman utilizzando CommonsHelper (dominio pubblico) tramite Commons Wikimedia