Merge sort este unul dintre algoritmii de bază în informatică, formulat încă din 1945 de marele matematician John von Neumann. În timp ce participa la Proiectul Manhattan, Neumann s-a confruntat cu nevoia de a procesa eficient cantități uriașe de date. Metoda pe care a dezvoltat-o a folosit principiul „împărți și cuceri”, care a redus semnificativ timpul necesar pentru muncă.
Principiul și utilizarea algoritmului
Metoda de sortare prin îmbinare este utilizată în problemele de sortare a structurilor care au acces ordonat la elemente, cum ar fi matrice, liste, fluxuri.
În timpul procesării, blocul de date inițial este împărțit în componente mici, până la un element, care de fapt este deja o listă sortată. Apoi este reasamblat în ordinea corectă.
Sortarea unei matrice de o anumită lungime necesită o zonă de memorie suplimentară de aceeași dimensiune, în care matricea sortată este colectată în părți.
Metoda poate fi folosită pentru a comanda orice tip de date comparabile, cum ar fi numere sau șiruri.
Imbinare sortatăparcele
Pentru a înțelege algoritmul, să începem analiza lui de la final - de la mecanismul de îmbinare a blocurilor sortate.
Să ne imaginăm că avem două matrice de numere sortate în orice fel care trebuie combinate între ele, astfel încât sortarea să nu fie întreruptă. Pentru simplitate, vom sorta numerele în ordine crescătoare.
Exemplu elementar: ambele matrice constau dintr-un element fiecare.
int arr1={31}; int arr2={18};
Pentru a le îmbina, trebuie să luați elementul zero al primului tablou (nu uitați că numerotarea începe de la zero) și elementul zero al celui de-al doilea tablou. Acestea sunt, respectiv, 31 și, respectiv, 18. În funcție de condiția de sortare, numărul 18 ar trebui să fie primul, deoarece este mai mic. Puneți numerele în ordinea corectă:
int rezultat={18, 31};
Să ne uităm la un exemplu mai complicat, în care fiecare matrice constă din mai multe elemente:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoritmul de îmbinare va consta în compararea secvenţială a elementelor mai mici şi plasarea lor în matricea rezultată în ordinea corectă. Pentru a ține evidența indicilor actuali, să introducem două variabile - index1 și index2. Inițial, le-am setat la zero, deoarece tablourile sunt sortate, iar cele mai mici elemente sunt la început.
int index1=0; int index2=0;
Să scriem întregul proces de fuziune pas cu pas:
- Luați elementul cu index1 din matricea arr1 și elementul cu index2 din matricea arr2.
- Comparați, selectați-l pe cel mai mic dintre ele și introducețimatrice rezultată.
- Incrementează indexul curent al elementului mai mic cu 1.
- Continuați de la primul pas.
Pe prima orbită, situația va arăta astfel:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; rezultat[0]=arr1[0]; // rezultat=[2]
La a doua tură:
index1=1; index2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; rezultat[1]=arr2[0]; // rezultat=[2, 5]
Al treilea:
index1=1; index2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; rezultat[2]=arr2[1]; // rezultat=[2, 5, 6]
Și așa mai departe, până când rezultatul este o matrice complet sortată: {2, 5, 6, 17, 21, 19, 30, 45}.
Pot apărea anumite dificultăți dacă sunt îmbinate matrice cu lungimi diferite. Ce se întâmplă dacă unul dintre indecșii actuali a ajuns la ultimul element și au mai rămas membri în a doua matrice?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 pas index1=0, index2=0; 1 2 rezultat={1, 2}; // 3 trepte index1=1, index2=1; 4 < 5 rezultat={1, 2, 4}; //4 pași index1=2, index2=1 ??
Variabila index1 a atins valoarea 2, dar matricea arr1 nu are un element cu acel index. Totul este simplu aici: doar transferați elementele rămase din a doua matrice în cel rezultat, păstrându-le ordinea.
rezultat={1, 2, 4, 5, 6, 7, 9};
Această situație ne indică nevoiapotriviți indexul de verificare curent cu lungimea matricei care este îmbinată.
Schema de îmbinare pentru secvențe ordonate (A și B) de lungimi diferite:
- Dacă lungimea ambelor secvențe este mai mare de 0, comparați A[0] și B[0] și mutați-o pe cea mai mică în tampon.
- Dacă lungimea uneia dintre secvențe este 0, luați elementele rămase din a doua secvență și, fără a le schimba ordinea, treceți la sfârșitul bufferului.
Implementarea celei de-a doua etape
Un exemplu de unire a două matrice sortate în Java este dat mai jos.
int a1=new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=new int[a1.lungime + a2.lungime]; int i=0, j=0; pentru (int k=0; k a1.lungime-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.lungime-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
Aici:
- a1 și a2 sunt tablourile originale sortate care trebuie îmbinate;
- a3 – matrice finală;
- i și j sunt indicii elementelor curente pentru tablourile a1 și a2.
Primul și al doilea dacă condițiile asigură că indecșii nu depășesc dimensiunea matricei. Al treilea și respectiv al patrulea bloc de condiții sunt mutate în matricea rezultată a elementului mai mic.
Divide and Conquer
Deci, am învățat să îmbinăm cele sortateculegeri de valori. Se poate spune că a doua parte a algoritmului de sortare de îmbinare - îmbinarea în sine - a fost deja sortată.
Totuși, trebuie să înțelegeți cum să treceți de la matricea originală de numere nesortate la mai multe sortate care pot fi îmbinate.
Să luăm în considerare prima etapă a algoritmului și să învățăm cum să separăm matrice.
Acest lucru nu este dificil - lista originală de valori este împărțită în jumătate, apoi fiecare parte este, de asemenea, bifurcată și așa mai departe până când se obțin blocuri foarte mici.
Lungimea unor astfel de elemente minime poate fi egală cu unu, adică pot fi ele însele o matrice sortată, dar aceasta nu este o condiție necesară. Mărimea blocului este determinată în prealabil și orice algoritm de sortare adecvat care funcționează eficient cu matrice de dimensiuni mici (de exemplu, sortare rapidă sau sortare prin inserție) poate fi folosit pentru a-l comanda.
Arată așa.
// matrice originală {34, 95, 10, 2, 102, 70}; // prima împărțire {34, 95, 10} și {2, 102, 70}; // împărțire secundă {34} și {95, 10} și {2} și {102, 70}
Blocurile rezultate, formate din 1-2 elemente, sunt foarte ușor de aranjat.
După aceea, trebuie să îmbinați matricele mici deja sortate în perechi, păstrând ordinea membrilor, ceea ce am învățat deja să facem.
Implementarea primei etape
Partiționarea recursiva a unei matrice este afișată mai jos.
void mergeSort(T a, long start, long finish) { long split; dacă(start < finish) { split=(start + finish)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); merge(a, start, split, finish); } }
Ce se întâmplă în acest cod:
-
Funcția mergeSort primește matricea inițială
a
și marginile din stânga și din dreapta ale regiunii care urmează să fie sortate (indicii încep și
- termină).
-
Dacă lungimea acestei secțiuni este mai mare de unu (
start < finish
), atunci este împărțită în două părți (după indexul
- split), iar fiecare este sortat recursiv.
-
În apelul de funcție recursivă pentru partea stângă, sunt transmise indexul de pornire al diagramei și indexul
split
. Pentru cea dreaptă, respectiv, începutul va fi
- (divizat + 1), iar sfârșitul va fi ultimul index al secțiunii originale.
-
Funcția
merge
primește două secvențe ordonate (
a[start]…a[split]
și
- a[split +1]…a[termină]) și le îmbină în ordinea sortării.
Mecanica funcției de îmbinare este discutată mai sus.
Schema generală a algoritmului
Metoda matricei de sortare de îmbinare constă în doi pași mari:
- Împărțiți matricea originală nesortată în bucăți mici.
- Colectați-le în perechi, urmând regula de sortare.
O sarcină mare și complexă este împărțită în multe altele simple, care sunt rezolvate secvenţial, ducând la rezultatul dorit.
Evaluarea metodei
Complexitatea temporală a sortării îmbinării este determinată de înălțimea arborelui împărțitalgoritm și este egal cu numărul de elemente din tablou (n) ori cu logaritmul său (log n). O astfel de estimare se numește logaritmică.
Acesta este atât un avantaj, cât și un dezavantaj al metodei. Timpul său de rulare nu se modifică nici în cel mai rău caz, când matricea originală este sortată în ordine inversă. Cu toate acestea, atunci când procesează date complet sortate, algoritmul nu oferă un câștig de timp.
Este de asemenea important să rețineți costul memoriei al metodei de sortare prin îmbinare. Sunt egale cu dimensiunea colecției originale. În această zonă alocată suplimentar, o matrice sortată este asamblată din bucăți.
Implementarea algoritmului
Sortarea îmbinării Pascal este afișată mai jos.
Procedura MergeSort(nume: șir; var f: text); Var a1, a2, s, i, j, kol, tmp: întreg; f1, f2: text; b: boolean Begincol:=0; Atribuire(f, nume); resetare(f); Deși nu EOF(f), începe citirea(f, a1); inc(col); Sfârşit; aproape(f); Assign(f1, '{numele primului fişier auxiliar}'); Assign(f2, '{numele celui de-al doilea fişier auxiliar}'); s:=1; În timp ce (s<kol) începe Reset(f); rescrie(f1); rescrie(f2); Pentru i:=1 to kol div 2 nu începe Read(f, a1); Scrie(f1, a1, ' '); Sfârşit; Dacă (kol div 2) mod s0 atunci începe tmp:=kol div 2; În timp ce tmp mod s0 începe Read(f, a1); Scrie(f1, a1, ' '); inc(tmp); Sfârşit; Sfârşit; Deși nu EOF(f), începe Read(f, a2); Scrie(f2, a2, ' '); Sfârşit; aproape(f); close(f1); close(f2); rescrie(f); resetare(f1); resetare(f2); Citiți(f1, a1); Citiți(f2, a2); În timp ce (nu EOF(f1)) și (nu EOF(f2)) încep i:=0; j:=0; b:=adevărat; În timp ce (b) și (nu EOF(f1)) și (nu EOF(f2)) încep Dacă (a1<a2) atunci începeScrie(f, a1, ' '); Citiți(f1, a1); inc(i); End else begin Write(f, a2, ' '); Citiți(f2, a2); inc(j); Sfârşit; Dacă (i=s) sau (j=s) atunci b:=fals; Sfârşit; Dacă nu b, atunci începe While (i<s) și (nu EOF(f1)) începe Write(f, a1, ' '); Citiți(f1, a1); inc(i); Sfârşit; În timp ce (j<s) și (nu EOF(f2)) încep Write(f, a2, ''); Citiți(f2, a2); inc(j); Sfârşit; Sfârşit; Sfârşit; Deși nu EOF(f1), începe tmp:=a1; Citiți(f1, a1); Dacă nu EOF(f1), atunci Write(f, tmp, ' ') altfel Write(f, tmp); Sfârşit; Deși nu EOF(f2), începe tmp:=a2; Citiți(f2, a2); Dacă nu EOF(f2), atunci Write(f, tmp, ' ') altfel Write(f, tmp); Sfârşit; aproape(f); close(f1); close(f2); s:=s2; Sfârşit; Șterge (f1); Șterge (f2); Sfârșit;
Vizual, funcționarea algoritmului arată astfel (sus - secvență neordonată, jos - ordonată).
Sortarea datelor externe
Foarte des este nevoie de sortarea unor date aflate în memoria externă a computerului. În unele cazuri, acestea au dimensiuni impresionante și nu pot fi plasate în RAM pentru a facilita accesul la ele. Pentru astfel de cazuri, se folosesc metode externe de sortare.
Nevoia de a accesa medii externe degradează eficiența timpului de procesare.
Complexitatea lucrării este că algoritmul poate accesa doar un element al fluxului de date la un moment dat. Și în acest caz, unul dintre cele mai bune rezultate este afișat de metoda de sortare prin îmbinare, care poate compara elementele a două fișiere secvenţial unul după altul.
Citirea datelor de lasursă externă, prelucrarea și scrierea lor în fișierul final se efectuează în blocuri ordonate (serie). În funcție de modul de lucru cu dimensiunea seriei ordonate, există două tipuri de sortare: fuziune simplă și naturală.
Imbinare simplă
Cu o simplă îmbinare, lungimea seriei este fixă.
Astfel, în fișierul original nesortat, toate seriile constau dintr-un singur element. După primul pas, dimensiunea crește la două. Următorul - 4, 8, 16 și așa mai departe.
Funcționează astfel:
- Fișierul sursă (f) este împărțit în două auxiliare - f1, f2.
- Sunt din nou îmbinați într-un singur fișier (f), dar în același timp toate elementele sunt comparate în perechi și formează perechi. Dimensiunea seriei la acest pas devine două.
- Pasul 1 se repetă.
- Pasul 2 se repetă, dar 2-urile deja ordonate sunt îmbinate pentru a forma 4-uri sortate.
- Bucla continuă, crescând seria la fiecare iterație, până când întregul fișier este sortat.
De unde știi că sortarea exterioară cu o simplă îmbinare este completă?
- lungime de serie nouă (după îmbinare) nu mai mică decât numărul total de elemente;
- a mai rămas doar un episod;
- Fișierul auxiliar f2 a fost lăsat gol.
Dezavantajele unei îmbinări simple sunt: deoarece lungimea rulării este fixă la fiecare trecere de îmbinare, procesarea datelor parțial ordonate va dura la fel de mult ca și a datelor complet aleatorii.
Fuziune naturală
Această metodă nu limitează lungimeaserie, dar alege maximul posibil.
Algoritm de sortare:
- Citirea secvenței inițiale din fișierul f. Primul element primit este scris în fișierul f1.
- Dacă următoarea intrare îndeplinește condiția de sortare, se scrie acolo, dacă nu, atunci în al doilea fișier auxiliar f2.
- În acest fel, toate înregistrările fișierului sursă sunt distribuite și se formează o secvență ordonată în f1, care determină dimensiunea curentă a seriei.
- Fișierele f1 și f2 sunt îmbinate.
- Ciclul se repetă.
Datorită dimensiunii nefixate a seriei, este necesar să se marcheze sfârșitul secvenței cu un caracter special. Prin urmare, la comasare, numărul de comparații crește. În plus, dimensiunea unuia dintre fișierele auxiliare poate fi apropiată de dimensiunea originalului.
În medie, îmbinarea naturală este mai eficientă decât simpla îmbinare cu sortare externă.
Caracteristici ale algoritmului
La compararea a două valori identice, metoda păstrează ordinea lor inițială, adică este stabilă.
Procesul de sortare poate fi împărțit cu succes în mai multe fire.
Videoclipul demonstrează clar funcționarea algoritmului de sortare prin îmbinare.
