Merge sort és un dels algorismes bàsics de la informàtica, formulat l'any 1945 pel gran matemàtic John von Neumann. Mentre participava en el Projecte Manhattan, Neumann es va enfrontar a la necessitat de processar de manera eficient grans quantitats de dades. El mètode que va desenvolupar utilitzava el principi de "divideix i vencerà", que va reduir significativament el temps necessari per treballar.
Principi i ús de l'algorisme
El mètode d'ordenació per combinació s'utilitza en problemes d'ordenació d'estructures que tenen accés ordenat a elements, com ara matrius, llistes, fluxos.
Durant el processament, el bloc de dades inicial es divideix en components petits, fins a un element, que de fet ja és una llista ordenada. Després es torna a muntar en l'ordre correcte.
L'ordenació d'una matriu d'una determinada longitud requereix una àrea de memòria addicional de la mateixa mida, en la qual la matriu ordenada es recull en parts.
El mètode es pot utilitzar per demanar qualsevol tipus de dades comparable, com ara números o cadenes.
Combinació ordenadaparcel·les
Per entendre l'algorisme, comencem la seva anàlisi des del final, des del mecanisme de fusió de blocs ordenats.
Imaginem que tenim dues matrius de números ordenats de qualsevol manera que s'han de combinar entre si perquè l'ordenació no es trenqui. Per simplificar, ordenarem els números en ordre ascendent.
Exemple elemental: ambdues matrius consten d'un element cadascuna.
int arr1={31}; int arr2={18};
Per combinar-los, cal agafar l'element zero de la primera matriu (no oblideu que la numeració comença des de zero) i l'element zero de la segona matriu. Aquests són, respectivament, 31 i 18. Segons la condició de classificació, el número 18 hauria de ser primer, ja que és menor. Només has de posar els números en l'ordre correcte:
int resultat={18, 31};
Mirem un exemple més complicat, on cada matriu consta de diversos elements:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
L'algorisme de combinació consistirà en comparar seqüencialment elements més petits i col·locar-los a la matriu resultant en l'ordre correcte. Per fer un seguiment dels índexs actuals, introduïm dues variables: índex1 i índex2. Inicialment, els posem a zero, ja que les matrius estan ordenades i els elements més petits estan al principi.
int índex1=0; int index2=0;
Escrivim tot el procés de fusió pas a pas:
- Preneu l'element amb index1 de la matriu arr1 i l'element amb index2 de la matriu arr2.
- Compara, selecciona el més petit d'ells i posa-himatriu resultant.
- Incrementa l'índex actual de l'element més petit en 1.
- Continueu des del primer pas.
A la primera òrbita, la situació serà així:
index1=0; índex2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; índex1++; resultat[0]=arr1[0]; // resultat=[2]
Al segon torn:
index1=1; índex2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; índex2++; resultat[1]=arr2[0]; // resultat=[2, 5]
Tercer:
index1=1; índex2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; índex2++; resultat[2]=arr2[1]; // resultat=[2, 5, 6]
I així successivament, fins que el resultat sigui una matriu completament ordenada: {2, 5, 6, 17, 21, 19, 30, 45}.
Poden sorgir certes dificultats si es fusionen matrius amb longituds diferents. Què passa si un dels índexs actuals ha arribat a l'últim element i encara queden membres a la segona matriu?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 pas índex1=0, índex2=0; 1 2 resultat={1, 2}; // índex de 3 passos1=1, índex2=1; 4 < 5 resultat={1, 2, 4}; //4 passos índex1=2, índex2=1 ??
La variable index1 ha assolit el valor 2, però la matriu arr1 no té cap element amb aquest índex. Aquí tot és senzill: només cal transferir els elements restants de la segona matriu a la resultant, conservant el seu ordre.
resultat={1, 2, 4, 5, 6, 7, 9};
Aquesta situació ens indica la necessitatcoincideix l'índex de comprovació actual amb la longitud de la matriu que s'està combinant.
Esquema de fusió per a seqüències ordenades (A i B) de diferents longituds:
- Si la longitud de les dues seqüències és superior a 0, compareu A[0] i B[0] i moveu la més petita a la memòria intermèdia.
- Si la longitud d'una de les seqüències és 0, agafeu els elements restants de la segona seqüència i, sense canviar-ne l'ordre, aneu al final de la memòria intermèdia.
Implementació de la segona etapa
A continuació es mostra un exemple d'unió de dues matrius ordenades a Java.
int a1=nou int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=nou int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=nou int[a1.longitud + a2.longitud]; int i=0, j=0; per (int k=0; k a1.longitud-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.longitud-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++; } }
Aquí:
- a1 i a2 són les matrius ordenades originals que s'han de combinar;
- a3 – matriu final;
- i i j són índexs dels elements actuals per a les matrius a1 i a2.
La primera i la segona si les condicions asseguren que els índexs no van més enllà de la mida de la matriu. Els blocs de condició tercer i quart, respectivament, es mouen a la matriu resultant de l'element més petit.
Divideix i conquereix
Així, hem après a combinar els ordenatscol·leccions de valors. Es pot dir que la segona part de l'algorisme d'ordenació de la fusió, la fusió en si mateixa, ja s'ha ordenat.
No obstant això, encara heu d'entendre com passar de la matriu original de números sense ordenar a diversos ordenats que es poden combinar.
Considerem la primera etapa de l'algorisme i aprenem a separar matrius.
Això no és difícil: la llista original de valors es divideix per la meitat, després cada part també es bifurca i així successivament fins que s'obtinguin blocs molt petits.
La longitud d'aquests elements mínims pot ser igual a un, és a dir, poden ser ells mateixos una matriu ordenada, però aquesta no és una condició necessària. La mida del bloc es determina per endavant i es pot utilitzar qualsevol algorisme d'ordenació adequat que funcioni de manera eficient amb matrius de mides petites (per exemple, ordenació ràpida o ordenació d'inserció) per ordenar-lo.
Sembla això.
// matriu original {34, 95, 10, 2, 102, 70}; // primer divideix {34, 95, 10} i {2, 102, 70}; // Segon dividit {34} i {95, 10} i {2} i {102, 70}
Els blocs resultants, formats per 1-2 elements, són molt fàcils d'organitzar.
Després d'això, heu de combinar les matrius petites ja ordenades per parelles, conservant l'ordre dels membres, cosa que ja hem après a fer.
Implementació de la primera etapa
La partició recursiva d'una matriu es mostra a continuació.
void mergeSort(T a, inici llarg, final llarg) { divisió llarga; si(inici < final) { split=(inici + final)/2; mergeOrdenar(a, iniciar, dividir); mergeOrdenar(a, dividir+1, acabar); fusionar (a, començar, dividir, acabar); } }
Què passa en aquest codi:
-
La funció mergeSort obté la matriu inicial
a
i les vores esquerra i dreta de la regió que cal ordenar (els índexs comencen i
- finish).
-
Si la longitud d'aquesta secció és superior a un (
inici < final
), es divideix en dues parts (per l'índex
- split), i cadascun s'ordena de manera recursiva.
-
A la crida de funció recursiva per al costat esquerre, es passa l'índex inicial de la trama i l'índex
split
. Per a la correcta, respectivament, l'inici serà
- (divisió + 1) i el final serà l'últim índex de la secció original.
La
-
Funció
merge
obté dues seqüències ordenades (
a[inici]…a[dividir]
i
- a[dividir +1]…a[acabar]) i els combina per ordre d'ordenació.
La mecànica de la funció de combinació es parla més amunt.
Esquema general de l'algorisme
El mètode de matriu d'ordenació combinada consta de dos grans passos:
- Divideix la matriu original no ordenada en trossos petits.
- Recolliu-los per parelles, seguint la regla d'ordenació.
Una tasca gran i complexa es divideix en moltes de senzilles, que es resolen seqüencialment, donant lloc al resultat desitjat.
Avaluació del mètode
La complexitat temporal de l'ordenació de combinació ve determinada per l'alçada de l'arbre dividitalgorisme i és igual al nombre d'elements de la matriu (n) vegades el seu logaritme (log n). Aquesta estimació s'anomena logarítmica.
Això és alhora un avantatge i un desavantatge del mètode. El seu temps d'execució no canvia fins i tot en el pitjor dels casos, quan la matriu original s'ordena en ordre invers. Tanmateix, quan es processen dades completament ordenades, l'algoritme no proporciona un guany de temps.
També és important tenir en compte el cost de memòria del mètode d'ordenació combinada. Són iguals a la mida de la col·lecció original. En aquesta àrea assignada addicionalment, s'ajunta una matriu ordenada a partir de les peces.
Implementació de l'algorisme
L'ordenació de combinació de Pascal es mostra a continuació.
Procediment MergeSort (nom: cadena; var f: text); Var a1, a2, s, i, j, kol, tmp: enter; f1, f2: text; b: booleà Begincol:=0; Assigna (f, nom); restablir (f); Encara que no EOF(f), comenceu a llegir(f, a1); inc(col); final; tancar (f); Assign(f1, '{nom del primer fitxer auxiliar}'); Assign(f2, '{nom del segon fitxer auxiliar}'); s:=1; Mentre (s<kol) comenceu Reset(f); reescriure (f1); reescriure (f2); Per i:=1 a kol div 2, comenceu Read(f, a1); Escriu(f1, a1, ''); final; Si (kol div 2) mod s0 llavors comença tmp:=kol div 2; Mentre que tmp mod s0 comença Read(f, a1); Escriu(f1, a1, ''); inc(tmp); final; final; Encara que no EOF(f), comenceu Read(f, a2); Escriu(f2, a2, ''); final; tancar (f); tancar (f1); tancar (f2); reescriure (f); restablir (f1); restablir (f2); Llegir(f1, a1); Llegir(f2, a2); Mentre que (no EOF(f1)) i (no EOF(f2)) comencen i:=0; j:=0; b:=vertader; Mentre que (b) i (no EOF(f1)) i (no EOF(f2)) comencen Si (a1<a2) comencenEscriu (f, a1, ' '); Llegir(f1, a1); inc(i); End else begin Write(f, a2, ''); Llegir(f2, a2); inc(j); final; Si (i=s) o (j=s) aleshores b:=fals; final; Si no és b, comencen Mentre (i<s) i (no EOF(f1)) comencen Write(f, a1, ' '); Llegir(f1, a1); inc(i); final; Mentre que (j<s) i (no EOF(f2)) comencen Write(f, a2, ''); Llegir(f2, a2); inc(j); final; final; final; Encara que no EOF(f1), comenceu tmp:=a1; Llegir(f1, a1); Si no és EOF(f1), llavors Write(f, tmp, ' ') sinó Write(f, tmp); final; Encara que no EOF(f2), comenceu tmp:=a2; Llegir(f2, a2); Si no és EOF(f2), llavors Write(f, tmp, ' ') sinó Write(f, tmp); final; tancar (f); tancar (f1); tancar (f2); s:=s2; final; Esborra (f1); Esborra (f2); Final;
Visualment, el funcionament de l'algorisme té aquest aspecte (a d alt - seqüència no ordenada, a baix - ordenat).
Ordenació de dades externes
Molt sovint cal ordenar algunes dades que es troben a la memòria externa de l'ordinador. En alguns casos, tenen una mida impressionant i no es poden col·locar a la memòria RAM per facilitar-hi l'accés. En aquests casos, s'utilitzen mètodes d'ordenació externs.
La necessitat d'accedir a mitjans externs degrada l'eficiència del temps de processament.
La complexitat del treball és que l'algoritme només pot accedir a un element del flux de dades alhora. I en aquest cas, un dels millors resultats es mostra amb el mètode d'ordenació combinada, que pot comparar els elements de dos fitxers seqüencialment un darrere l' altre.
Llegint dades defont externa, el seu tractament i escriptura al fitxer final es duen a terme en blocs ordenats (sèries). Segons la manera de treballar amb la mida de les sèries ordenades, hi ha dos tipus d'ordenació: fusió simple i natural.
Fusió simple
Amb una combinació senzilla, la llargada de la sèrie és fixa.
Així, al fitxer original sense ordenar, totes les sèries consten d'un element. Després del primer pas, la mida augmenta a dos. Següent: 4, 8, 16 i així successivament.
Funciona així:
- El fitxer font (f) es divideix en dos auxiliars: f1, f2.
- Es fusionen de nou en un sol fitxer (f), però alhora es comparen tots els elements per parells i formen parells. La mida de la sèrie en aquest pas passa a ser dues.
- Es repeteix el pas 1.
- El pas 2 es repeteix, però els 2 ja ordenats es fusionen per formar 4 ordenats.
- El bucle continua, augmentant la sèrie a cada iteració, fins que s'ordena tot el fitxer.
Com saps que l'ordenació externa amb una combinació simple s'ha completat?
- durada de sèrie nova (després de la fusió) no inferior al nombre total d'elements;
- només queda un episodi;
- El fitxer auxiliar f2 s'ha deixat buit.
Els desavantatges d'una fusió simple són: com que la durada de l'execució es fixa a cada passada de fusió, les dades ordenades parcialment trigaran a processar-se com a dades completament aleatòries.
Fusió natural
Aquest mètode no limita la longitudsèrie, però tria el màxim possible.
Algorisme d'ordenació:
- Llegint la seqüència inicial del fitxer f. El primer element rebut s'escriu al fitxer f1.
- Si la següent entrada compleix la condició d'ordenació, s'escriu allà, si no, al segon fitxer auxiliar f2.
- D'aquesta manera, es distribueixen tots els registres del fitxer font i es forma una seqüència ordenada a f1, que determina la mida actual de la sèrie.
- Els fitxers f1 i f2 es combinen.
- El cicle es repeteix.
A causa de la mida no fixa de la sèrie, cal marcar el final de la seqüència amb un caràcter especial. Per tant, quan es fusionen, augmenta el nombre de comparacions. A més, la mida d'un dels fitxers auxiliars pot ser propera a la mida de l'original.
De mitjana, la combinació natural és més eficient que la combinació simple amb l'ordenació externa.
Característiques de l'algorisme
Quan es comparen dos valors idèntics, el mètode conserva el seu ordre original, és a dir, és estable.
El procés d'ordenació es pot dividir amb èxit en diversos fils.
El vídeo demostra clarament el funcionament de l'algorisme d'ordenació de combinació.
