Luego de tanto batallar hemos hallado el resultado de este conflicto que muchos lectores de nuestra web tienen. Si quieres aportar algún dato puedes compartir tu información.[**]
[***]Solución:[******]
CLASIFICACIÓN FUSIÓN:
[**]
1) Dividir el array a la mitad
2) Clasifica la mitad izquierda
3) Clasifica la mitad derecha
4) Fusiona las dos mitades juntas
[**]
[**]
Creo que el nombre de la función “ordenar” en MergeSort es un nombre poco apropiado, en realidad debería llamarse “dividir”.[**]
Aquí hay una visualización del algoritmo en proceso. [**]
[************][**]
Cada vez que la función se repite, está trabajando en una subdivisión cada vez más pequeña de la entrada. array, comenzando con la mitad izquierda. Cada vez que la función regresa de la recursividad, continuará y comenzará a trabajar en la mitad derecha, o volverá a subir y trabajará en una mitad más grande.[**]
Como 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
Una cosa obvia sería probar este tipo de combinación en un pequeño array, digamos tamaño 8 (la potencia de 2 es conveniente aquí), en papel. Imagina que eres una computadora que ejecuta el código y fíjate si comienza a aclararse un poco. [**]
Su pregunta es un poco ambigua porque no explica lo que encuentra confuso, pero parece que está tratando de desenrollar las llamadas recursivas en su cabeza. Lo cual puede ser algo bueno o no, pero creo que puede llevar fácilmente a tener demasiadas cosas en la cabeza a la vez. En lugar de intentar rastrear el código de principio a fin, vea si puede entender el concepto de manera abstracta. Combinar ordenación:[**]
- Divide el array 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) el key insight es esta, la mitad izquierda de un array… es un array. Suponiendo que su ordenación de combinación funcione, debería poder ordenar la mitad izquierda del array. ¿Correcto? 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 fusión sería esta. Imagina que alguien más escribió mergesort() y está seguro de que funciona. Entonces podrías usar esa implementación de mergesort() 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 la recursividad. Solo dice “ordenar las dos mitades y luego fusionarlas”. Si entendió el ejemplo de fusión anterior, es de esperar que vea intuitivamente que esto sort la función parece hacer lo que dice … ordenar.[**]
Ahora, si lo miras con más atención … sort() se ve más o menos exactamente como 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: suponga que la función funciona cuando la llama. Trátelo como una caja negra que hace lo que necesita. Cuando hace esa suposición, a menudo es fácil averiguar cómo llenar esa casilla negra. Para una entrada determinada, ¿puede dividirla en entradas más pequeñas para alimentar su caja negra? Después de resolver eso, lo único que queda es manejar los casos base al comienzo de su función (que son los casos en los que no necesita hacer ninguna llamada recursiva. Por ejemplo, mergesort([]) solo devuelve un vacío array; no hace una llamada recursiva a mergesort()).[**]
Finalmente, esto es un poco abstracto, pero una buena manera de entender la recursividad es escribir pruebas matemáticas usando inducción. La misma estrategia usada para escribir una prueba por inducción se usa para escribir una función recursiva:[**]
Prueba matemática:[**]
- Muestre que el reclamo es true para los casos base
- Asume que es true para entradas más pequeñas que algunas
n - Utilice esa suposición para demostrar que todavía es true 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 - Utilice esa suposición para manejar una entrada de tamaño
n
Recuerda que puedes interpretar si te fue de ayuda.[**]