Combinar ordenar

Algoritmo de clasificación divide y vencerás

En informática , merge sort (también comúnmente escrito como mergesort ) es un algoritmo de clasificación eficiente, de propósito general y basado en comparaciones . La mayoría de las implementaciones producen una clasificación estable , lo que significa que el orden relativo de elementos iguales es el mismo en la entrada y la salida. La ordenación por fusión es un algoritmo de divide y vencerás inventado por John von Neumann en 1945. ^[2] Una descripción y un análisis detallados de la ordenación por fusión ascendente aparecieron en un informe de Goldstine y von Neumann ya en 1948. ^{[3 ]}

Algoritmo

Conceptualmente, una clasificación por combinación funciona de la siguiente manera:

1. Divida la lista sin ordenar en n sublistas, cada una de las cuales contenga un elemento (una lista de un elemento se considera ordenada).
2. Combine sublistas repetidamente para producir nuevas sublistas ordenadas hasta que solo quede una sublista. Esta será la lista ordenada.

Implementación de arriba hacia abajo

Ejemplo de código tipo C que utiliza índices para un algoritmo de ordenación por combinación de arriba hacia abajo que divide recursivamente la lista (llamada ejecuciones en este ejemplo) en sublistas hasta que el tamaño de la sublista es 1, luego combina esas sublistas para producir una lista ordenada. El paso de copia hacia atrás se evita alternando la dirección de la fusión con cada nivel de recursividad (excepto para una copia inicial única, que también se puede evitar). Para ayudar a entender esto, considere una matriz con dos elementos. Los elementos se copian en B[] y luego se fusionan nuevamente en A[]. Si hay cuatro elementos, cuando se alcanza el nivel inferior del nivel de recursividad, las ejecuciones de un solo elemento desde A[] se fusionan en B[], y luego, en el siguiente nivel superior de recursividad, esas ejecuciones de dos elementos se fusionan en A[ ]. Este patrón continúa con cada nivel de recursividad.

// La matriz A[] tiene los elementos para ordenar; la matriz B[] es una matriz de trabajo. void TopDownMergeSort ( A [], B [], n ) { CopyArray ( A , 0 , n , B ); // copia única de A[] a B[] TopDownSplitMerge ( A , 0 , n , B ); // ordenar datos de B[] en A[] }             // Dividir A[] en 2 ejecuciones, ordenar ambas ejecuciones en B[], fusionar ambas ejecuciones de B[] a A[] // iBegin es inclusivo; iEnd es exclusivo (A[iEnd] no está en el conjunto). void TopDownSplitMerge ( B [], iBegin , iEnd , A []) { if ( iEnd - iBegin <= 1 ) // si tamaño de ejecución == 1 return ; // considerarlo ordenado // dividir la ejecución de más de 1 elemento en mitades iMiddle = ( iEnd + iBegin ) / 2 ; // iMiddle = punto medio // ordena recursivamente ambas ejecuciones desde la matriz A[] en B[] TopDownSplitMerge ( A , iBegin , iMiddle , B ); // ordenar la ejecución izquierda TopDownSplitMerge ( A , iMiddle , iEnd , B ); // ordenar la ejecución correcta // fusionar las ejecuciones resultantes de la matriz B[] en A[] TopDownMerge ( B , iBegin , iMiddle , iEnd , A ); }                                       // La mitad izquierda de la fuente es A[iBegin:iMiddle-1]. // La mitad derecha de la fuente es A[iMiddle:iEnd-1]. // El resultado es B[iBegin:iEnd-1]. void TopDownMerge ( B [], iBegin , iMiddle , iEnd , A []) { i = iBegin , j = iMiddle ; // Mientras haya elementos en los tramos izquierdo o derecho... for ( k = iBegin ; k < iEnd ; k ++ ) { // Si el encabezado de recorrido izquierdo existe y es <= encabezado de recorrido derecho existente. if ( i < iMiddle && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; yo = yo + 1 ; } más { B [ k ] = A [ j ]; j = j + 1 ; } } }                                                         void CopyArray ( A [], iBegin , iEnd , B []) { para ( k = iBegin ; k < iEnd ; k ++ ) B [ k ] = A [ k ]; }               

La clasificación de toda la matriz se logra mediante TopDownMergeSort(A, B, length(A)) .

Implementación ascendente

Ejemplo de código tipo C que utiliza índices para un algoritmo de ordenación por combinación de abajo hacia arriba que trata la lista como una matriz de n sublistas (llamadas ejecuciones en este ejemplo) de tamaño 1 y combina de forma iterativa las sublistas entre dos buffers:

// la matriz A[] tiene los elementos para ordenar; la matriz B[] es una matriz de trabajo void BottomUpMergeSort ( A [], B [], n ) { // Cada ejecución de 1 elemento en A ya está "ordenada". // Realiza secuencias ordenadas sucesivamente más largas de longitud 2, 4, 8, 16... hasta que se ordene toda la matriz. for ( ancho = 1 ; ancho < n ; ancho = 2 * ancho ) { // La matriz A está llena de tramos de largo ancho. for ( i = 0 ; i < n ; i = i + 2 * ancho ) { // Fusionar dos ejecuciones: A[i:i+width-1] y A[i+width:i+2*width-1] a B[] // o copia A[i:n-1] a B[] ( if (i+width >= n) ) BottomUpMerge ( A , i , min ( i + width , n ), min ( i + 2 * ancho , n ), B ); } // Ahora la matriz de trabajo B está llena de ejecuciones de longitud 2*ancho. // Copie la matriz B a la matriz A para la siguiente iteración. // Una implementación más eficiente intercambiaría los roles de A y B. CopyArray ( B , A , n ); // Ahora la matriz A está llena de ejecuciones de longitud 2*ancho. } }                                                    // El tramo izquierdo es A[iLeft:iRight-1]. // El recorrido derecho es A[iRight:iEnd-1]. void BottomUpMerge ( A [], iLeft , iRight , iEnd , B []) { i = iLeft , j = iRight ; // Mientras haya elementos en los tramos izquierdo o derecho... for ( k = iLeft ; k < iEnd ; k ++ ) { // Si el encabezado de recorrido izquierdo existe y es <= encabezado de recorrido derecho existente. if ( i < iRight && ( j >= iEnd || A [ i ] <= A [ j ])) { B [ k ] = A [ i ]; yo = yo + 1 ; } más { B [ k ] = A [ j ]; j = j + 1 ; } } }                                                          void CopyArray ( B [], A [], n ) { para ( i = 0 ; i < n ; i ++ ) A [ i ] = B [ i ]; }              

