Merge sort es uno de los algoritmos informáticos básicos, formulado en 1945 por el gran matemático John von Neumann. Mientras participaba en el Proyecto Manhattan, Neumann se enfrentó a la necesidad de procesar de manera eficiente grandes cantidades de datos. El método que desarrolló utilizó el principio de "divide y vencerás", lo que redujo significativamente el tiempo requerido para el trabajo.
Principio y uso del algoritmo
El método de clasificación por combinación se usa en problemas de clasificación de estructuras que tienen acceso ordenado a elementos, como arreglos, listas, flujos.
Durante el procesamiento, el bloque de datos inicial se divide en pequeños componentes, hasta un elemento, que de hecho ya es una lista ordenada. Luego se vuelve a montar en el orden correcto.
Ordenar una matriz de cierta longitud requiere un área de memoria adicional del mismo tamaño, en la que la matriz ordenada se recopila en partes.
El método se puede utilizar para ordenar cualquier tipo de datos comparable, como números o cadenas.
Combinar ordenadoparcelas
Para comprender el algoritmo, comencemos su análisis desde el final, desde el mecanismo de combinación de bloques ordenados.
Imaginemos que tenemos dos conjuntos de números ordenados de alguna manera que deben combinarse entre sí para que la clasificación no se interrumpa. Para simplificar, ordenaremos los números en orden ascendente.
Ejemplo elemental: ambas matrices constan de un elemento cada una.
int arr1={31}; int arr2={18};
Para fusionarlos, debe tomar el elemento cero de la primera matriz (no olvide que la numeración comienza desde cero) y el elemento cero de la segunda matriz. Estos son, respectivamente, 31 y 18. De acuerdo con la condición de clasificación, el número 18 debe ir primero, ya que es menor. Simplemente coloque los números en el orden correcto:
int resultado={18, 31};
Veamos un ejemplo más complicado, donde cada matriz consta de varios elementos:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
El algoritmo de fusión consistirá en comparar secuencialmente elementos más pequeños y colocarlos en la matriz resultante en el orden correcto. Para realizar un seguimiento de los índices actuales, introduzcamos dos variables: index1 e index2. Inicialmente, los establecemos en cero, ya que las matrices están ordenadas y los elementos más pequeños están al principio.
int índice1=0; int índice2=0;
Escribamos todo el proceso de fusión paso a paso:
- Tome el elemento con índice1 de la matriz arr1 y el elemento con índice2 de la matriz arr2.
- Compara, selecciona el más pequeño de ellos y ponlomatriz resultante.
- Incrementa el índice actual del elemento más pequeño en 1.
- Continúa desde el primer paso.
En la primera órbita, la situación se verá así:
índice1=0; índice2=0; matriz1[0]=2; matriz2[0]=5; arr1[0] < arr2[0]; índice1++; resultado[0]=arr1[0]; // resultado=[2]
En el segundo turno:
índice1=1; índice2=0; matriz1[1]=17; matriz2[0]=5; arr1[1] > arr2[0]; índice2++; resultado[1]=arr2[0]; // resultado=[2, 5]
Tercero:
índice1=1; índice2=1; matriz1[1]=17; matriz2[1]=6; arr1[1] > arr2[1]; índice2++; resultado[2]=arr2[1]; // resultado=[2, 5, 6]
Y así sucesivamente, hasta que el resultado sea una matriz completamente ordenada: {2, 5, 6, 17, 21, 19, 30, 45}.
Pueden surgir ciertas dificultades si se fusionan matrices con diferentes longitudes. ¿Qué pasa si uno de los índices actuales ha alcanzado el último elemento y aún quedan miembros en la segunda matriz?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 paso índice1=0, índice2=0; 1 2 resultado={1, 2}; // 3 pasos index1=1, index2=1; 4 < 5 resultado={1, 2, 4}; //4 pasos índice1=2, índice2=1 ??
La variable index1 ha alcanzado el valor 2, pero la matriz arr1 no tiene un elemento con ese índice. Aquí todo es simple: simplemente transfiera los elementos restantes de la segunda matriz a la resultante, conservando su orden.
resultado={1, 2, 4, 5, 6, 7, 9};
Esta situación nos indica la necesidadhacer coincidir el índice de verificación actual con la longitud de la matriz que se fusiona.
Esquema de fusión para secuencias ordenadas (A y B) de diferentes longitudes:
- Si la longitud de ambas secuencias es mayor que 0, compare A[0] y B[0] y mueva la más pequeña al búfer.
- Si la longitud de una de las secuencias es 0, tome los elementos restantes de la segunda secuencia y, sin cambiar su orden, muévase al final del búfer.
Implementación de la segunda etapa
A continuación se muestra un ejemplo de unir dos matrices ordenadas en Java.
int a1=nuevo int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=nuevo int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=new int[a1.longitud + a2.longitud]; inti=0, j=0; for (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; yo++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; yo++; } más { int b=a2[j]; a3[k]=b; j++; } }
Aquí:
- a1 y a2 son las matrices ordenadas originales que se fusionarán;
- a3 – matriz final;
- i y j son índices de los elementos actuales para las matrices a1 y a2.
La primera y la segunda condición if aseguran que los índices no superen el tamaño de la matriz. Los bloques de condición tercero y cuarto, respectivamente, se mueven a la matriz resultante del elemento más pequeño.
Divide y vencerás
Entonces, hemos aprendido a fusionar los ordenadoscolecciones de valores. Se puede decir que la segunda parte del algoritmo de clasificación por fusión, la fusión en sí, ya se ha ordenado.
Sin embargo, aún debe comprender cómo pasar de la matriz original de números sin clasificar a varios números ordenados que se pueden fusionar.
Consideremos la primera etapa del algoritmo y aprendamos a separar matrices.
Esto no es difícil: la lista original de valores se divide por la mitad, luego cada parte también se bifurca, y así sucesivamente hasta obtener bloques muy pequeños.
La longitud de tales elementos mínimos puede ser igual a uno, es decir, ellos mismos pueden ser una matriz ordenada, pero esta no es una condición necesaria. El tamaño del bloque se determina de antemano y se puede utilizar cualquier algoritmo de clasificación adecuado que funcione de manera eficiente con matrices de tamaños pequeños (por ejemplo, clasificación rápida o clasificación por inserción).
Se parece a esto.
// matriz original {34, 95, 10, 2, 102, 70}; // primera división {34, 95, 10} y {2, 102, 70}; // segunda división {34} y {95, 10} y {2} y {102, 70}
Los bloques resultantes, que constan de 1 o 2 elementos, son muy fáciles de organizar.
Después de eso, debe fusionar los arreglos pequeños ya ordenados en pares, conservando el orden de los miembros, lo cual ya hemos aprendido a hacer.
Implementación de la primera etapa
La partición recursiva de una matriz se muestra a continuación.
void mergeSort(T a, comienzo largo, final largo) { división larga; Si(inicio < fin) { split=(inicio + fin)/2; mergeSort(a, inicio, división); mergeSort(a, split+1, finish); fusionar (a, comenzar, dividir, terminar); } }
Qué sucede en este código:
-
La función mergeSort obtiene la matriz inicial
a
y los bordes izquierdo y derecho de la región a ordenar (índices start y
- finish).
-
Si la longitud de esta sección es mayor que uno (
start < finish
), entonces se divide en dos partes (por el índice
- split), y cada uno se ordena recursivamente.
-
En la llamada de función recursiva para el lado izquierdo, se pasan el índice inicial del gráfico y el índice
split
. Para el derecho, respectivamente, el comienzo será
- (split + 1), y el final será el último índice de la sección original.
-
La función
merge
obtiene dos secuencias ordenadas (
a[start]…a[split]
y
- a[split +1]…a[terminar]) y los fusiona en orden de clasificación.
La mecánica de la función de combinación se trata más arriba.
Esquema general del algoritmo
El método de matriz de clasificación por fusión consta de dos grandes pasos:
- Divida la matriz original sin clasificar en pedazos pequeños.
- Recójalos en pares, siguiendo la regla de clasificación.
Una tarea grande y compleja se divide en muchas más sencillas, que se resuelven secuencialmente, lo que conduce al resultado deseado.
Evaluación del método
La complejidad temporal de la ordenación por fusión está determinada por la altura del árbol divididoalgoritmo y es igual al número de elementos en la matriz (n) por su logaritmo (log n). Tal estimación se llama logarítmica.
Esto es tanto una ventaja como una desventaja del método. Su tiempo de ejecución no cambia incluso en el peor de los casos, cuando la matriz original se ordena en orden inverso. Sin embargo, cuando se procesan datos completamente ordenados, el algoritmo no proporciona una ganancia de tiempo.
También es importante tener en cuenta el costo de memoria del método de clasificación por fusión. Son iguales al tamaño de la colección original. En esta área asignada adicionalmente, se ensambla una matriz ordenada a partir de las piezas.
Implementación del algoritmo
A continuación se muestra la ordenación por combinación de Pascal.
Procedure MergeSort(nombre: cadena; var f: texto); Var a1, a2, s, i, j, kol, tmp: entero; f1, f2: texto; b: booleano Comienzocol:=0; Asignar(f, nombre); restablecer (f); Si bien no es EOF (f), comience a leer (f, a1); inc(columna); fin; cerrar (f); Assign(f1, '{nombre del primer archivo auxiliar}'); Assign(f2, '{nombre del segundo archivo auxiliar}'); s:=1; Mientras que (s<kol) comienza Reset(f); reescribir (f1); reescribir (f2); Para i:=1 a kol div 2 comience Read(f, a1); Escribir (f1, a1, ' '); fin; Si (kol div 2) mod s0 entonces comienza tmp:=kol div 2; Mientras que tmp mod s0 comienza Read(f, a1); Escribir (f1, a1, ' '); inc(tmp); fin; fin; Si bien no es EOF(f), sí comienza Read(f, a2); Escribir(f2, a2, ' '); fin; cerrar (f); cerrar (f1); cerrar (f2); reescribir (f); restablecer (f1); restablecer (f2); Leer (f1, a1); Leer (f2, a2); Mientras que (no EOF(f1)) y (no EOF(f2)) sí comienzan i:=0; j:=0; b:=verdadero; Mientras que (b) y (no EOF(f1)) y (no EOF(f2)) sí comienzan Si (a1<a2) entonces comienzanEscribir(f, a1, ' '); Leer (f1, a1); inc(i); End else begin Write(f, a2, ' '); Leer (f2, a2); inc(j); fin; Si (i=s) o (j=s) entonces b:=falso; fin; Si no es b entonces empieza Mientras (i<s) y (no EOF(f1)) empiezan Escribe(f, a1, ' '); Leer (f1, a1); inc(i); fin; Mientras que (j<s) y (no EOF(f2)) comienzan Write(f, a2, ' '); Leer (f2, a2); inc(j); fin; fin; fin; Si bien no es EOF(f1), sí comienza tmp:=a1; Leer (f1, a1); Si no EOF(f1) entonces Write(f, tmp, ' ') else Write(f, tmp); fin; Mientras no EOF(f2) comience tmp:=a2; Leer (f2, a2); Si no EOF(f2) entonces Write(f, tmp, ' ') else Write(f, tmp); fin; cerrar (f); cerrar (f1); cerrar (f2); s:=s2; fin; Borrar (f1); Borrar (f2); Fin;
Visualmente, el funcionamiento del algoritmo se ve así (arriba: secuencia desordenada, abajo: orden).
Clasificación de datos externos
Muy a menudo es necesario ordenar algunos datos ubicados en la memoria externa de la computadora. En algunos casos, tienen un tamaño impresionante y no se pueden colocar en la memoria RAM para facilitar el acceso a ellos. Para tales casos, se utilizan métodos de clasificación externa.
La necesidad de acceder a medios externos degrada la eficiencia del tiempo de procesamiento.
La complejidad del trabajo es que el algoritmo solo puede acceder a un elemento del flujo de datos a la vez. Y en este caso, uno de los mejores resultados lo muestra el método de clasificación por combinación, que puede comparar los elementos de dos archivos secuencialmente, uno tras otro.
Leyendo datos defuente externa, su procesamiento y escritura en el archivo final se llevan a cabo en bloques ordenados (series). Según la forma de trabajar con el tamaño de las series ordenadas, existen dos tipos de ordenación: simple y natural merging.
Fusión simple
Con una combinación simple, la longitud de la serie es fija.
Así, en el archivo original sin clasificar, todas las series constan de un elemento. Después del primer paso, el tamaño aumenta a dos. Siguiente - 4, 8, 16 y así sucesivamente.
Funciona así:
- El archivo fuente (f) se divide en dos archivos auxiliares: f1, f2.
- Se fusionan nuevamente en un archivo (f), pero al mismo tiempo todos los elementos se comparan en pares y forman pares. El tamaño de la serie en este paso se convierte en dos.
- Se repite el paso 1.
- Se repite el paso 2, pero los 2 ya ordenados se fusionan para formar 4 ordenados.
- El bucle continúa, aumentando la serie en cada iteración, hasta que se ordena todo el archivo.
¿Cómo sabes que la clasificación externa con una combinación simple está completa?
- longitud de la nueva serie (después de la fusión) no menor que el número total de elementos;
- solo queda un episodio;
- El archivo auxiliar f2 quedó vacío.
Las desventajas de una combinación simple son: dado que la longitud de ejecución se fija en cada paso de combinación, los datos parcialmente ordenados tardarán tanto en procesarse como los datos completamente aleatorios.
Fusión natural
Este método no limita la longitudserie, pero elige la máxima posible.
Algoritmo de clasificación:
- Leyendo la secuencia inicial del archivo f. El primer elemento recibido se escribe en el archivo f1.
- Si la siguiente entrada cumple con la condición de clasificación, se escribe allí, si no, entonces en el segundo archivo auxiliar f2.
- De esta manera, todos los registros del archivo fuente se distribuyen y se forma una secuencia ordenada en f1, que determina el tamaño actual de la serie.
- Los archivos f1 y f2 se fusionan.
- El ciclo se repite.
Debido al tamaño no fijo de la serie, es necesario marcar el final de la secuencia con un carácter especial. Por lo tanto, al fusionarse, aumenta el número de comparaciones. Además, el tamaño de uno de los archivos auxiliares puede estar cerca del tamaño del original.
En promedio, la combinación natural es más eficiente que la combinación simple con clasificación externa.
Características del algoritmo
Al comparar dos valores idénticos, el método conserva su orden original, es decir, es estable.
El proceso de clasificación se puede dividir con éxito en varios subprocesos.
El video demuestra claramente el funcionamiento del algoritmo de clasificación por combinación.
