python - recursive - Explicación de Merge Sort para Dummies

mergesort c++ codigo

Question

Encontré este código en línea:

def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

def mergesort(list):
    if len(list) < 2:
        return list
    middle = len(list) / 2
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])
    return merge(left, right)

Funciona al 100% cuando lo ejecuto. Simplemente no entiendo cómo funciona la ordenación de combinación o cómo la función recursiva puede ordenar correctamente una izquierda y una derecha.

Answer 1

Como lo explica el artículo de Wikipedia , hay muchas formas valiosas de lograr una clasificación de fusión. La forma de lograr una fusión también depende de la colección de cosas que se fusionarán, ciertas colecciones que permiten ciertas herramientas que la colección tiene a su disposición.

No voy a responder a esta pregunta usando Python, simplemente porque no puedo escribirla; Sin embargo, una parte del algoritmo de "ordenamiento de fusión" parece estar realmente en el centro de la cuestión, en general. Un recurso que me ayudó es la webpage del KITE, bastante anticuada, sobre el algoritmo (escrita por un profesor), simplemente porque el autor del contenido elimina los identificadores significativos para el contexto.

Mi respuesta se deriva de este recurso.

Recuerde, los algoritmos de clasificación combinada funcionan desarmando la colección suministrada y luego uniendo cada una de las piezas individuales de nuevo, comparando las piezas entre sí a medida que la colección se reconstruye.

Aquí está el "código" (busque el "violín" de Java):

