algorithm - recursive - merge sort recursivo

Comprender la recursión de mergesort (9)

Una cosa obvia que hacer sería probar este tipo de combinación en una matriz pequeña, digamos tamaño 8 (el poder de 2 es conveniente aquí), en papel. Pretenda que es una computadora que ejecuta el código, y vea si comienza a ser un poco más claro.

Tu pregunta es un poco ambigua porque no explicas lo que encuentras confuso, pero parece que estás tratando de desenrollar las llamadas recursivas en tu cabeza. Lo cual puede o no ser algo bueno, pero creo que puede conducir fácilmente a tener demasiado en tu cabeza a la vez. En lugar de tratar de rastrear el código de principio a fin, vea si puede entender el concepto de manera abstracta. Tipo de fusión:

Divide la matriz a la mitad
Ordena la mitad izquierda
Ordena la mitad derecha
Fusiona las dos mitades juntas

(1) debería ser bastante obvio e intuitivo para usted. Para el paso (2) la información clave es esta, la mitad izquierda de una matriz ... es una matriz. Suponiendo que su tipo de fusión funciona , debería poder ordenar la mitad izquierda de la matriz. ¿Derecha? El paso (4) es en realidad una parte bastante intuitiva del algoritmo. Un ejemplo debería hacerlo trivial:

at the start left: [1, 3, 5], right: [2, 4, 6, 7], out: [] after step 1 left: [3, 5], right: [2, 4, 6, 7], out: [1] after step 2 left: [3, 5], right: [4, 6, 7], out: [1, 2] after step 3 left: [5], right: [4, 6, 7], out: [1, 2, 3] after step 4 left: [5], right: [6, 7], out: [1, 2, 3, 4] after step 5 left: [], right: [6, 7], out: [1, 2, 3, 4, 5] after step 6 left: [], right: [7], out: [1, 2, 3, 4, 5, 6] at the end left: [], right: [], out: [1, 2, 3, 4, 5, 6, 7]

Entonces, suponiendo que comprenda (1) y (4), otra forma de pensar en el tipo de combinación sería esta. Imagina que alguien más escribió mergesort() y estás seguro de que funciona. Entonces podrías usar esa implementación de mergesort() para escribir:

sort(myArray) { leftHalf = myArray.subArray(0, myArray.Length/2); rightHalf = myArray.subArray(myArray.Length/2 + 1, myArray.Length - 1); sortedLeftHalf = mergesort(leftHalf); sortedRightHalf = mergesort(rightHalf); sortedArray = merge(sortedLeftHalf, sortedRightHalf); }

Tenga en cuenta que sort no usa recursión. Simplemente dice "ordenar ambas mitades y luego fusionarlas". Si entendiste el ejemplo de fusión anterior, entonces ojalá veas intuitivamente que esta función de sort parece hacer lo que dice ... ordenar.

Ahora, si lo miras con más cuidado ... sort() parece bastante exactamente a mergesort() ! Eso es porque es mergesort() (¡excepto que no tiene casos base porque no es recursivo!).

Pero así es como me gusta pensar en funciones recursivas: supongamos que la función funciona cuando la llamas. Trátelo como una caja negra que hace lo que usted necesita. Cuando haces esa suposición, descubrir cómo llenar esa caja negra a menudo es fácil. Para una entrada dada, ¿puede dividirla en entradas más pequeñas para alimentar a su caja negra? Después de resolver eso, lo único que queda es manejar los casos base al inicio de su función (que son los casos en los que no es necesario hacer ninguna llamada recursiva. Por ejemplo, mergesort([]) simplemente devuelve un mensaje vacío array, no hace una llamada recursiva a mergesort() ).

Finalmente, esto es un poco abstracto, pero una buena forma de entender la recursión es escribir pruebas matemáticas usando la inducción. La misma estrategia utilizada para escribir una prueba por inducción se usa para escribir una función recursiva:

Prueba de matemáticas:

Muestre que el reclamo es verdadero para los casos base
Supongamos que es cierto para las entradas más pequeñas que algunas n
Use esa suposición para mostrar que sigue siendo cierto para una entrada de tamaño n

Función recursiva:

Manejar los casos base
Suponga que su función recursiva funciona en entradas más pequeñas que algunas n
Use esa suposición para manejar una entrada de tamaño n

