Combinar ordenación - Merge sort

Combinar ordenación

Un ejemplo de ordenación por combinación. Primero divida la lista en la unidad más pequeña (1 elemento), luego compare cada elemento con la lista adyacente para ordenar y fusionar las dos listas adyacentes. Finalmente, todos los elementos se ordenan y combinan.
Clase	Algoritmo de clasificación
Estructura de datos	Formación
Rendimiento en el peor de los casos	${\ Displaystyle O (n \ log n)}$
Rendimiento en el mejor de los casos	${\ Displaystyle \ Omega (n \ log n)}$variante típica, natural${\ Displaystyle \ Omega (n)}$
Rendimiento medio	${\ Displaystyle \ Theta (n \ log n)}$
Complejidad espacial en el peor de los casos	${\ Displaystyle O (n)}$total con auxiliares, auxiliares con listas enlazadas${\ Displaystyle O (n)}$${\ Displaystyle O (1)}$

En ciencias de la computación , ordenamiento por mezcla (también escrito comúnmente como mergesort ) es una de propósito general eficiente y basada en la comparación algoritmo de ordenación . La mayoría de las implementaciones producen una clasificación estable , lo que significa que el orden de los elementos iguales es el mismo en la entrada y la salida. La ordenación por combinación es un algoritmo de división y conquista que fue inventado por John von Neumann en 1945. Una descripción detallada y un análisis de la ordenación por combinación de abajo hacia arriba apareció en un informe de Goldstine y von Neumann ya en 1948.

Algoritmo

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

1. Divida la lista sin clasificar en n sublistas, cada una de las cuales contiene un elemento (una lista de un elemento se considera ordenada).
2. Fusionar repetidamente sublistas 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 similar a C que usa índices para el algoritmo de clasificación de combinación de arriba hacia abajo que divide de forma recursiva la lista (denominada ejecuciones en este ejemplo) en sublistas hasta que el tamaño de la sublista es 1, luego fusiona 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). Para ayudar a comprender esto, considere una matriz con dos elementos. Los elementos se copian en B [] y luego se vuelven a fusionar en A []. Si hay cuatro elementos, cuando se alcanza la parte inferior del nivel de recursividad, las ejecuciones de un solo elemento de A [] se combinan con B [], y luego, en el siguiente nivel superior de recursividad, esas ejecuciones de dos elementos se combinan en A [ ]. Este patrón continúa con cada nivel de recursividad.

// Array A[] has the items to sort; array B[] is a work array.
void TopDownMergeSort(A[], B[], n)
{
    CopyArray(A, 0, n, B);           // one time copy of A[] to B[]
    TopDownSplitMerge(B, 0, n, A);   // sort data from B[] into A[]
}

// Split A[] into 2 runs, sort both runs into B[], merge both runs from B[] to A[]
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
void TopDownSplitMerge(B[], iBegin, iEnd, A[])
{
    if (iEnd - iBegin <= 1)                     // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    TopDownSplitMerge(A, iBegin,  iMiddle, B);  // sort the left  run
    TopDownSplitMerge(A, iMiddle,    iEnd, B);  // sort the right run
    // merge the resulting runs from array B[] into A[]
    TopDownMerge(B, iBegin, iMiddle, iEnd, A);
}