public class MergeSort {

/**
 * @param a     the array to divide
 * @param low   the low INDEX of the array
 * @param high  the high INDEX of the array
 */
public void divide (int[] a, int low, int high, String hilo) {


    /* The if statement, here, determines whether the array has at least two elements (more than one element). The
     * "low" and "high" variables are derived from the bounds of the array "a". So, at the first call, this if 
     * statement will evaluate to true; however, as we continue to divide the array and derive our bounds from the 
     * continually divided array, our bounds will become smaller until we can no longer divide our array (the array 
     * has one element). At this point, the "low" (beginning) and "high" (end) will be the same. And further calls 
     * to the method will immediately return. 
     * 
     * Upon return of control, the call stack is traversed, upward, and the subsequent calls to merge are made as each 
     * merge-eligible call to divide() resolves
     */
    if (low < high) {
        String source = hilo;
        // We now know that we can further divide our array into two equal parts, so we continue to prepare for the division 
        // of the array. REMEMBER, as we progress in the divide function, we are dealing with indexes (positions)

        /* Though the next statement is simple arithmetic, understanding the logic of the statement is integral. Remember, 
         * at this juncture, we know that the array has more than one element; therefore, we want to find the middle of the 
         * array so that we can continue to "divide and conquer" the remaining elements. When two elements are left, the
         * result of the evaluation will be "1". And the element in the first position [0] will be taken as one array and the
         * element at the remaining position [1] will be taken as another, separate array.
         */
        int middle = (low + high) / 2;

        divide(a, low, middle, "low");
        divide(a, middle + 1, high, "high");


        /* Remember, this is only called by those recursive iterations where the if statement evaluated to true. 
         * The call to merge() is only resolved after program control has been handed back to the calling method. 
         */
        merge(a, low, middle, high, source);
    }
}


public void merge (int a[], int low, int middle, int high, String source) {
// Merge, here, is not driven by tiny, "instantiated" sub-arrays. Rather, merge is driven by the indexes of the 
// values in the starting array, itself. Remember, we are organizing the array, itself, and are (obviously
// using the values contained within it. These indexes, as you will see, are all we need to complete the sort.  

    /* Using the respective indexes, we figure out how many elements are contained in each half. In this 
     * implementation, we will always have a half as the only way that merge can be called is if two
     * or more elements of the array are in question. We also create to "temporary" arrays for the 
     * storage of the larger array''s elements so we can "play" with them and not propogate our 
     * changes until we are done. 
     */
    int first_half_element_no       = middle - low + 1;
    int second_half_element_no      = high - middle;
    int[] first_half                = new int[first_half_element_no];
    int[] second_half               = new int[second_half_element_no];

    // Here, we extract the elements. 
    for (int i = 0; i < first_half_element_no; i++) {  
        first_half[i] = a[low + i]; 
    }

    for (int i = 0; i < second_half_element_no; i++) {  
        second_half[i] = a[middle + i + 1]; // extract the elements from a
    }

    int current_first_half_index = 0;
    int current_second_half_index = 0;
    int k = low;


    while (current_first_half_index < first_half_element_no || current_second_half_index < second_half_element_no) {

        if (current_first_half_index >= first_half_element_no) {
            a[k++] = second_half[current_second_half_index++];
            continue;
        }

        if (current_second_half_index >= second_half_element_no) {
            a[k++] = first_half[current_first_half_index++];
            continue;
        }

        if (first_half[current_first_half_index] < second_half[current_second_half_index]) {
            a[k++] = first_half[current_first_half_index++];
        } else {
            a[k++] = second_half[current_second_half_index++];
        }
    }
}

También tengo una versión, here , que imprimirá información útil y proporcionará una representación más visual de lo que está pasando arriba. El resaltado de sintaxis también es mejor, si eso es útil.

Answer 2

Creo que la clave para entender el orden de fusión es entender el siguiente principio: lo llamaré el principio de fusión:

Dadas dos listas separadas A y B ordenadas de menor a mayor, construya una lista C comparando repetidamente el menor valor de A con el menor valor de B, eliminando el menor valor y agregándolo a C. Cuando una lista se agota, agregue los elementos restantes en la otra lista en C en orden. La lista C es entonces también una lista ordenada.

Si lo resuelves a mano varias veces, verás que es correcto. Por ejemplo:

A = 1, 3
B = 2, 4
C = 
min(min(A), min(B)) = 1

A = 3
B = 2, 4
C = 1
min(min(A), min(B)) = 2

A = 3
B = 4
C = 1, 2
min(min(A), min(B)) = 3

A = 
B = 4
C = 1, 2, 3

Ahora A está agotado, así que extienda C con los valores restantes de B:

C = 1, 2, 3, 4

El principio de fusión también es fácil de probar. El valor mínimo de A es menor que todos los demás valores de A, y el valor mínimo de B es menor que todos los demás valores de B. Si el valor mínimo de A es menor que el valor mínimo de B, entonces también debe ser menor que todos los valores de B. Por lo tanto, es menor que todos los valores de A y todos los valores de B.

Entonces, mientras continúe agregando el valor que cumple con esos criterios a C, obtendrá una lista ordenada. Esto es lo que hace la función de merge anterior.

Ahora, dado este principio, es muy fácil entender una técnica de clasificación que ordena una lista al dividirla en listas más pequeñas, clasificar esas listas y luego fusionarlas. La función merge_sort es simplemente una función que divide una lista por la mitad, ordena esas dos listas y luego combina esas dos listas juntas de la manera descrita anteriormente.

El único problema es que, debido a que es recursivo, cuando clasifica las dos sub-listas, lo hace pasándolas a sí mismo. Si tiene dificultades para entender la recursión aquí, sugeriría que primero estudie problemas más simples. Pero si ya tienes lo básico de la recursión, entonces todo lo que tienes que darte cuenta es que la lista de un elemento ya está ordenada. La fusión de dos listas de un elemento genera una lista ordenada de dos elementos; la fusión de dos listas de dos elementos genera una lista ordenada de cuatro elementos; y así.

Answer 3

Cuando me tropiezo con la dificultad de entender cómo funciona el algoritmo, agrego resultados de depuración para verificar qué sucede realmente dentro del algoritmo.

Aquí el código con salida de depuración. Intente entender todos los pasos con llamadas recursivas de mergesort y lo que la merge hace con la salida:

def merge(left, right):
    result = []
    i ,j = 0, 0
    while i < len(left) and j < len(right):
        print(''left[i]: {} right[j]: {}''.format(left[i],right[j]))
        if left[i] <= right[j]:
            print(''Appending {} to the result''.format(left[i]))           
            result.append(left[i])
            print(''result now is {}''.format(result))
            i += 1
            print(''i now is {}''.format(i))
        else:
            print(''Appending {} to the result''.format(right[j]))
            result.append(right[j])
            print(''result now is {}''.format(result))
            j += 1
            print(''j now is {}''.format(j))
    print(''One of the list is exhausted. Adding the rest of one of the lists.'')
    result += left[i:]
    result += right[j:]
    print(''result now is {}''.format(result))
    return result

def mergesort(L):
    print(''---'')
    print(''mergesort on {}''.format(L))
    if len(L) < 2:
        print(''length is 1: returning the list withouth changing'')
        return L
    middle = len(L) / 2
    print(''calling mergesort on {}''.format(L[:middle]))
    left = mergesort(L[:middle])
    print(''calling mergesort on {}''.format(L[middle:]))
    right = mergesort(L[middle:])
    print(''Merging left: {} and right: {}''.format(left,right))
    out = merge(left, right)
    print(''exiting mergesort on {}''.format(L))
    print(''#---'')
    return out


mergesort([6,5,4,3,2,1])

Salida:

---
mergesort on [6, 5, 4, 3, 2, 1]
calling mergesort on [6, 5, 4]
---
mergesort on [6, 5, 4]
calling mergesort on [6]
---
mergesort on [6]
length is 1: returning the list withouth changing
calling mergesort on [5, 4]
---
mergesort on [5, 4]
calling mergesort on [5]
---
mergesort on [5]
length is 1: returning the list withouth changing
calling mergesort on [4]
---
mergesort on [4]
length is 1: returning the list withouth changing
Merging left: [5] and right: [4]
left[i]: 5 right[j]: 4
Appending 4 to the result
result now is [4]
j now is 1
One of the list is exhausted. Adding the rest of one of the lists.
result now is [4, 5]
exiting mergesort on [5, 4]
#---
Merging left: [6] and right: [4, 5]
left[i]: 6 right[j]: 4
Appending 4 to the result
result now is [4]
j now is 1
left[i]: 6 right[j]: 5
Appending 5 to the result
result now is [4, 5]
j now is 2
One of the list is exhausted. Adding the rest of one of the lists.
result now is [4, 5, 6]
exiting mergesort on [6, 5, 4]
#---
calling mergesort on [3, 2, 1]
---
mergesort on [3, 2, 1]
calling mergesort on [3]
---
mergesort on [3]
length is 1: returning the list withouth changing
calling mergesort on [2, 1]
---
mergesort on [2, 1]
calling mergesort on [2]
---
mergesort on [2]
length is 1: returning the list withouth changing
calling mergesort on [1]
---
mergesort on [1]
length is 1: returning the list withouth changing
Merging left: [2] and right: [1]
left[i]: 2 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2]
exiting mergesort on [2, 1]
#---
Merging left: [3] and right: [1, 2]
left[i]: 3 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
left[i]: 3 right[j]: 2
Appending 2 to the result
result now is [1, 2]
j now is 2
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2, 3]
exiting mergesort on [3, 2, 1]
#---
Merging left: [4, 5, 6] and right: [1, 2, 3]
left[i]: 4 right[j]: 1
Appending 1 to the result
result now is [1]
j now is 1
left[i]: 4 right[j]: 2
Appending 2 to the result
result now is [1, 2]
j now is 2
left[i]: 4 right[j]: 3
Appending 3 to the result
result now is [1, 2, 3]
j now is 3
One of the list is exhausted. Adding the rest of one of the lists.
result now is [1, 2, 3, 4, 5, 6]
exiting mergesort on [6, 5, 4, 3, 2, 1]
#---