Implementación de arriba hacia abajo usando listas

Pseudocódigo para el algoritmo de ordenación por fusión de arriba hacia abajo que divide recursivamente la lista de entrada en sublistas más pequeñas hasta que las sublistas se ordenan trivialmente y luego fusiona las sublistas mientras regresa a la cadena de llamadas.

La función merge_sort( lista m) es // Caso base. Una lista de cero o uno elementos está ordenada, por definición.  si la longitud de m ≤ 1 entonces  devuelve m // Caso recursivo. Primero, divida la lista en sublistas del mismo tamaño // que constan de la primera mitad y la segunda mitad de la lista.  // Esto supone que las listas comienzan en el índice 0.  var izquierda: = lista vacía var derecha: = lista vacía para cada x con índice i en m , hazlo  si i < (longitud de m)/2 entonces agregar x a la izquierda demás agregar x a la derecha // Ordena recursivamente ambas sublistas. izquierda := merge_sort(izquierda) derecha: = merge_sort (derecha) // Luego fusiona las sublistas ahora ordenadas. volver a fusionar (izquierda, derecha)

En este ejemplo, la función de combinación fusiona las sublistas izquierda y derecha.

la función fusionar (izquierda, derecha) es el resultado  var : = lista vacía mientras que la izquierda no está vacía y la derecha no está vacía, hazlo  si primero (izquierda) ≤ primero (derecha) entonces agregar primero (izquierda) al resultado izquierda := descanso(izquierda) demás agregar primero (derecha) al resultado derecha: = descanso (derecha) // Tanto la izquierda como la derecha pueden tener elementos left; consumirlos.  // (En realidad, solo se ingresará uno de los siguientes bucles).  Mientras que left no esté vacío, haga agregar primero (izquierda) al resultado izquierda := descanso(izquierda) mientras que la derecha no está vacía, hazlo agregar primero (derecha) al resultado derecha: = descanso (derecha) resultado de retorno

Implementación ascendente mediante listas

Pseudocódigo para el algoritmo de clasificación de fusión ascendente que utiliza una pequeña matriz de referencias de tamaño fijo a nodos, donde matriz[i] es una referencia a una lista de tamaño 2 ⁱ o nil . nodo es una referencia o puntero a un nodo. La función merge() sería similar a la que se muestra en el ejemplo de combinación de listas de arriba hacia abajo, fusiona dos listas ya ordenadas y maneja listas vacías. En este caso, merge() usaría node para sus parámetros de entrada y valor de retorno.

la función merge_sort ( cabeza de nodo ) es // regresa si la lista está vacía si head = nil entonces  devuelve nil var  node array[32]; inicialmente todo nulo resultado del  nodo var  nodo var siguiente var  int i resultado := cabeza // fusionar nodos en una matriz mientras que el resultado ≠ nil do siguiente := resultado.siguiente; resultado.siguiente: = nulo para (i = 0; (i < 32) && (matriz[i] ≠ nil); i += 1) hacer resultado: = fusionar (matriz [i], resultado) matriz [i] := nulo // no pasa del final de la matriz si i = 32 entonces yo-= 1 matriz[i] := resultado resultado := siguiente // fusionar matriz en una sola lista resultado: = nulo para (i = 0; i < 32; i += 1) hacer resultado: = fusionar (matriz [i], resultado) resultado de retorno

Implementación de arriba hacia abajo en un estilo declarativo

Pseudocódigo similar a Haskell , que muestra cómo se puede implementar la clasificación por fusión en dicho lenguaje utilizando construcciones e ideas de programación funcional .

merge_sort :: [ a ] ​​-> [ a ] ​​merge_sort ( [] ) = [] merge_sort ([ x ]) = [ x ] merge_sort ( xs ) = fusionar ( merge_sort ( izquierda ), merge_sort ( derecha )) donde ( izquierda , derecha ) = dividir ( xs , longitud ( xs ) / 2 ) fusionar :: ([ a ], [ a ]) -> [ a ] fusionar ( [] , xs ) = xs fusionar ( xs , [] ) = xs fusionar ( x : xs , y : ys ) | si x ≤ y = x : fusionar ( xs , y : ys ) | else = y : fusionar ( x : xs , ys )                                                          

Análisis

Un algoritmo de clasificación por fusión recursivo que se utiliza para ordenar una matriz de 7 valores enteros. Estos son los pasos que seguiría un humano para emular la ordenación por combinación (de arriba hacia abajo).

Al ordenar n objetos, la ordenación por fusión tiene un rendimiento promedio y en el peor de los casos de comparaciones O ( n  log  n ). Si el tiempo de ejecución (número de comparaciones) de la ordenación por fusión para una lista de longitud n es T ( n ), entonces la relación de recurrencia T ( n ) = 2 T ( n /2) + n se sigue de la definición del algoritmo ( aplicar el algoritmo a dos listas de la mitad del tamaño de la lista original y agregar los n pasos tomados para fusionar las dos listas resultantes). ^[4] La forma cerrada se deriva del teorema maestro de recurrencias de divide y vencerás .

El número de comparaciones realizadas mediante clasificación por fusión en el peor de los casos viene dado por los números de clasificación . Estos números son iguales o ligeramente menores que ( n  ⌈ lg  n ⌉ − 2 ^{⌈lg  n ⌉} + 1), que está entre ( n  lg  n − n + 1 ) y ( n  lg  n + n + O(lg  n ) ). ^[5] El mejor caso de ordenación por fusión requiere aproximadamente la mitad de iteraciones que el peor caso. ^[6]

Para n grande y una lista de entrada ordenada aleatoriamente, el número esperado (promedio) de comparaciones del ordenamiento combinado se acerca a α · n menos que en el peor de los casos, donde ${\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.}$