La mayoría de las implementaciones de mergesort que veo son similares a esto. introducción al libro de algoritmos junto con las implementaciones en línea que busco. Mis chuletas de recursión no van más allá de jugar con la generación de Fibonacci (que era lo suficientemente simple) así que tal vez sean las múltiples recursiones las que me pasen por la mente, pero ni siquiera puedo leer el código y entender qué está pasando incluso antes de golpearlo. la función de fusión.

¿Cómo está pasando por esto? ¿Hay alguna estrategia o lectura que deba seguir para comprender mejor el proceso aquí?

void mergesort(int *a, int*b, int low, int high) { int pivot; if(low<high) { pivot=(low+high)/2; mergesort(a,b,low,pivot); mergesort(a,b,pivot+1,high); merge(a,b,low,pivot,high); } }

y la fusión (aunque, francamente, estoy atrapado mentalmente incluso antes de llegar a esta parte)

void merge(int *a, int *b, int low, int pivot, int high) { int h,i,j,k; h=low; i=low; j=pivot+1; while((h<=pivot)&&(j<=high)) { if(a[h]<=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(h>pivot) { for(k=j; k<=high; k++) { b[i]=a[k]; i++; } } else { for(k=h; k<=pivot; k++) { b[i]=a[k]; i++; } } for(k=low; k<=high; k++) a[k]=b[k]; }

el mergesort() simplemente divide la matriz en dos mitades hasta que la condición if falla que es low < high . Como está llamando a mergesort() dos veces: una con low para pivot y la segunda con pivot+1 a high , esto dividirá las matrices secundarias aún más.

Tomemos un ejemplo:

a[] = {9,7,2,5,6,3,4} pivot = 0+6/2 (which will be 3) => first mergesort will recurse with array {9,7,2} : Left Array => second will pass the array {5,6,3,4} : Right Array

Se repetirá hasta que tengas 1 elemento en cada matriz left y right . Al final tendrás algo similar a esto:

L : {9} {7} {2} R : {5} {6} {3} {4} (each L and R will have further sub L and R) => which on call to merge will become L(L{7,9} R{2}) : R(L{5,6} R{3,4}) As you can see that each sub array are getting sorted in the merge function. => on next call to merge the next L and R sub arrays will get in order L{2,7,9} : R{3,4,5,6} Now both L and R sub array are sorted within On last call to merge they''ll be merged in order Final Array would be sorted => {2,3,4,5,6,7,9}

Vea los pasos de fusión en la respuesta dada por @roliu

Creo que el nombre de la función "ordenar" en MergeSort es un poco inapropiado, realmente debería llamarse "dividir".

Aquí hay una visualización del algoritmo en proceso.

Cada vez que la función recurre, está trabajando en una subdivisión cada vez más pequeña de la matriz de entrada, empezando por la mitad izquierda. Cada vez que la función regresa de la recursión, continuará y comenzará a trabajar en la mitad derecha, o recurrirá nuevamente y trabajará en una mitad más grande.

Me gusta esto

[************************]mergesort [************]mergesort(lo,mid) [******]mergesort(lo,mid) [***]mergesort(lo,mid) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [***]mergesort(mid+1,hi) [**]mergesort*(lo,mid) [**]mergesort(mid+1,hi) [***]merge [******]merge [******]mergesort(mid+1,hi) [***]mergesort(lo,mid) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [***]mergesort(mid+1,hi) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [******]merge [************]merge [************]mergesort(mid+1,hi) [******]mergesort(lo,mid) [***]mergesort(lo,mid) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [***]mergesort(mid+1,hi) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [******]merge [******]mergesort(mid+1,hi) [***]mergesort(lo,mid) [**]mergesort*(lo,mid) [**]mergesort(mid+1,hi) [***]merge [***]mergesort(mid+1,hi) [**]mergesort(lo,mid) [**]mergesort(mid+1,hi) [***]merge [******]merge [************]merge [************************]merge

En cuanto a la parte de recursión del tipo de combinación, he encontrado que esta página es muy útil. Puede seguir el código mientras se está ejecutando. Le muestra qué se ejecuta primero y qué sigue a continuación.

Tom

MERGE SORT:

1) Divida la matriz por la mitad
2) Ordena la mitad izquierda
3) Ordena la mitad derecha
4) Combina las dos mitades juntas

Mis disculpas si esto ha sido respondido de esta manera. Reconozco que esto es solo un boceto, en lugar de una explicación profunda.

Si bien no es obvio para ver cómo el código real se asigna a la recursión, pude entender la recursión en un sentido general de esta manera.

Tome como ejemplo el conjunto {2,9,7,5} ejemplo {2,9,7,5} como entrada. El algoritmo merge_sort se denota por "ms" para la brevedad a continuación. Entonces podemos dibujar la operación como:

paso 1: ms (ms (ms (2), ms (9)), ms (ms (7), ms (5)))
paso 2: ms (ms ({2}, {9}), ms ({7}, {5}))
paso 3: ms ({2,9}, {5,7})
paso 4: {2,5,7,9}

Es importante tener en cuenta que merge_sort de singlete (como {2} ) es simplemente singlete (ms (2) = {2} ), de modo que en el nivel más profundo de recursión obtenemos nuestra primera respuesta. Las respuestas restantes luego caen como fichas de dominó a medida que las recursiones interiores finalizan y se fusionan.

Parte del genio del algoritmo es la forma en que construye la fórmula recursiva del paso 1 automáticamente a través de su construcción. Lo que me ayudó fue el ejercicio de pensar cómo pasar el paso 1 anterior de una fórmula estática a una recursión general.

proceso para dividir el problema en subproblemas. El ejemplo dado lo ayudará a comprender la recursión. int A [] = {número de elemento a cortocircuitar.}, int p = 0; (índice de amante). int r = A.length - 1; (Índice más alto).

class DivideConqure1 { void devide(int A[], int p, int r) { if (p < r) { int q = (p + r) / 2; // divide problem into sub problems. devide(A, p, q); //divide left problem into sub problems devide(A, q + 1, r); //divide right problem into sub problems merger(A, p, q, r); //merger the sub problem } } void merger(int A[], int p, int q, int r) { int L[] = new int[q - p + 1]; int R[] = new int[r - q + 0]; int a1 = 0; int b1 = 0; for (int i = p; i <= q; i++) { //store left sub problem in Left temp L[a1] = A[i]; a1++; } for (int i = q + 1; i <= r; i++) { //store left sub problem in right temp R[b1] = A[i]; b1++; } int a = 0; int b = 0; int c = 0; for (int i = p; i < r; i++) { if (a < L.length && b < R.length) { c = i + 1; if (L[a] <= R[b]) { //compare left element<= right element A[i] = L[a]; a++; } else { A[i] = R[b]; b++; } } } if (a < L.length) for (int i = a; i < L.length; i++) { A[c] = L[i]; //store remaining element in Left temp into main problem c++; } if (b < R.length) for (int i = b; i < R.length; i++) { A[c] = R[i]; //store remaining element in right temp into main problem c++; } }

Sé que esta es una vieja pregunta, pero quería expresar mis pensamientos sobre lo que me ayudó a entender el tipo de fusión.

Hay dos partes grandes para fusionar

División de la matriz en trozos más pequeños (división)
Fusionando la matriz juntos (conquistando)

El papel de la recurrencia es simplemente la parte divisoria.

Creo que lo que confunde a la mayoría de las personas es que creen que hay mucha lógica en la división y en qué dividir, pero la mayor parte de la lógica real de clasificación ocurre en la fusión . La recursión está simplemente allí para dividir y hacer la primera mitad, y luego la segunda mitad simplemente está girando, copiando las cosas.

Veo algunas respuestas que mencionan pivotes, pero recomendaría no asociar la palabra "pivote" con el tipo de combinación porque es una forma fácil de confundir el orden de fusión con el servicio rápido (que depende en gran medida de elegir un "pivote"). Ambos son algoritmos de "divide y vencerás". Para el tipo de fusión, la división siempre ocurre en el medio, mientras que para el quicksort puede ser inteligente con la división al elegir un pivote óptimo.

Cuando llama al método recursivo, no ejecuta la función real al mismo tiempo que es pila en la memoria de la pila. Y cuando la condición no está satisfecha, va a la siguiente línea.

Considera que esta es tu matriz:

int a[] = {10,12,9,13,8,7,11,5};

Por lo tanto, su método de fusión de métodos funcionará de la siguiente manera:

mergeSort(arr a, arr empty, 0 , 7); mergeSort(arr a, arr empty, 0, 3); mergeSort(arr a, arr empty,2,3); mergeSort(arr a, arr empty, 0, 1); after this `(low + high) / 2 == 0` so it will come out of first calling and going to next: mergeSort(arr a, arr empty, 0+1,1); for this also `(low + high) / 2 == 0` so it will come out of 2nd calling also and call: merger(arr a, arr empty,0,0,1); merger(arr a, arr empty,0,3,1); . . So on

Entonces todos los valores de clasificación se almacenan en arr vacío Podría ayudar a entender cómo funciona la función recursiva