Care este diferența dintre Quicksort și Merge Sort
Share
principala diferență între sortarea rapidă și îmbinarea este aceea că rapidsort sortează elementele prin compararea fiecărui element cu un element numit pivot, în timp ce sortarea îmbinării împarte matricea în două subarraje din nou și din nou până când rămâne un element.
Sortarea este metoda de aranjare a datelor într-o anumită ordine. La aranjarea datelor, este posibil să se ia în considerare ordinea numerică sau lexicografică. Sortarea ajută la căutarea și accesarea elementelor de date mai rapid și mai rapid. Există diverse algoritmi de sortare și rapid și sortare sunt două dintre ele.
Domenii cheie acoperite
1. Ce este Quicksort
- Definiție, funcționalitate
2. Ce este Merge Sort
- Definiție, funcționalitate
3. Care este diferența dintre Quicksort și Merge Sort
- Compararea diferențelor cheie
Termeni cheie
Algoritm, Array, Merge Sort, Quicksort
Ce este Quicksort
Quicksort este un algoritm intern care folosește tehnica de divizare și cucerire. Este, de asemenea, numit un fel de schimb de partiții. Utilizează un element cheie numit pivot pentru compararea și partiționarea elementelor din matrice. Elementele cu o valoare mai mică decât pivotul merg în partea stângă a pivotului, în timp ce elementele cu o valoare mai mare decât pivotul merg în partea dreaptă a pivotului. Secțiunea din stânga este denumită partiția din stânga, iar secțiunea din dreapta este denumită partiția corectă.
Figura 1: Quicksort
Consultați exemplul de mai jos.
36 34 43 11 15 20 28 45 27 32
Considerați 32 ca pivot și luați în considerare 36 și 27. Condițiile 36 < pivot, 27 > pivot sunt false. Prin urmare, putem schimba aceste două valori. Acum lista este după cum urmează.
27 34 43 11 15 20 28 45 36 32
Luați în considerare valorile 34 și 45. Când luați în considerare 34 < pivot, the condition is false. Similarly, 45 > pivot condiția este adevărată. Acum, putem trece de la 45 la 28. Să luăm în considerare 34 și 28. 34 < pivot is false and 28 > pivot este fals. Prin urmare, putem schimba 34 și 28.
27 28 43 11 15 20 34 45 36 32
Luați în considerare 43 și 20. 43 < pivot is false. 20 > pivot este fals. Prin urmare, putem schimba cele două numere. Acum lista este după cum urmează.
27 28 20 11 15 43 34 45 36 32
Acum ia în considerare 11 și 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
Acum numerele din partea stângă a pivotului sunt mai mici decât pivotul, iar partea dreaptă a pivotului este mai mare decât pivotul. Putem aplica rapid sortarea partițiilor din stânga și dreapta pentru a sorta întreaga listă.
Ce este Merge Sort
Merge sort este un algoritm extern care folosește tehnica "divide și conquer". Se împarte matricea în două secțiuni. Se sortează fiecare matrice și le combină pentru a forma matricea sortată. Merge sortarea necesită un spațiu de stocare suplimentar pentru a sorta matricea auxiliară.
Luați în considerare următorul exemplu.
Figura 2: Merge Sort
Putem împărți matricea în două secțiuni. Acum există două tablouri după cum urmează.
38 27 43 3 9 82 10
Luați în considerare 38 27 43 3. Îl putem împărți din nou în două mese. Acestea sunt 38 27 și 43 3. 38 27 se împart în 38 și 27, în timp ce 43 3 se împarte în 43 și 3. Sortarea 38 și 27 dă 27 38. Sortarea 43 3 dă 3 43. Acum este posibil să se combine 27 38 și 43 După sortare, obținem o matrice de 3 27 38 43.
În mod similar, ia în considerare 9 82 10. Îi putem împărți din nou în două mese. Acestea sunt 9 82 și 10. 9 82 se împarte în 9 și 82. Mai mult decât atât, există numărul 10 în cealaltă matrice. 9 și 82 sortează ca 9 82. Astfel, această matrice și matrice cu valoarea 10 combină și oferă 9 10 și 82.
În cele din urmă, 3 27 38 43 și 9 10 82 combină pentru a furniza matricea sortată.
Diferența dintre Quicksort și Merge Sort
Definiție
Quicksort este un algoritm eficient de sortare, care servește ca metodă sistematică pentru plasarea în ordine a elementelor unei matrice. În schimb, sortarea fuzionării este un algoritm eficient de sortare, bazat pe comparație, bazat pe comparație. Astfel, aceasta este diferența fundamentală dintre rapid și sortarea.
Funcționalitate
Mai presus de toate, funcționalitatea este principala diferență dintre quicksort și merge. Quicksort sortează elementele prin compararea fiecărui element cu pivotul, în timp ce sortarea îmbinării împarte matricea în două subarraje (n / 2) din nou și din nou până când rămâne un element.
cerere
Deasemenea, în timp ce rapidsortul este potrivit pentru rețele mici, îmbinarea lucrărilor de sortare pentru orice tip de matrice.
Viteză
O alta diferenta intre quicksort si fuziunea este faptul ca quicksort-ul functioneaza mai repede pentru seturi de date mici, in timp ce sortarea merge intr-o viteza consistenta pentru toate seturile de date.
Cerința spațială
Mai mult decât atât, cerința de spațiu este, de asemenea, o diferență importantă între sortarea rapidă și sortarea. Quicksort necesită un spațiu minim în comparație cu tipul de îmbinare.
Eficienţă
În plus, comanda rapidă nu este eficientă pentru rețelele mari, dar tipul de îmbinare este mai eficient decât rapid. Prin urmare, aceasta este o altă diferență între quicksort și fuziune sort.
Concluzie
În concluzie, principala diferență dintre sortarea rapidă și cea de îmbinare este aceea că sortarea rapidă sortează elementele prin compararea fiecărui element cu un element numit pivot în timp ce sortarea de fuziune împarte matricea în două subarraje din nou și din nou până când rămâne un element.
Referinţă:
1. Algoritmul Quicksort Partea 2, Educație 4u, 15 martie 2018, Disponibil aici.
2. Mergeți Exemplul de Sortare, Educație 4u, 15 Mar. 2018, Disponibil aici.
Datorită fotografiei:
1. "Diagrama Quicksort" de Znupi - Lucrare proprie (Domeniul Public) prin Wikimedia Commons
2. "Schimbarea algoritmului de sortare" De Vineet Kumar la Wikipedia engleză - Transferat de la en.wikipedia la Commons de Eric Bauman folosind CommonsHelper (Public Domain) prin Commons Wikimedia