En el peor de los casos, la ordenación por combinación utiliza aproximadamente un 39 % menos de comparaciones que la ordenación rápida en su caso promedio y, en términos de movimientos, la complejidad del peor caso de la ordenación por combinación es O ( n  log  n ), la misma complejidad que el mejor caso de la ordenación rápida. ^[6]

La clasificación por combinación es más eficiente que la clasificación rápida para algunos tipos de listas si solo se puede acceder de manera eficiente a los datos que se van a ordenar de manera secuencial y, por lo tanto, es popular en lenguajes como Lisp , donde las estructuras de datos a las que se accede secuencialmente son muy comunes. A diferencia de algunas implementaciones (eficientes) de clasificación rápida, la clasificación por combinación es una clasificación estable.

La implementación más común de ordenación por combinación no ordena en su lugar; ^[7] por lo tanto, el tamaño de la memoria de la entrada debe asignarse para que se almacene la salida ordenada (consulte a continuación las variaciones que necesitan solo n /2 espacios adicionales).

Orden de fusión natural

Una ordenación por combinación natural es similar a una ordenación por combinación ascendente, excepto que se explotan las ejecuciones (secuencias ordenadas) que ocurren naturalmente en la entrada. Se pueden explotar ejecuciones tanto monótonas como bitónicas (alternando arriba/abajo), siendo las listas (o equivalentemente cintas o archivos) estructuras de datos convenientes (utilizadas como colas FIFO o pilas LIFO ). ^[8] En la clasificación de combinación ascendente, el punto de partida supone que cada ejecución tiene una longitud de un elemento. En la práctica, los datos de entrada aleatorios tendrán muchas ejecuciones cortas que simplemente estarán ordenadas. En el caso típico, es posible que la clasificación de combinación natural no necesite tantas pasadas porque hay menos ejecuciones para combinar. En el mejor de los casos, la entrada ya está ordenada (es decir, es una ejecución), por lo que la clasificación por combinación natural sólo necesita realizar una pasada a través de los datos. En muchos casos prácticos, existen ejecuciones naturales largas y, por esa razón, se aprovecha la ordenación por fusión natural como el componente clave de Timsort . Ejemplo:

Inicio : 3 4 2 1 7 5 8 9 0 6Seleccione carreras: (3 4)(2)(1 7)(5 8 9)(0 6)Fusionar : (2 3 4)(1 5 7 8 9)(0 6)Fusionar : (1 2 3 4 5 7 8 9)(0 6)Fusionar: (0 1 2 3 4 5 6 7 8 9)

Formalmente, se dice que la clasificación de fusión natural es Ejecuciones óptimas, donde es el número de ejecuciones en , menos uno. ${\displaystyle {\mathtt {Runs}}(L)}$ ${\displaystyle L}$

Las clasificaciones de selección de reemplazo de torneos se utilizan para recopilar las ejecuciones iniciales para algoritmos de clasificación externos.

Clasificación de combinación de ping-pong

En lugar de fusionar dos bloques a la vez, una combinación de ping-pong fusiona cuatro bloques a la vez. Los cuatro bloques ordenados se fusionan simultáneamente en el espacio auxiliar en dos bloques ordenados, luego los dos bloques ordenados se fusionan nuevamente en la memoria principal. Al hacerlo, se omite la operación de copia y se reduce el número total de movimientos a la mitad. WikiSort realizó una de las primeras implementaciones de dominio público de una combinación de cuatro a la vez en 2014; más tarde ese año, el método se describió como una optimización para la clasificación con paciencia y se denominó combinación de ping-pong. ^{[9] [10]} Quadsort implementó el método en 2020 y lo denominó combinación cuádruple. ^[11]

Clasificación por combinación in situ

Un inconveniente de la ordenación por combinación, cuando se implementa en matrices, es su requisito de memoria de trabajo O ( n ) . Se han sugerido varios métodos para reducir la memoria o hacer que la ordenación por combinación se realice completamente en el lugar :

• Kronrod (1969) sugirió una versión alternativa de ordenación por fusión que utiliza espacio adicional constante.
• Katajainen et al. presentar un algoritmo que requiere una cantidad constante de memoria de trabajo: suficiente espacio de almacenamiento para contener un elemento de la matriz de entrada y espacio adicional para contener punteros O (1) en la matriz de entrada. Logran un límite de tiempo O ( n log n ) con pequeñas constantes, pero su algoritmo no es estable. ^[12]
• Se han realizado varios intentos para producir un algoritmo de combinación in situ que pueda combinarse con una clasificación de combinación estándar (de arriba hacia abajo o de abajo hacia arriba) para producir una clasificación de combinación in situ. En este caso, la noción de "in situ" se puede relajar para significar "tomar espacio de pila logarítmico", porque la ordenación por combinación estándar requiere esa cantidad de espacio para su propio uso de pila. Fue demostrado por Geffert et al. que la fusión estable in situ es posible en O ( n log n ) tiempo usando una cantidad constante de espacio temporal, pero su algoritmo es complicado y tiene factores constantes altos: fusionar matrices de longitud n y m puede tomar 5 n + 12 m + o ( m ) se mueve. ^[13] Este alto factor constante y complicado algoritmo local se hizo más simple y fácil de entender. Bing-Chao Huang y Michael A. Langston ^[14] presentaron un algoritmo de tiempo lineal sencillo y práctico de fusión in situ para fusionar una lista ordenada utilizando una cantidad fija de espacio adicional. Ambos han utilizado el trabajo de Kronrod y otros. Se fusiona en un tiempo lineal y un espacio extra constante. El algoritmo requiere un poco más de tiempo promedio que los algoritmos de clasificación por fusión estándar, libres de explotar O(n) celdas de memoria extra temporales, en menos de un factor de dos. Aunque el algoritmo es mucho más rápido en la práctica, también es inestable para algunas listas. Pero utilizando conceptos similares, han podido solucionar este problema. Otros algoritmos locales incluyen SymMerge, que toma O (( n + m ) log ( n + m )) tiempo en total y es estable. ^[15] Conectar un algoritmo de este tipo a la ordenación por fusión aumenta su complejidad hasta el nivel no lineal , pero aún cuasilineal , O ( n (log n ) ² ) .
• Muchas aplicaciones de clasificación externa utilizan una forma de clasificación por combinación en la que la entrada se divide en un mayor número de sublistas, idealmente hasta un número en el que al fusionarlas el conjunto de páginas actualmente procesadas encaje en la memoria principal.
• Una variante de combinación moderna, estable, lineal e in situ es la ordenación de combinación en bloques , que crea una sección de valores únicos para usar como espacio de intercambio.
• La sobrecarga de espacio se puede reducir a sqrt( n ) mediante búsquedas y rotaciones binarias. ^[16] Este método lo emplean la biblioteca STL de C++ y quadsort. ^[11]
• Una alternativa para reducir la copia en múltiples listas es asociar un nuevo campo de información con cada clave (los elementos en m se llaman claves). Este campo se utilizará para vincular las claves y cualquier información asociada en una lista ordenada (una clave y su información relacionada se denomina registro). Luego, la fusión de las listas ordenadas continúa cambiando los valores de los enlaces; no es necesario mover ningún registro. Un campo que contiene sólo un vínculo generalmente será más pequeño que un registro completo, por lo que también se utilizará menos espacio. Esta es una técnica de clasificación estándar, que no se limita a la clasificación por combinación.
• Una forma sencilla de reducir la sobrecarga de espacio a n /2 es mantener la izquierda y la derecha como una estructura combinada, copiar solo la parte izquierda de m en el espacio temporal y dirigir la rutina de fusión para colocar la salida fusionada en m . Con esta versión es mejor asignar el espacio temporal fuera de la rutina de fusión , de modo que sólo se necesite una asignación. La copia excesiva mencionada anteriormente también se mitiga, ya que el último par de líneas antes de la declaración de resultado de retorno (función de fusión en el pseudocódigo anterior) se vuelven superfluas.