//  Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1   ].
// Result is            B[ iBegin:iEnd-1   ].
void TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
{
    i = iBegin, j = iMiddle;
 
    // While there are elements in the left or right runs...
    for (k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

void CopyArray(A[], iBegin, iEnd, B[])
{
    for (k = iBegin; k < iEnd; k++)
        B[k] = A[k];
}

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

Implementación de abajo hacia arriba

Ejemplo de código similar a C que usa índices para el algoritmo de clasificación de fusión ascendente que trata la lista como una matriz de n sublistas (llamadas ejecuciones en este ejemplo) de tamaño 1, y fusiona de forma iterativa las sublistas entre dos búferes:

// array A[] has the items to sort; array B[] is a work array
void BottomUpMergeSort(A[], B[], n)
{
    // Each 1-element run in A is already "sorted".
    // Make successively longer sorted runs of length 2, 4, 8, 16... until the whole array is sorted.
    for (width = 1; width < n; width = 2 * width)
    {
        // Array A is full of runs of length width.
        for (i = 0; i < n; i = i + 2 * width)
        {
            // Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
            // or copy A[i:n-1] to B[] ( if (i+width >= n) )
            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
        // Now work array B is full of runs of length 2*width.
        // Copy array B to array A for the next iteration.
        // A more efficient implementation would swap the roles of A and B.
        CopyArray(B, A, n);
        // Now array A is full of runs of length 2*width.
    }
}

//  Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1  ].
void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    // While there are elements in the left or right runs...
    for (k = iLeft; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;    
        }
    } 
}

void CopyArray(B[], A[], n)
{
    for (i = 0; i < n; i++)
        A[i] = B[i];
}

Implementación de arriba hacia abajo usando listas

Pseudocódigo para el algoritmo de clasificación de combinació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 hacia arriba en la cadena de llamadas.

function merge_sort(list m) is
    // Base case. A list of zero or one elements is sorted, by definition.
    if length of m ≤ 1 then
        return m

    // Recursive case. First, divide the list into equal-sized sublists
    // consisting of the first half and second half of the list.
    // This assumes lists start at index 0.
    var left := empty list
    var right := empty list
    for each x with index i in m do
        if i < (length of m)/2 then
            add x to left
        else
            add x to right

    // Recursively sort both sublists.
    left := merge_sort(left)
    right := merge_sort(right)

    // Then merge the now-sorted sublists.
    return merge(left, right)

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

function merge(left, right) is
    var result := empty list

    while left is not empty and right is not empty do
        if first(left) ≤ first(right) then
            append first(left) to result
            left := rest(left)
        else
            append first(right) to result
            right := rest(right)

    // Either left or right may have elements left; consume them.
    // (Only one of the following loops will actually be entered.)
    while left is not empty do
        append first(left) to result
        left := rest(left)
    while right is not empty do
        append first(right) to result
        right := rest(right)
    return result

Implementación de abajo hacia arriba usando listas

Pseudocódigo para el algoritmo de clasificación de fusión ascendente que utiliza una matriz pequeña de tamaño fijo de referencias 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 listas de combinación de arriba hacia abajo, combina 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.

function merge_sort(node head) is
    // return if empty list
    if head = nil then
        return nil
    var node array[32]; initially all nil
    var node result
    var node next
    var int  i
    result := head
    // merge nodes into array
    while result ≠ nil do
        next := result.next;
        result.next := nil
        for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do
            result := merge(array[i], result)
            array[i] := nil
        // do not go past end of array
        if i = 32 then
            i -= 1
        array[i] := result
        result := next
    // merge array into single list
    result := nil
    for (i = 0; i < 32; i += 1) do
        result := merge(array[i], result)
    return result

Orden de fusión natural

Una clasificación de combinación natural es similar a una clasificación de combinación de abajo hacia arriba, excepto que se explotan las ejecuciones naturales (secuencias ordenadas) en la entrada. Se pueden explotar ejecuciones tanto monótonas como bitónicas (alternando arriba / abajo), siendo las listas (o, de manera equivalente, cintas o archivos) estructuras de datos convenientes (utilizadas como colas FIFO o pilas LIFO ). En la clasificación de combinación de abajo hacia arriba, el punto de partida asume 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 se ordenan. 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 de combinación natural solo necesita hacer una pasada a través de los datos. En muchos casos prácticos, existen largas corridas naturales y, por esa razón, el tipo de fusión natural se explota como el componente clave de Timsort . Ejemplo:

Start       :  3  4  2  1  7  5  8  9  0  6
Select runs : (3  4)(2)(1  7)(5  8  9)(0  6)
Merge       : (2  3  4)(1  5  7  8  9)(0  6)
Merge       : (1  2  3  4  5  7  8  9)(0  6)
Merge       : (0  1  2  3  4  5  6  7  8  9)

Formalmente, se dice que la combinación de tipo natural estar ejecuta -optimal, donde es el número de carreras en , menos uno. ${\ displaystyle {\ mathtt {Runs}} (L)}$${\ Displaystyle L}$

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

Análisis

Un algoritmo de clasificación de combinación recursiva que se utiliza para clasificar una matriz de 7 valores enteros. Estos son los pasos que tomaría un humano para emular la ordenación por fusió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 O ( n  log  n ). Si el tiempo de ejecución 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 (aplique el algoritmo a dos listas de la mitad del tamaño de la lista original y agregue los n pasos dados para fusionar las dos listas resultantes). La forma cerrada se deriva del teorema maestro para las recurrencias de divide y vencerás .

El número de comparaciones realizadas por ordenación por combinación en el peor de los casos viene dado por los números de ordenació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 ) ). El mejor caso de Merge sort requiere aproximadamente la mitad de iteraciones que el peor de los casos.

