Conţinut

• Diagramă de comparație
• Definiția Quick Sort
• Definiția Merge Sort
• Concluzie

Algoritmii de sortare rapidă și sortare se bazează pe algoritmul de împărțire și cucerire care funcționează într-un mod destul de similar. Diferența anterioară dintre sortarea rapidă și cea combinată este că în sortare rapidă elementul pivot este utilizat pentru sortare. Pe de altă parte, sortarea combinată nu folosește elementul pivot pentru a efectua sortarea.

Ambele tehnici de sortare, sortare rapidă și sortare de îmbinare sunt construite pe metoda de împărțire și cucerire în care setul de elemente este împărțit și apoi combinat după reamenajare. Sortarea rapidă necesită, de obicei, mai multe comparații decât combinarea sortării pentru sortarea unui set mare de elemente.

1. 1. Diagramă de comparație
   2. Definiție
   3. Diferențele cheie
   4. Concluzie

Diagramă de comparație

Baza de comparație	Sortare rapida	Unire de fel
Partiționarea elementelor din tablou	Divizarea unei liste de elemente nu este neapărat împărțită în jumătate.	Array-ul este întotdeauna împărțit în jumătate (n / 2).
Complexitatea cea mai rea	Pe2)	O (n log n)
Funcționează bine	Matricea mai mică	Funcționează bine în orice tip de tablou.
Viteză	Mai rapid decât alți algoritmi de sortare pentru setul de date mici.	Viteza consecventă în toate tipurile de seturi de date.
Necesar suplimentar de spațiu de stocare	Mai puțin	Mai Mult
Eficienţă	Neeficient pentru tablele mai mari.	Mai eficient.
Metoda de sortare	Intern	Extern

Definiția Quick Sort

Sortare rapida este folosit pervasiv algoritmul de sortare, deoarece este rapid pentru tablourile scurte. Ansamblul elementelor este împărțit în părți în mod repetat, până când nu este posibil să îl împărțiți în continuare. Sortul rapid este cunoscut și sub numele de sortare de schimb de partiții. Folosește un element cheie (cunoscut sub numele de pivot) pentru împărțirea elementelor. O partiție conține acele elemente care sunt mai mici decât elementul cheie. O altă partiție conține acele elemente care sunt mai mari decât elementul cheie. Elementele sunt sortate recursiv.

Să presupunem că A este un tablou A, A, A, …… .., A de n număr care trebuie sortate. Algoritmul de sortare rapidă cuprinde următoarele etape.

1. Primul element sau orice element aleatoriu selectat ca cheie, presupune cheia = A (1).
2. Indicatorul „scăzut” este plasat la al doilea și indicatorul „sus” este poziționat la ultimul element al tabloului, adică low = 2 și sus = n;
3. În mod constant, creșteți indicatorul „scăzut” cu o poziție până la tasta (A>).
4. Declanșează constant indicatorul „sus” cu o poziție până la (tasta A <=).
5. Dacă în sus este mai mare decât un schimb mic A cu A.
6. Repetați pasul 3,4 și 5 până când starea de la pasul 5 nu reușește (adică sus = = scăzut) apoi schimbă A cu tasta.
7. Dacă elementele din stânga cheii sunt mai mici decât tasta și elementele din dreapta tastei sunt mai mari decât cheia, atunci tabloul este împărțit în două sub-tablouri.
8. Procedura de mai sus este aplicată în mod repetat la subordonări până la sortarea întregului tablou.

   

   
   

Avantaje și dezavantaje

Are un comportament mediu bun. Complexitatea timpului de rulare a sortării rapide este bună, deoarece este mai rapid decât algoritmii, cum ar fi sortarea cu bule, sortarea inserțiilor și sortarea selecției. Cu toate acestea, este complex și foarte recursiv, acesta este motivul pentru care nu este potrivit pentru tablele mari.

Definiția Merge Sort

Unire de fel este un algoritm extern care se bazează și pe strategia de împărțire și cucerire. Elementele sunt împărțite în sub-matrice (n / 2) din nou și din nou până când rămâne doar un element, ceea ce reduce semnificativ timpul de sortare. Utilizează stocare suplimentară pentru stocarea tabloului auxiliar. Sortarea Merge folosește trei tablouri în care două sunt utilizate pentru stocarea fiecărei jumătăți, iar cel de-al treilea este folosit pentru a stoca lista finală sortată. Fiecare tablă este apoi sortată recursiv. În cele din urmă, subordonările sunt contopite pentru a face din n dimensiunea elementului tabloului. Lista este întotdeauna împărțită în doar jumătate (n / 2) diferită de sortarea rapidă.

Fie A o serie de n număr de elemente care urmează să fie sortate A, A, ..........., A. Sortarea urmează pașii dat.

1. Împărțiți tabloul A în aproximativ n / 2 sub-tablă sortată la 2, ceea ce înseamnă că elementele din sub-tablele (A, A), (A, A), (A, A), (A, A) trebuie să fii în ordine ordonată.
2. Combinați fiecare pereche de perechi pentru a obține lista subordonărilor sortate de dimensiunea 4; elementele din subarraje sunt de asemenea ordonate, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Etapa 2 este efectuată în mod repetat până când există o singură tablă sortată cu dimensiunea n.

   

Avantaje și dezavantaje

Algoritmul de sortare a fuziunii se realizează în mod exact și exact indiferent de numărul de elemente implicate în sortare. Funcționează bine chiar și cu setul mare de date. Cu toate acestea, consumă o parte mai mare a memoriei.

1. În sortarea de îmbinare, tabloul trebuie împărțit în doar două jumătăți (adică n / 2). Spre deosebire, în mod rapid, nu există nicio constrângere a divizării listei în elemente egale.
2. Cea mai gravă complexitate a cazurilor rapide este O (n²) deoarece este nevoie de mult mai multe comparații în cele mai proaste condiții. Dimpotrivă, sortarea de îmbinare are aceleași complexități dintre cazurile cele mai rele și media, adică O (n log n).
3. Sortarea Merge poate funcționa bine pe orice tip de set de date, fie că este mare sau mică. Dimpotrivă, sortarea rapidă nu poate funcționa bine cu seturi de date mari.
4. Sortarea rapidă este mai rapidă decât sortarea fuziunii în unele cazuri, cum ar fi pentru seturile de date mici.
5. Sortarea Merge necesită spațiu suplimentar de memorie pentru a stoca tablourile auxiliare. Pe de altă parte, sortarea rapidă nu necesită mult spațiu pentru depozitare suplimentară.
6. Sortarea Merge este mai eficientă decât cea rapidă.
7. Sortarea rapidă este o metodă de sortare internă în care datele care urmează să fie sortate sunt ajustate la un moment dat în memoria principală. În schimb, sortarea de îmbinare este o metodă de sortare externă în care datele care urmează să fie sortate nu pot fi adăpostite în memorie în același timp, iar unele trebuie păstrate în memoria auxiliară.

Concluzie

Sortarea rapidă este mai rapidă, dar este ineficientă în unele situații și, de asemenea, realizează o mulțime de comparații în comparație cu sortarea fuziunii. Deși sortarea combinării necesită o comparație mai mică, este nevoie de un spațiu suplimentar de memorie de 0 (n) pentru stocarea tabloului suplimentar, în timp ce sortarea rapidă are nevoie de spațiu de O (log n).