Usar con unidades de cinta

Los algoritmos de tipo de clasificación por fusión permitieron clasificar grandes conjuntos de datos en las primeras computadoras que tenían pequeñas memorias de acceso aleatorio según los estándares modernos. Los registros se almacenaban en cinta magnética y se procesaban en bancos de unidades de cinta magnética, como estos IBM 729 .

Es práctico ejecutar una ordenación por combinación externa usando unidades de disco o cinta cuando los datos que se van a ordenar son demasiado grandes para caber en la memoria . La clasificación externa explica cómo se implementa la clasificación por combinación con unidades de disco. Un tipo típico de unidad de cinta utiliza cuatro unidades de cinta. Todas las E/S son secuenciales (excepto los rebobinados al final de cada pasada). Una implementación mínima puede funcionar con sólo dos buffers de registro y algunas variables de programa.

Al nombrar las cuatro unidades de cinta como A, B, C, D, con los datos originales en A y usar solo dos buffers de registro, el algoritmo es similar a la implementación ascendente, usando pares de unidades de cinta en lugar de matrices en la memoria. El algoritmo básico se puede describir de la siguiente manera:

1. Fusionar pares de registros de A; escribir sublistas de dos registros alternativamente en C y D.
2. Fusionar sublistas de dos registros de C y D en sublistas de cuatro registros; escribiéndolos alternativamente en A y B.
3. Fusionar sublistas de cuatro registros de A y B en sublistas de ocho registros; escribiéndolos alternativamente en C y D
4. Repita hasta que tenga una lista que contenga todos los datos, ordenados en log ₂ ( n ) pases.

En lugar de comenzar con ejecuciones muy cortas, generalmente se usa un algoritmo híbrido , donde el pase inicial leerá muchos registros en la memoria, realizará una clasificación interna para crear una ejecución larga y luego distribuirá esas ejecuciones largas en el conjunto de salida. El paso evita muchos pases tempranos. Por ejemplo, una clasificación interna de 1024 registros guardará nueve pases. El tipo interno suele ser grande porque tiene ese beneficio. De hecho, existen técnicas que pueden hacer que las ejecuciones iniciales duren más que la memoria interna disponible. Uno de ellos, el 'quitanieves' de Knuth (basado en un min-heap binario ), genera ejecuciones dos veces más largas (en promedio) que el tamaño de memoria utilizada. ^[17]

Con algo de sobrecarga, el algoritmo anterior se puede modificar para utilizar tres cintas. El tiempo de ejecución O ( n log n ) también se puede lograr usando dos colas , o una pila y una cola, o tres pilas. En la otra dirección, usando k > dos cintas (y O ( k ) elementos en la memoria), podemos reducir el número de operaciones de cinta en O (log k ) veces usando una combinación de k/2 vías .

Una clasificación de combinación más sofisticada que optimiza el uso de la unidad de cinta (y disco) es la clasificación de combinación polifásica .

Optimización del ordenamiento combinado

Clasificación de combinación en mosaico aplicada a una matriz de números enteros aleatorios. El eje horizontal es el índice de la matriz y el eje vertical es el número entero.

En las computadoras modernas, la localidad de referencia puede ser de suma importancia en la optimización del software , porque se utilizan jerarquías de memoria multinivel . Se han propuesto versiones con reconocimiento de caché del algoritmo de clasificación por fusión, cuyas operaciones se han elegido específicamente para minimizar el movimiento de páginas dentro y fuera de la memoria caché de una máquina. Por ejemplo, elEl algoritmo de ordenación por combinación en mosaico detiene la partición de subarreglos cuando se alcanzan subarreglos de tamaño S, donde S es el número de elementos de datos que caben en el caché de una CPU. Cada uno de estos subarreglos se ordena con un algoritmo de clasificación local, como laordenación por inserción, para desalentar los intercambios de memoria, y luego la ordenación por fusión normal se completa de forma recursiva estándar. Este algoritmo ha demostrado un mejor rendimiento^{[ ejemplo necesario ]}en máquinas que se benefician de la optimización de la caché. (LaMarca y Ladner 1997)

Ordenación por fusión en paralelo

La ordenación por fusión es un buen paralelismo debido al uso del método de divide y vencerás . A lo largo de los años se han desarrollado varias variantes paralelas diferentes del algoritmo. Algunos algoritmos de clasificación de fusión paralela están fuertemente relacionados con el algoritmo de fusión secuencial de arriba hacia abajo, mientras que otros tienen una estructura general diferente y utilizan el método de fusión K-way .