Answer 4

La clasificación por fusión siempre ha sido uno de mis algoritmos favoritos.

Comienza con secuencias ordenadas cortas y continúa fusionándolas, en orden, en secuencias ordenadas más grandes. Tan sencillo.

La parte recursiva significa que estás trabajando hacia atrás, comenzando con la secuencia completa y clasificando las dos mitades. Cada mitad también se divide, hasta que la clasificación se vuelve trivial cuando solo hay cero o un elemento en la secuencia. A medida que las funciones recursivas regresan, las secuencias ordenadas se hacen más grandes, como dije en la descripción inicial.

Answer 5

Puede tener una buena visualización de cómo funciona la ordenación de fusión aquí:

http://www.ee.ryerson.ca/~courses/coe428/sorting/mergesort.html

Espero que ayude.

Answer 6

Un par de maneras para ayudarte a entender esto:

Recorra el código en un depurador y observe lo que sucede. O, Paso a paso en papel (con un ejemplo muy pequeño) y observe lo que sucede.

(Personalmente, me parece más instructivo hacer este tipo de cosas en papel)

Conceptualmente funciona de la siguiente manera: la lista de entrada sigue siendo dividida en partes cada vez más pequeñas al reducirse a la mitad (por ejemplo, la list[:middle] es la primera mitad). Cada mitad se reduce a la mitad una y otra vez hasta que tiene una longitud de menos de 2. Es decir, hasta que no es nada en absoluto o un solo elemento. Estas piezas individuales se vuelven a unir mediante la rutina de fusión, agregando o intercalando las 2 sublistas a la lista de result , y de este modo obtiene una lista ordenada. Debido a que las 2 sublistas deben estar ordenadas, la adición / intercalación es una operación rápida ( O (n) ).

La clave para esto (en mi opinión) no es la rutina de fusión, eso es bastante obvio una vez que entiendes que las entradas a ella siempre se ordenarán. El "truco" (uso comillas porque no es un truco, es ciencia de la computación :-)) es para garantizar que las entradas para fusionar estén ordenadas, hay que seguir recurriendo hasta llegar a una lista que debe ordenarse. , y es por eso que sigues llamando recursivamente a mergesort hasta que la lista tenga menos de 2 elementos.

La recursión y, por extensión, la ordenación por fusión, pueden no ser obvias cuando se encuentran por primera vez. Es posible que desee consultar un buen libro de algoritmos (por ejemplo, DPV está disponible en línea, legalmente y de forma gratuita), pero puede recorrer un largo camino a través del código que tiene. Si realmente quieres entrar en él, el curso Stanford / Coursera algo volverá a ejecutarse pronto y él cubre el tipo de Combinación con gran detalle.

Si realmente quiere entenderlo, lea el capítulo 2 de la referencia del libro, luego deseche el código anterior y vuelva a escribir desde cero. Seriamente.

Answer 7

Una imagen vale más que mil palabras, y una animación vale 10.000.

Revise la siguiente animación tomada de Wikipedia que le ayudará a visualizar cómo funciona realmente el algoritmo de clasificación de mezcla.

Animación detallada con explicación para cada paso en el proceso de clasificación para los inquisitivos.

Otra animación interesante de varios tipos de algoritmos de clasificación.

Answer 8

básicamente obtienes tu lista, luego la divides y la ordenas, pero aplicas este método de forma recursiva para terminar dividiéndola nuevamente y hasta que tengas un conjunto trivial que puedas clasificar fácilmente y luego fusiones todas las soluciones simples para obtener una matriz completamente ordenada