Para n grandes y una lista de entrada ordenada aleatoriamente, fusionar el número esperado (promedio) de comparaciones de la ordenación α · 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 fusión usa 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 ordenación rápida.

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

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

Variantes

Las variantes del tipo de combinación se preocupan principalmente por reducir la complejidad del espacio y el costo de la copia.

Una alternativa simple para 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 combinación para colocar la salida combinada en m . Con esta versión, es mejor asignar el espacio temporal fuera de la rutina de combinación , de modo que solo 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 devuelto ( fusión de funciones en el pseudocódigo anterior) se vuelve superflua.

Un inconveniente de la ordenación por fusión, cuando se implementa en matrices, es su requisito de memoria de trabajo O ( n ) . Se han sugerido varias variantes in situ :

• Katajainen y col. 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 O (1) punteros en la matriz de entrada. Alcanzan un límite de tiempo O ( n log n ) con pequeñas constantes, pero su algoritmo no es estable.
• Se han realizado varios intentos para producir un algoritmo de combinación en el lugar que se puede combinar 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 en el lugar. En este caso, la noción de "en el lugar" se puede relajar para que signifique "tomar espacio de pila logarítmico", porque la clasificación de combinación estándar requiere esa cantidad de espacio para su propio uso de pila. Fue demostrado por Geffert et al. que en el lugar, la fusión estable que es posible en O ( n log n ) tiempo utilizando una cantidad constante de espacio cero, pero su algoritmo es complicada y tiene altos factores constantes: la fusión de matrices de longitud n y m puede tomar 5 n + 12 m + o ( m ) se mueve. Este factor de alta constante y el complicado algoritmo in situ se simplificaron y facilitaron la comprensión. Bing-Chao Huang y Michael A. Langston presentaron una combinación práctica en el lugar de un algoritmo de tiempo lineal sencillo para combinar una lista ordenada utilizando una cantidad fija de espacio adicional. Ambos han utilizado el trabajo de Kronrod y otros. Se fusiona en tiempo lineal y espacio extra constante. El algoritmo toma un poco más de tiempo promedio que los algoritmos estándar de ordenación por fusión, 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 resolver este problema. Otros algoritmos in situ incluyen SymMerge, que toma O (( n + m ) log ( n + m )) tiempo en total y es estable. Conectar un algoritmo de este tipo en una ordenación por fusión aumenta su complejidad al no linealítmico , pero aún cuasilineal , O ( n (log n ) ² ) .
• Una combinación moderna y estable lineal e in situ es la clasificación por combinación de bloques .

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 procede cambiando los valores del enlace; no es necesario mover ningún registro. Un campo que contiene solo un enlace generalmente será más pequeño que un registro completo, por lo que también se usará menos espacio. Esta es una técnica de clasificación estándar, no restringida a la clasificación por combinación.

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 almacenaron en cinta magnética y se procesaron en bancos de unidades de cinta magnética, como estos IBM 729 .

Es práctico ejecutar una clasificación de combinación externa utilizando unidades de disco o cinta cuando los datos que se van a clasificar son demasiado grandes para caber en la memoria . La clasificación externa explica cómo se implementa la clasificación por combinación con las unidades de disco. Un tipo de unidad de cinta típico 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 solo dos búferes de registro y algunas variables de programa.