Combinar ordenación con recursividad paralela

El procedimiento de clasificación por fusión secuencial se puede describir en dos fases, la fase de división y la fase de fusión. El primero consta de muchas llamadas recursivas que realizan repetidamente el mismo proceso de división hasta que las subsecuencias se ordenan trivialmente (contienen uno o ningún elemento). Un enfoque intuitivo es la paralelización de esas llamadas recursivas. ^[18] El siguiente pseudocódigo describe la ordenación por combinación con recursividad paralela utilizando las palabras clave fork y join :

// Ordena los elementos de bajo a alto (exclusivo) de la matriz A. El algoritmo mergesort(A, lo, alto) es  si lo+1 < alto entonces // Dos o más elementos. medio := ⌊(lo + hola) / 2⌋ mergesort de bifurcación (A, lo, mid) mergesort(A, medio, hola) unirse fusionar (A, bajo, medio, hola)

Este algoritmo es la modificación trivial de la versión secuencial y no se paraleliza bien. Por tanto, su aceleración no es muy impresionante. Tiene una duración de , lo cual es solo una mejora en comparación con la versión secuencial (consulte Introducción a los algoritmos ). Esto se debe principalmente al método de fusión secuencial, ya que es el cuello de botella de las ejecuciones paralelas. ${\displaystyle \Theta (n)}$ ${\displaystyle \Theta (\log n)}$

Combinar ordenación con combinación paralela

Se puede lograr un mejor paralelismo utilizando un algoritmo de fusión paralela . Cormen et al. presenta una variante binaria que fusiona dos subsecuencias ordenadas en una secuencia de salida ordenada. ^[18]

En una de las secuencias (la más larga si tiene una longitud desigual), se selecciona el elemento del índice medio. Su posición en la otra secuencia se determina de tal manera que esta secuencia permanecería ordenada si este elemento se insertara en esta posición. Por lo tanto, se sabe cuántos elementos más de ambas secuencias son más pequeños y se puede calcular la posición del elemento seleccionado en la secuencia de salida. Para las secuencias parciales de los elementos más pequeños y más grandes creados de esta manera, el algoritmo de fusión se ejecuta nuevamente en paralelo hasta que se alcanza el caso base de la recursividad.

El siguiente pseudocódigo muestra el método de clasificación por fusión paralela modificado utilizando el algoritmo de fusión paralela (adoptado de Cormen et al.).

/** * A: matriz de entrada * B: matriz de salida * lo: límite inferior * hola: límite superior * apagado: compensación */algoritmo paraleloMergesort(A, lo, hola, B, apagado) es len := hola - lo + 1 si len == 1 entonces B[apagado] := A[lo] de lo contrario, deje que T[1..len] sea una nueva matriz medio := ⌊(lo + hola) / 2⌋ medio' := medio - lo + 1 bifurcación paralelaMergesort(A, lo, mid, T, 1) paraleloMergesort(A, medio + 1, hola, T, medio' + 1) unirse  paraleloMerge(T, 1, mid', mid' + 1, len, B, off)

Para analizar una relación de recurrencia para el peor de los casos, las llamadas recursivas de paraleloMergesort deben incorporarse solo una vez debido a su ejecución en paralelo, obteniendo

$${\displaystyle T_{\infty }^{\text{sort}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+T_{\infty }^{\text{merge}}(n)=T_{\infty }^{\text{sort}}\left({\frac {n}{2}}\right)+\Theta \left(\log(n)^{2}\right).}$$

Para obtener información detallada sobre la complejidad del procedimiento de fusión paralela, consulte Algoritmo de fusión .

La solución de esta recurrencia viene dada por

$${\displaystyle T_{\infty }^{\text{sort}}=\Theta \left(\log(n)^{3}\right).}$$

Este algoritmo de fusión paralela alcanza un paralelismo de , que es mucho mayor que el paralelismo del algoritmo anterior. Esta clasificación puede funcionar bien en la práctica cuando se combina con una clasificación secuencial rápida y estable, como la clasificación por inserción , y una combinación secuencial rápida como caso base para fusionar matrices pequeñas. ^[19] ${\textstyle \Theta \left({\frac {n}{(\log n)^{2}}}\right)}$

Clasificación de fusión multidireccional paralela

Parece arbitrario restringir los algoritmos de clasificación por fusión a un método de fusión binario, ya que normalmente hay p > 2 procesadores disponibles. Un mejor enfoque puede ser utilizar un método de fusión K-way , una generalización de la fusión binaria, en la que se fusionan secuencias ordenadas. Esta variante de combinación es muy adecuada para describir un algoritmo de clasificación en una PRAM . ^{[20] [21]} ${\displaystyle k}$

Idea básica

El proceso de fusión multidireccional paralelo en cuatro procesadores para . ${\displaystyle t_{0}}$ ${\displaystyle t_{3}}$

Dada una secuencia de elementos sin clasificar, el objetivo es ordenar la secuencia con los procesadores disponibles . Estos elementos se distribuyen equitativamente entre todos los procesadores y se clasifican localmente mediante un algoritmo de clasificación secuencial . Por tanto, la secuencia consta de secuencias ordenadas de longitud . Para simplificar, sea un múltiplo de , de modo que para . ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle S_{1},...,S_{p}}$ ${\textstyle \lceil {\frac {n}{p}}\rceil }$ ${\displaystyle n}$ ${\displaystyle p}$ ${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$ ${\displaystyle i=1,...,p}$

Estas secuencias se utilizarán para realizar una selección multisecuencia/selección divisoria. Para , el algoritmo determina los elementos divisores con rango global . Luego, las posiciones correspondientes de en cada secuencia se determinan con búsqueda binaria y, por lo tanto, se dividen en subsecuencias con . ${\displaystyle j=1,...,p}$ ${\displaystyle v_{j}}$ ${\textstyle k=j{\frac {n}{p}}}$ ${\displaystyle v_{1},...,v_{p}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle p}$ ${\displaystyle S_{i,1},...,S_{i,p}}$ ${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(v_{j})\}}$

Además, los elementos de están asignados al procesador , es decir, todos los elementos entre rango y rango , que se distribuyen por todo . Por tanto, cada procesador recibe una secuencia de secuencias ordenadas. El hecho de que el rango de los elementos divisores se haya elegido globalmente proporciona dos propiedades importantes: por un lado, se eligió de modo que cada procesador pueda seguir operando con los elementos después de la asignación. El algoritmo tiene un equilibrio de carga perfecto . Por otro lado, todos los elementos del procesador son menores o iguales que todos los elementos del procesador . Por lo tanto, cada procesador realiza la fusión p -way localmente y así obtiene una secuencia ordenada a partir de sus subsecuencias. Debido a la segunda propiedad, no es necesario realizar más p -way-merge, los resultados sólo deben juntarse en el orden del número de procesador. ${\displaystyle S_{1,i},...,S_{p,i}}$ ${\displaystyle i}$ ${\textstyle (i-1){\frac {n}{p}}}$ ${\textstyle i{\frac {n}{p}}}$ ${\displaystyle S_{i}}$ ${\displaystyle k}$ ${\displaystyle v_{i}}$ ${\displaystyle k}$ ${\textstyle n/p}$ ${\displaystyle i}$ ${\displaystyle i+1}$

Selección multisecuencia

En su forma más simple, dadas secuencias ordenadas distribuidas uniformemente en procesadores y un rango , la tarea es encontrar un elemento con un rango global en la unión de las secuencias. Por lo tanto, esto se puede usar para dividir cada uno en dos partes en un índice divisor , donde la parte inferior contiene solo elementos que son más pequeños que , mientras que los elementos más grandes que se encuentran en la parte superior. ${\displaystyle p}$ ${\displaystyle S_{1},...,S_{p}}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle k}$ ${\displaystyle S_{i}}$ ${\displaystyle l_{i}}$ ${\displaystyle x}$ ${\displaystyle x}$

El algoritmo secuencial presentado devuelve los índices de las divisiones en cada secuencia, por ejemplo, los índices en secuencias que tienen una clasificación global menor que y . ^[22] ${\displaystyle l_{i}}$ ${\displaystyle S_{i}}$ ${\displaystyle S_{i}[l_{i}]}$ ${\displaystyle k}$ ${\displaystyle \mathrm {rank} \left(S_{i}[l_{i}+1]\right)\geq k}$

algoritmo msSelect(S: Matriz de secuencias ordenadas [S_1,..,S_p], k: int) es  para i = 1 a p do (l_i, r_i) = (0, |S_i|-1) mientras exista i: l_i < r_i do// elige el elemento pivote en S_j[l_j], .., S_j[r_j], elige j aleatorio de manera uniformev := elegirPivote(S, l, r)para i = 1 a p hacer  m_i = binarioSearch(v, S_i[l_i, r_i]) // secuencialmentesi m_1 + ... + m_p >= k entonces // m_1+ ... + m_p es el rango global de v r := m // asignación de vectoresdemás l := metro regresar l

Para el análisis de complejidad se elige el modelo PRAM . Si los datos se distribuyen uniformemente en todos , la ejecución p-fold del método binarioSearch tiene un tiempo de ejecución de . La profundidad de recursividad esperada es la misma que en la selección rápida normal . Por lo tanto, el tiempo de ejecución general esperado es . ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}\left(p\log \left(n/p\right)\right)}$ ${\displaystyle {\mathcal {O}}\left(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log(n))}$ ${\displaystyle {\mathcal {O}}\left(p\log(n/p)\log(n)\right)}$

Aplicado en la clasificación de fusión multidireccional paralela, este algoritmo debe invocarse en paralelo de modo que todos los elementos divisores de clasificación se encuentren simultáneamente. Estos elementos divisores se pueden usar para dividir cada secuencia en partes, con el mismo tiempo de ejecución total de . ${\textstyle i{\frac {n}{p}}}$ ${\displaystyle i=1,..,p}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$

Pseudocódigo

A continuación, se proporciona el pseudocódigo completo del algoritmo de clasificación por fusión multidireccional paralelo. Suponemos que existe una barrera de sincronización antes y después de la selección multisecuencia de modo que cada procesador pueda determinar los elementos de división y la partición de secuencia correctamente.

/** * d: Matriz de elementos sin clasificar * n: Número de elementos * p: Número de procesadores * devolver matriz ordenada */algoritmo paraleloMultiwayMergesort(d: Array, n: int, p: int) es o := new Array[0, n] // la matriz de salida para i = 1 a p se hace en paralelo // cada procesador en paralelo S_i := d[(i-1) * n/p, i * n/p] // Secuencia de longitud n/psort(S_i) // ordenar localmente sincronizarv_i := msSelect([S_1,...,S_p], i * n/p) // elemento con rango global i * n/p sincronizar(S_i,1, ..., S_i,p) := secuencia_partitioning(si, v_1, ..., v_p) // divide s_i en subsecuencias o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // fusionar y asignar a la matriz de salida regresar o

Análisis

En primer lugar, cada procesador clasifica los elementos asignados localmente utilizando un algoritmo de clasificación con complejidad . Después de eso, los elementos divisores deben calcularse a tiempo . Finalmente, cada grupo de divisiones debe fusionarse en paralelo por cada procesador con un tiempo de ejecución que utilice un algoritmo de fusión secuencial p-way . Por lo tanto, el tiempo total de ejecución está dado por ${\displaystyle n/p}$ ${\displaystyle {\mathcal {O}}\left(n/p\;\log(n/p)\right)}$ ${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}(\log(p)\;n/p)}$

${\displaystyle {\mathcal {O}}\left({\frac {n}{p}}\log \left({\frac {n}{p}}\right)+p\log \left({\frac {n}{p}}\right)\log(n)+{\frac {n}{p}}\log(p)\right)}$.

Adaptación y aplicación práctica.