Nombrando las cuatro unidades de cinta como A, B, C, D, con los datos originales en A y usando solo dos búferes 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éndolas alternativamente en A y B.
3. Fusionar sublistas de cuatro registros de A y B en sublistas de ocho registros; escribiendo estos alternativamente en C y D
4. Repita hasta que tenga una lista que contenga todos los datos, ordenados, en log ₂ ( n ) pasadas.

En lugar de comenzar con ejecuciones muy cortas, generalmente se usa un algoritmo híbrido , donde la pasada inicial leerá muchos registros en la memoria, hará 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, un tipo interno de 1024 registros guardará nueve pasadas. El tipo interno suele ser grande porque tiene ese beneficio. De hecho, existen técnicas que pueden hacer que las ejecuciones iniciales sean más largas que la memoria interna disponible. Uno de ellos, el 'quitanieves' de Knuth (basado en un min-montón binario ), genera ejecuciones dos veces más largas (en promedio) que el tamaño de la memoria utilizada.

Con algo de sobrecarga, el algoritmo anterior se puede modificar para usar tres cintas. El tiempo de ejecución O ( n log n ) también se puede lograr utilizando dos colas , o una pila y una cola, o tres pilas. En la otra dirección, usando k > dos cintas (y elementos O ( k ) 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 .

Un tipo de combinación más sofisticado que optimiza el uso de la unidad de cinta (y disco) es el tipo de combinación polifásica .

Optimización de la ordenación por combinación

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 memoria 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, el El algoritmo de ordenación por fusión en mosaico detiene la partición de subarreglos cuando se alcanzan los subarreglos de tamaño S, donde S es el número de elementos de datos que encajan en la memoria caché de una CPU. Cada uno de estos subarreglos se ordena con un algoritmo de ordenación en el lugar, como elordenamiento por inserción, para desalentar los intercambios de memoria, y el ordenamiento de fusión normal se completa luego de la forma recursiva estándar. Este algoritmo ha demostrado un mejor rendimiento en máquinas que se benefician de la optimización de la caché. (LaMarca y Ladner 1997)

Kronrod (1969) sugirió una versión alternativa del tipo de combinación que usa espacio adicional constante. Este algoritmo se perfeccionó posteriormente. ( Katajainen, Pasanen y Teuhola 1996 )

Además, muchas aplicaciones de clasificación externa utilizan una forma de clasificación por fusión en la que la entrada se divide en un número mayor de sublistas, idealmente en un número para el que fusionarlas todavía hace que el conjunto de páginas procesadas actualmente quepa en la memoria principal.

Orden de fusión en paralelo

La ordenación combinada se paraleliza bien debido al uso del método divide y vencerás . Se han desarrollado varias variantes paralelas diferentes del algoritmo a lo largo de los años. Algunos algoritmos de clasificación de fusión en paralelo están estrechamente 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 de K-way .

Combinar ordenación con recursividad paralela

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

// Sort elements lo through hi (exclusive) of array A.
algorithm mergesort(A, lo, hi) is
    if lo+1 < hi then  // Two or more elements.
        mid := ⌊(lo + hi) / 2⌋
        fork mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        join
        merge(A, lo, mid, hi)

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 un intervalo de , que es solo una mejora en comparación con la versión secuencial (ver 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)}$

Fusionar ordenación con fusión paralela

Se puede lograr un mejor paralelismo mediante el uso de un algoritmo de fusión en paralelo . Cormen y col. presentan una variante binaria que fusiona dos subsecuencias ordenadas en una secuencia de salida ordenada.

En una de las secuencias (la más larga si la longitud es 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 otros elementos 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 de fusión en paralelo modificado utilizando el algoritmo de fusión en paralelo (adoptado de Cormen et al.).

/**
 * A: Input array
 * B: Output array
 * lo: lower bound
 * hi: upper bound
 * off: offset
 */
algorithm parallelMergesort(A, lo, hi, B, off) is
    len := hi - lo + 1
    if len == 1 then
        B[off] := A[lo]
    else let T[1..len] be a new array
        mid := ⌊(lo + hi) / 2⌋ 
        mid' := mid - lo + 1
        fork parallelMergesort(A, lo, mid, T, 1)
        parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
        join 
        parallelMerge(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 paralelMergesort 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 {fusionar}} (n) = T _ {\ infty} ^ {\ text {sort}} \ left ({\ frac {n} {2}} \ right) + \ Theta \ izquierda (\ log (n) ^ {2} \ right).}$$

Para obtener información detallada sobre la complejidad del procedimiento de fusión en paralelo, consulte el algoritmo de fusión .

La solución de esta recurrencia está dada por

$${\ Displaystyle T _ {\ infty} ^ {\ text {sort}} = \ Theta \ left (\ log (n) ^ {3} \ right).}$$

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

Ordenación de combinación de múltiples vías paralela

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

Idea básica

El proceso de fusión múltiple 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 por igual 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 de secuencia múltiple / selección de divisor. Para , el algoritmo determina 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} | rango (v_ {j-1}) <rango (x) \ rango leq (v_ {j}) \}}$

Además, los elementos de están asignados al procesador , es decir, todos los elementos entre rango y rango , que se distribuyen entre todos . Por tanto, cada procesador recibe una secuencia de secuencias ordenadas. El hecho de que el rango de los elementos divisores se eligió globalmente, proporciona dos propiedades importantes: Por un lado, se eligió para que cada procesador aún pueda operar sobre los elementos después de la asignación. El algoritmo tiene una carga perfectamente equilibrada . Por otro lado, todos los elementos del procesador son menores o iguales que todos los elementos del procesador . Por tanto, cada procesador realiza la fusión de vías p localmente y, por tanto, obtiene una secuencia ordenada a partir de sus subsecuencias. Debido a la segunda propiedad, no es necesario realizar más combinaciones de p -way-merge, los resultados solo deben agruparse 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 de secuencia múltiple

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 puede usarse para dividir cada uno en dos partes en un índice de división , 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 tales que tienen un rango global menor que y . ${\ Displaystyle l_ {i}}$${\ Displaystyle S_ {i}}$${\ Displaystyle S_ {i} [l_ {i}]}$${\ Displaystyle k}$${\ Displaystyle \ mathrm {rango} \ left (S_ {i} [l_ {i} +1] \ right) \ geq k}$

algorithm msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) is
    for i = 1 to p do 
	(l_i, r_i) = (0, |S_i|-1)
	
    while there exists i: l_i < r_i do
	// pick Pivot Element in S_j[l_j], .., S_j[r_j], chose random j uniformly
	v := pickPivot(S, l, r)
	for i = 1 to p do 
	    m_i = binarySearch(v, S_i[l_i, r_i]) // sequentially
	if m_1 + ... + m_p >= k then // m_1+ ... + m_p is the global rank of v
	    r := m  // vector assignment
	else
	    l := m 
	
    return l

Para el análisis de complejidad se elige el modelo PRAM . Si los datos se distribuyen uniformemente entre todos , la ejecución p-fold del método binarySearch tiene un tiempo de ejecución de . La profundidad de recursividad esperada es como en la selección rápida ordinaria . Por lo tanto, el tiempo de ejecución total 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 ( norte))}$${\ Displaystyle {\ mathcal {O}} \ left (p \ log (n / p) \ log (n) \ right)}$

Aplicado en la clasificación de fusión de múltiples vías en paralelo, este algoritmo debe invocarse en paralelo de manera que todos los elementos divisores de rango para 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 de fusión de múltiples vías en paralelo. Suponemos que hay una sincronización de barrera antes y después de la selección de secuencia múltiple, de modo que cada procesador puede determinar los elementos de división y la partición de secuencia correctamente.

/**
 * d: Unsorted Array of Elements
 * n: Number of Elements
 * p: Number of Processors
 * return Sorted Array
 */