El algoritmo de clasificación por fusión multidireccional es muy escalable gracias a su alta capacidad de paralelización, que permite el uso de muchos procesadores. Esto convierte al algoritmo en un candidato viable para clasificar grandes cantidades de datos, como los procesados ​​en grupos de computadoras . Además, dado que en dichos sistemas la memoria no suele ser un recurso limitante, la desventaja de la complejidad espacial de la clasificación por fusión es insignificante. Sin embargo, en este tipo de sistemas cobran importancia otros factores que no se tienen en cuenta a la hora de modelar en una PRAM . Aquí, se deben considerar los siguientes aspectos: Jerarquía de memoria , cuando los datos no caben en la memoria caché del procesador, o la sobrecarga de comunicación del intercambio de datos entre procesadores, que podría convertirse en un cuello de botella cuando ya no se pueda acceder a los datos a través del espacio compartido. memoria.

Sanders y cols. han presentado en su artículo un algoritmo paralelo síncrono masivo para mergesort multinivel, que divide los procesadores en grupos de tamaño . Todos los procesadores clasifican primero localmente. A diferencia de la clasificación por fusión multidireccional de un solo nivel, estas secuencias luego se dividen en partes y se asignan a los grupos de procesadores apropiados. Estos pasos se repiten recursivamente en esos grupos. Esto reduce la comunicación y, sobre todo, evita problemas con muchos mensajes pequeños. La estructura jerárquica de la red real subyacente se puede utilizar para definir los grupos de procesadores (por ejemplo , bastidores , clústeres ,...). ^[21] ${\displaystyle p}$ ${\displaystyle r}$ ${\displaystyle p'}$ ${\displaystyle r}$

Otras variantes

La clasificación por combinación fue uno de los primeros algoritmos de clasificación en los que se logró una velocidad óptima, y ​​Richard Cole utilizó un algoritmo de submuestreo inteligente para garantizar la combinación O (1). ^[23] Otros algoritmos sofisticados de clasificación paralela pueden lograr los mismos o mejores límites de tiempo con una constante más baja. Por ejemplo, en 1991, David Powers describió una clasificación rápida paralelizada (y una clasificación de base relacionada ) que puede operar en tiempo O (log n ) en una máquina de acceso aleatorio paralela (PRAM) CRCW con n procesadores realizando la partición implícitamente. ^{[24] Powers muestra además que una versión canalizada de} Bitonic Mergesort de Batcher en tiempo O ((log n ) ² ) en una red de clasificación de mariposas es en la práctica más rápida que su clasificación O (log n ) en una PRAM, y proporciona detalles discusión de los gastos generales ocultos en comparación, clasificación por base y en paralelo. ^[25]

Comparación con otros algoritmos de clasificación

Aunque la ordenación en montón tiene los mismos límites de tiempo que la ordenación por fusión, solo requiere Θ(1) espacio auxiliar en lugar del Θ( n ) de ordenación por fusión. En las arquitecturas modernas típicas, las implementaciones eficientes de clasificación rápida generalmente superan la clasificación por fusión para ordenar matrices basadas en RAM. ^{[ cita necesaria ] [26]} Se prefieren las clasificaciones rápidas cuando el tamaño de los datos a ordenar es menor, dado que la complejidad del espacio para la clasificación rápida es O (logn), ayuda a utilizar la localidad de caché mejor que la clasificación por combinación (con complejidad espacial O (n) ). ^[26] Por otro lado, la clasificación por fusión es una clasificación estable y es más eficiente en el manejo de medios secuenciales de acceso lento. La ordenación por combinación es a menudo la mejor opción para ordenar una lista enlazada : en esta situación es relativamente fácil implementar una ordenación por combinación de tal manera que requiera sólo Θ(1) espacio adicional y el lento rendimiento de acceso aleatorio de una lista enlazada. list hace que algunos otros algoritmos (como Quicksort) funcionen mal y otros (como Heapsort) sean completamente imposibles.

A partir de Perl 5.8, la clasificación por combinación es su algoritmo de clasificación predeterminado (era de clasificación rápida en versiones anteriores de Perl). ^[27] En Java , los métodos Arrays.sort() utilizan ordenación por fusión o una ordenación rápida ajustada según los tipos de datos y, para lograr eficiencia en la implementación, cambia a ordenación por inserción cuando se ordenan menos de siete elementos de la matriz. ^[28] El kernel de Linux utiliza clasificación por fusión para sus listas enlazadas. ^[29] Python usa Timsort , otro híbrido optimizado de ordenación por fusión y ordenación por inserción, que se ha convertido en el algoritmo de ordenación estándar en Java SE 7 (para matrices de tipos no primitivos), ^[30] en la plataforma Android , ^[31] y en GNU Octava . ^[32]

Notas

1. Skiena (2008, pág.122)
2. Knuth (1998, pág.158)
3. Katajainen, Jyrki; Träff, Jesper Larsson (marzo de 1997). "Algoritmos y Complejidad". Actas de la 3ª Conferencia Italiana sobre Algoritmos y Complejidad . Congreso Italiano sobre Algoritmos y Complejidad. Apuntes de conferencias sobre informática. vol. 1203. Roma. págs. 217-228. CiteSeerX  10.1.1.86.3154 . doi :10.1007/3-540-62592-5_74. ISBN 978-3-540-62592-6.
4. Cormen et al. (2009, pág. 36)
5. El número del peor caso dado aquí no concuerda con el dado en El arte de la programación informática de Knuth , Vol 3 . La discrepancia se debe a que Knuth analiza una implementación variante de ordenación de fusión que es ligeramente subóptima.
6. Jayalakshmi, N. (2007). Estructura de datos usando C++. Medios de firewall. ISBN 978-81-318-0020-1. OCLC  849900742.
7. Cormen et al. (2009, pág.151)
8. Poderes, David MW; McMahon, Graham B. (1983). "Un compendio de interesantes programas de prólogo". Informe técnico de DCS 8313 (Reporte). Departamento de Ciencias de la Computación, Universidad de Nueva Gales del Sur.
9. "WikiSort. Algoritmo de clasificación rápido y estable que utiliza memoria O (1). Dominio público". GitHub . 14 de abril de 2014.
10. Chandramouli, Badrish; Goldstein, Jonathan (2014). La paciencia es una virtud: revisando la combinación y clasificación en procesadores modernos (PDF) . SIGMOD/PODS.
11. "Quadsort es una clasificación de fusión adaptativa estable sin ramas". GitHub . 8 de junio de 2022.
12. Katajainen, Pasanen y Teuhola (1996)
13. Geffert, Viliam; Katajainen, Jyrki; Pasanen, Tomi (2000). "Fusión in situ asintóticamente eficiente". Informática Teórica . 237 (1–2): 159–181. doi : 10.1016/S0304-3975(98)00162-5 .
14. Huang, Bing-Chao; Langston, Michael A. (marzo de 1988). "Fusión práctica in situ". Comunicaciones de la ACM . 31 (3): 348–352. doi : 10.1145/42392.42403 . S2CID  4841909.
15. Kim, Pok-Son; Kutzner, Arne (2004). "Fusión de almacenamiento mínimo estable mediante comparaciones simétricas". Algoritmos – ESA 2004 . Simposio europeo. Algoritmos. Apuntes de conferencias sobre informática. vol. 3221, págs. 714–723. CiteSeerX 10.1.1.102.4612 . doi :10.1007/978-3-540-30140-0_63. ISBN  978-3-540-23025-0.
16. Kim, Pok-Son; Kutzner, Arne (1 de septiembre de 2003). "Un nuevo método para una fusión in situ eficiente". Actas de la Conferencia del Instituto Coreano de Sistemas Inteligentes : 392–394.
17. Ferragina, Paolo (2009-2019), "5. Clasificación de elementos atómicos" (PDF) , ¡La magia de los algoritmos! , pag. 5-4, archivado (PDF) desde el original el 2021-05-12
18. Cormen et al. (2009, págs. 797–805)
19. Victor J. Duvanenko "Parallel Merge Sort" Diario y blog del Dr. Dobb [1] e implementación de C++ en el repositorio de GitHub [2]
20. Peter Lijadoras; Johannes Singler (2008). "Conferencia Algoritmos paralelos" (PDF) . Consultado el 2 de mayo de 2020 .
21. Axtmann, Michael; Bingmann, Timo; Lijadoras, Peter; Schulz, cristiano (2015). "Práctica clasificación masiva en paralelo". Actas del 27º simposio ACM sobre paralelismo en algoritmos y arquitecturas . págs. 13-23. doi :10.1145/2755573.2755595. ISBN 9781450335881. S2CID  18249978.
22. Peter Sanders (2019). "Conferencia Algoritmos paralelos" (PDF) . Consultado el 2 de mayo de 2020 .
23. Cole, Richard (agosto de 1988). "Clasificación por fusión en paralelo". SIAM J. Computación . 17 (4): 770–785. CiteSeerX 10.1.1.464.7118 . doi :10.1137/0217049. S2CID  2416667. 
24. Poderes, David MW (1991). "Quicksort y Radixsort paralelos con aceleración óptima". Actas de la Conferencia Internacional sobre Tecnologías de Computación Paralela, Novosibirsk . Archivado desde el original el 25 de mayo de 2007.
25. Powers, David MW (enero de 1995). Unificación paralela: complejidad práctica (PDF) . Taller de arquitectura informática de Australasia Universidad de Flinders.
26. Oladipupo, Esaú Taiwo; Abikoye, Oluwakemi Christianah (20 de enero de 2024). "Comparación de ordenación rápida y ordenación por combinación". Ciencia directa . 2020 (2020): 9 - vía Elsevier Science Direct.
27. "Ordenar: documentación de Perl 5 versión 8.8" . Consultado el 23 de agosto de 2020 .
28. coleenp (22 de febrero de 2019). "src/java.base/share/classes/java/util/Arrays.java @ 53904:9c3fe09f69bc". AbiertoJDK .
29. núcleo de Linux /lib/list_sort.c
30. jjb (29 de julio de 2009). "Commit 6804124: Reemplace" mergesort modificado "en java.util.Arrays.sort con timsort". Repositorio del kit de desarrollo Java 7 Hg . Archivado desde el original el 26 de enero de 2018 . Consultado el 24 de febrero de 2011 .
31. "Clase: java.util.TimSort <T>". Documentación JDK de Android . Archivado desde el original el 20 de enero de 2015 . Consultado el 19 de enero de 2015 .
32. "liboctave/util/oct-sort.cc". Repositorio Mercurial del código fuente de Octave . Líneas 23-25 ​​del bloque de comentarios inicial . Consultado el 18 de febrero de 2013 . Código robado en gran parte de listobject.c de Python, que a su vez no tenía encabezado de licencia. Sin embargo, gracias a Tim Peters por las partes del código que estafé.

Referencias

• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.
• Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Práctica ordenación por combinación in situ". Revista Nórdica de Computación . 3 (1): 27–40. CiteSeerX  10.1.1.22.8523 . ISSN  1236-6064. Archivado desde el original el 7 de agosto de 2011 . Consultado el 4 de abril de 2009 .. También es práctico Mergesort in situ. También [3]
• Knuth, Donald (1998). "Sección 5.2.4: Ordenar mediante fusión". Ordenar y buscar . El arte de la programación informática . vol. 3 (2ª ed.). Addison-Wesley. págs. 158-168. ISBN 0-201-89685-0.
• Kronrod, MA (1969). "Algoritmo de pedido óptimo sin campo operativo". Matemáticas soviéticas - Doklady . 10 : 744.
• LaMarca, A.; Ladner, RE (1997). "La influencia de las cachés en el rendimiento de la clasificación". Proc. 8vo Ana. Síntoma ACM-SIAM. Sobre algoritmos discretos (SODA97) : 370–379. CiteSeerX  10.1.1.31.1153 .
• Skiena, Steven S. (2008). "4.5: Mergesort: ordenar por divide y vencerás". El manual de diseño de algoritmos (2ª ed.). Saltador. págs. 120-125. ISBN 978-1-84800-069-8.
• Microsistemas solares. "API de matrices (Java SE 6)" . Consultado el 19 de noviembre de 2007 .
• Oracle Corp. "Matrices (Java SE 10 y JDK 10)" . Consultado el 23 de julio de 2018 .

enlaces externos

• Algoritmos de clasificación animados: clasificación por combinación en Wayback Machine (archivado el 6 de marzo de 2015): demostración gráfica
• Estructuras de datos abiertas - Sección 11.1.1 - Ordenación por combinación, Pat Morin