algorithm parallelMultiwayMergesort(d : Array, n : int, p : int) is
    o := new Array[0, n]                         // the output array
    for i = 1 to p do in parallel                // each processor in parallel
        S_i := d[(i-1) * n/p, i * n/p] 	         // Sequence of length n/p
	sort(S_i)                                // sort locally
        synch
	v_i := msSelect([S_1,...,S_p], i * n/p)          // element with global rank i * n/p
        synch
	(S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // split s_i into subsequences
	    
	o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i)  // merge and assign to output array
	
    return 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 mediante el uso de un algoritmo secuencial de combinación de vías p . Por lo tanto, el tiempo de ejecución total viene 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}} \ derecha) \ log (n) + {\ frac {n} {p}} \ log (p) \ derecha)}$.

Adaptación y aplicación prácticas

El algoritmo de clasificación de combinación de múltiples vías es muy escalable gracias a su alta capacidad de paralelización, que permite el uso de muchos procesadores. Esto hace que el algoritmo sea un candidato viable para clasificar grandes cantidades de datos, como los procesados ​​en grupos de computadoras . Además, dado que en tales sistemas la memoria no suele ser un recurso limitante, la desventaja de la complejidad del espacio del tipo de combinación es insignificante. Sin embargo, otros factores se vuelven importantes en dichos sistemas, que no se tienen en cuenta al modelar en un PRAM . Aquí, se deben considerar los siguientes aspectos: la jerarquía de la memoria , cuando los datos no encajan en la caché de los procesadores, 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 puede acceder a los datos a través de la memoria compartida. memoria.

Sanders y col. han presentado en su artículo un algoritmo paralelo síncrono masivo para la ordenación por fusión multinivel y de varias vías, que divide los procesadores en grupos de tamaño . Todos los procesadores se clasifican primero localmente. A diferencia del mergesort de múltiples vías de un solo nivel, estas secuencias se dividen en partes y se asignan a los grupos de procesadores apropiados. Estos pasos se repiten de forma recursiva en esos grupos. Esto reduce la comunicación y especialmente 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 , racks , clústeres , ...). ${\ 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, con Richard Cole utilizando un algoritmo de submuestreo inteligente para garantizar la combinación O (1). Otros algoritmos sofisticados de clasificación en paralelo pueden lograr los mismos o mejores límites de tiempo con una constante más baja. Por ejemplo, en 1991 David Powers describió una ordenación rápida paralelizada (y una ordenación de base relacionada ) que puede operar en tiempo O (log n ) en una máquina CRCW de acceso aleatorio paralelo (PRAM) con n procesadores realizando particiones implícitamente. Poderes muestra además que una versión pipeline de la Dosificadores bitónica por fusión en O ((log n ) ² ) el tiempo en una mariposa de clasificación de la red es en la práctica realmente más rápido que su O (log n ) tipo en un cochecito de niño, y proporciona una discusión detallada de la gastos generales ocultos en comparación, ordenación en base y en paralelo.

Comparación con otros algoritmos de ordenación

Aunque heapsort tiene los mismos límites de tiempo que la ordenación por combinación, solo requiere espacio auxiliar Θ (1) en lugar de Θ ( n ) de la ordenación por combinación . En las arquitecturas modernas típicas, las implementaciones eficientes de ordenación rápida generalmente superan a la ordenación por fusión para ordenar matrices basadas en RAM. 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 vinculada : en esta situación, es relativamente fácil implementar una ordenación por combinación de tal manera que solo requiere Θ (1) espacio adicional y el rendimiento de acceso aleatorio lento de una lista vinculada. list hace que algunos otros algoritmos (como quicksort) funcionen mal y otros (como heapsort) completamente imposibles.

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

Notas

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). "Mergesort práctico en el lugar" . 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: Clasificación por fusión". Clasificación y búsqueda . El arte de la programación informática . 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 los cachés en el rendimiento de la clasificación". Proc. 8th Ann. ACM-SIAM Symp. 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.
• Sun Microsystems. "Arrays API (Java SE 6)" . Consultado el 19 de noviembre de 2007 .
• Oracle Corp. "Arrays (Java SE 10 y JDK 10)" . Consultado el 23 de julio de 2018 .

enlaces externos

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