El algoritmo MergeSort es un algoritmo del tipo Divide and Conquer, en este dividimos el array de entrada en dos mitades, se invoca la función merge_sort(arr,low,mid); y merge_sort(arr,mid+1,high);
En cada una de esas mitades y luego une las dos mitades ordenadas, la función merge() se encargará de unir las dos mitades.
El comando merge(arr, low, mid, high) es un proceso clave que une las partes ordenadas, a continuación te comparto la implementación estándar utilizada por codeblocks:
//Divide : Divide the n-element array into two n/2-element subarrays.//Conquer : Sort the two subarrays recursively using merge sort//Combine : Merge the two sorted subsequences to form the sorted array#include<stdio.h>int arr[20];// array to be sortedint main(){ int n,i;printf("Enter the size of array\n");// input the elementsscanf("%d",&n);printf("Enter the elements:");for(i=0;i<n;i++)scanf("%d",&arr[i]);merge_sort(arr,0,n-1);// sort the arrayprintf("Sorted array:");// print sorted arrayfor(i=0;i<n;i++)printf("%d",arr[i]);return0;}int merge_sort(int arr[],int low,int high){ int mid;if(low<high){ mid=(low+high)/2;// Divide and Conquermerge_sort(arr,low,mid);merge_sort(arr,mid+1,high);// Combinemerge(arr,low,mid,high);}return0;}int merge(int arr[],int l,int m,int h){ int arr1[10],arr2[10];// Two temporary arrays to hold the two arrays to be merged
int n1,n2,i,j,k; n1=m-l+1; n2=h-m;for(i=0;i<n1;i++) arr1[i]=arr[l+i];for(j=0;j<n2;j++) arr2[j]=arr[m+j+1]; arr1[i]=9999;// To mark the end of each temporary array arr2[j]=9999; i=0;j=0;for(k=l;k<=h;k++)//process of combining two sorted arrays{if(arr1[i]<=arr2[j]) arr[k]=arr1[i++];else arr[k]=arr2[j++];}return0;}
Es un poco molesto, para otros temas dan explicación hasta gráfica y todo, pero algoritmos como estos que no son tan fácil que digamos lo dan como un articulo, generalizando que todo aquel que lea ya lo comprenderá.
Tendrían que hacer una clase (video) explicando cada linea de código de este Algoritmo.
comparto tu comentario, creo que ese debe ser el plus que nos deberían de compartir los profes en este tipo de cursos, aclaro que no es malo el material que dan, si deberían de ahondar mas a fondo, porque muchos temas los ven por encima y deberían ser mas concisos.
Muy bueno el aporte, en cuando a la pregunta comentada en el código, la línea se ejecuta cuando los elementos llegaron a la longitud de 1 y no pueden seguir dividiendose
La verdad a este código me parece que le hace falta muchísimo para lo que esperaría de un curso de Platzi.
Para empezar, no se explica bien (siendo un algoritmo complicado por usar la recursividad), declara primero la función que divide y luego la que combina (¿Cómo va a hacer eso?, la función de dividir llama a la de combinar, ¿no?), además, tiene un límite en cuanto a los número del array, y termina el array con “9999”, ¿es en serio? ¿En donde se usa ese fin del array?
Les dejo mi código por si puedo ayudar a alguien que se perdió por este código tan incompleto:
Para poder entender el algoritmo y como se comporta cada función tuve que hacerlo a mano paso a paso con un simple array de 3 numeros = [3,2,1].
Me tomó un poco de tiempo para entender y 3 hojas de cuaderno jajaja
Aqui la inplementación del mergeSort en python con algunos print statements para entender mucho mejor lo que hace el código!
import random
def mergeSort(arr):iflen(arr)>1: mid =len(arr)// 2 left = arr[:mid] rigth = arr[mid:]print(f"Dividing left: {left} rigth {rigth}")mergeSort(left)mergeSort(rigth) # Esta es una de las dudas que me surgió al intentar entender recursividad.print("¿Cuándo se ejecuta esta línea?") i =0 j =0 k =0while i <len(left) and j <len(rigth):if left[i]< rigth[j]: arr[k]= left[i] i +=1else: arr[k]= rigth[j] j +=1 k +=1while i <len(left): arr[k]= left[i] i +=1 k +=1while j <len(rigth): arr[k]= rigth[j] j +=1 k +=1print(f'comparando izquierda {left}, derecha {rigth}')print(arr)print('-'*50)return arr
if __name__ =='__main__': n =int(input('What is the length of the array? ')) arr =[random.randint(0,100)for i inrange(n)]print(arr)print('-'*20) ordered_arr =mergeSort(arr)print(ordered_arr)
En esta lectura siento que nos hubieran soltado en el coliseo romano junto a los leones, a ver como se defiende uno y logra salir vivo. Al menos en el curso de C listas enlazadas, el profesor "explico" el codigo.
Puse los printf para entender mejor el codigo con los comentarios
Lo mejor es probar con numeros pequeños(ordenar 3 numeros) y luego van agregando mas valores.
hasta que logren entender el codigo.
#include<stdio.h>int main(){ int n,i,arr[20];//declaracion array de 20 elementosprintf("Enter the size of array: ");scanf("%d",&n);//valor del tamaño del arrayprintf("Enter the elements:\n");for(i=0;i<n;i++){scanf("%d",&arr[i]);//ingresa los valores al arreglo}printf("merge_sort(arr,0,%d)\n",n-1);merge_sort(arr,0,n-1);//aca ocurre la magiaprintf("Array Ordenado:");//imprime arreglo ordenadofor(i=0;i<n;i++)printf("%d,",arr[i]);return0;}int merge_sort(int arr[],int low,int high){ int mid;if(low<high){ mid=(low+high)/2;// Divide en 2 al arrayprintf("ordena toda izquierda -> merge_sort(arr,%d,%d)\n",low,mid);merge_sort(arr,low,mid);//izquierdaprintf("ordena toda derecha -> merge_sort(arr,%d,%d)\n",mid+1,high);merge_sort(arr,mid+1,high);//derecha// Combinaprintf("\nmerge(arr,%d,%d,%d)\n",low,mid,high);merge(arr,low,mid,high);}return0;}int merge(int arr[],int l,int m,int h){ int arr1[10],arr2[10];//crea dos arreglos temporales int n1,n2,i,j,k;//i es indice izq de arr1 con tamaño n1, j es indice der de arr2 con tamaño n2 n1=m-l+1;//mid-low+1 = tamaño izquierdo n2=h-m;// tamaño derecho//lo que hace es ordenar los valores del arr en arr1 y arr2printf("Funcion Merge l:%d ,m:%d ,h:%d \n",l,m,h);printf("n1:%d ,n2:%d \n",n1,n2);for(i=0;i<n1;i++){ arr1[i]=arr[l+i];printf("i arr1[%d]:%d = arr[%d]:%d\n",i,arr[i],l+i,arr[l+i]);for(j=0;j<n2;j++){ arr2[j]=arr[m+j+1];printf("j arr2[%d]:%d= arr[%d]:%d\n",j,arr2[j],m+j+1,arr[m+j+1]);}} arr1[i]=9999;printf("arr1[%d]:%d\n",i,arr1[i]); arr2[j]=9999;printf("arr2[%d]:%d \n",j,arr2[j]);//el final del arr1 y arr2 les pone 9999 i=0;j=0;//compara y ordena el arreglo "combina"for(k=l;k<=h;k++){printf("\nCombinando dos arrays: k:%d \n",k);printf("arr1[%d]:%d <= arr2[%d]:%d\n",i,arr1[i],j,arr2[j]);if(arr1[i]<=arr2[j]){ arr[k]=arr1[i];printf("if arr[%d]:%d = arr1[%d]:%d \n",k,arr[k],i,arr1[i]); i++;}else{ arr[k]=arr2[j];printf("else arr[%d]:%d = arr2[%d]:%d \n",k,arr[k],j,arr2[j]); j++;}}return0;}
Mergesort en python:
''' Con esta funcion podemos crear arrays
con un numero aletorio de datos'''
def create_array(size=10, max =50):from random import randint
return[randint(0, max)for i inrange(size)]''' Rompemos el algoritmo en dos funciones principales
la funcion principal mergesort y la propia funcion de merge
para combinar los data sets '''
def merge(a, b): result=[] a_index, b_index =0,0''' Itramaos mientras el indice del arreglo sea menor a su largo'''while a_index <len(a) and b_index <len(b):''' Discriminamos que valor es mayor o menor y
lo almacenamos en result ordenado '''
if a[a_index]< b[b_index]: result.append(a[a_index])''' Aumentamos el indice para pasar al siguiente
valor dentro del array'''
a_index +=1else: result.append(b[b_index]) b_index +=1''' Ahora verificamos que todos los elementos sean agregados.Utilizamos el metodo extend() para agregar todo elemento iterable
de forma recursiva en el array que haya completado su ciclo primero '''
if a_index ==len(a): result.extend(b[b_index:])else: result.extend(a[a_index:])return result
def merge_sort(a):''' Una lista con cero o un elementos
esta ordenada por defecto '''
iflen(a)<=1:return a
''' Rompemos al lista en dos partes left y right
llamamos de forma recursiva a merge_sort() en cada mitad
aprovechando los slices de python '''
left, right =merge_sort(a[:len(a)//2]), merge_sort(a[len(a)//2:])''' Retornamos el resultado con la funcion merge() de esta forma creamos la recursividad que realmente implementa nuestra logica '''
returnmerge(left, right)dataset =create_array()print(merge_sort(dataset))
<constmergeSort=arr=>{//Check if the array has more than one elementif(arr.length<=1){return arr;}//Figure out the middle of the array ( divide the array in half)let middle =Math.floor(arr.length/2);//divided into left and rightlet left = arr.slice(0, middle);console.log("left", left);let right = arr.slice(middle);console.log("right", right);//using recursion to combine the left and right partreturnmerge(mergeSort(left),mergeSort(right));};//Merge the two arrays: left and rightconstmerge=(leftArray, rightArray)=>{let resultArray =[], leftIndex =0, rightIndex =0;//We willconcatenate values into the resultArray in orderwhile(leftIndex < leftArray.length&& rightIndex < rightArray.length){if(leftArray[leftIndex]< rightArray[rightIndex]){ resultArray.push(leftArray[leftIndex]); leftIndex++;console.log("leftArray", leftArray);}else{ resultArray.push(rightArray[rightIndex]); rightIndex++;console.log("rightArray", rightArray);}}//Concate all the elementsreturn resultArray
.concat(leftArray.slice(leftIndex)).concat(rightArray.slice(rightIndex));};mergeSort([0,3,5,2,7,1,-10,3,6]);>
#include <stdio.h>#include <stdlib.h>voidmerge(int array[], int left, int m, int right){ int i, j, k; int n1 = m - left +1; int n2 = right - m; int tempArray1[n1]; int tempArray2[n2];for(i =0; i < n1; i++){ tempArray1[i]= array[left + i];}for(j =0; j < n2; j++){ tempArray2[j]= array[m +1+ j];} i =0; j =0; k = left;while(i < n1 && j < n2){if(tempArray1[i]<= tempArray2[j]){ array[k]= tempArray1[i]; i++;}else{ array[k]= tempArray2[j]; j++;} k++;}while(i < n1){ array[k]= tempArray1[i]; i++; k++;}while(j < n2){ array[k]= tempArray2[j]; j++; k++;}return0;}voidmergeSort(int array[], int left, int right){ int m;if(left < right){ m =(left + right)/2;mergeSort(array, left, m);mergeSort(array, m+1, right);merge(array, left, m, right);}return0;}voidprintArray(int array[], int right){ int i;for(i =0; i < right; i++){printf("%d, ", array[i]);}return0;}int main(int argc, char const*argv[]){ int array[]={1,10,958,95,69,35,420}; int sizeArray =sizeof(array)/sizeof(array[0]);printf("Array is \n");printArray(array, sizeArray);mergeSort(array,0, sizeArray-1);printf("After merge sort algorithm\n");printArray(array, sizeArray);return0;}
Este algoritmo me tomo 5 dias en resolverlo y para ser honestos al 4to día mire la solución. Pero esto me ayudo a percatarme que estaba haciendo algo totalmente diferente a MergeSort.
Tambien vi el video que compartio nuestra compañera @DaneSanchz donde explica a profundidad como funciona este algoritmo (Link directo a su comentario). Esto me ayudo a entender mejor como funciona Merge Sort.
Después de analizar el algoritmo presentado en este artículo, me percate que este solo funciona con arreglos de 20 unidades que almacenan digitos menores a 9999 y el mismo solo puede ordenar ascedentemente.
Por el cual, me puse a pensar en una solución que atacara los problemas restantes. Despues de un día entero, les comparto la solución con C#:
using System;
namespace merge_sort
{publicclassMergeSort{publicvoidSort(ref int[] target, short order =1){InnerSort(ref target, order,0, target.Length-1);}privatevoidInnerSort(ref int[] target, short order, int min, int max){if(min < max){ int half =(min + max)/2;InnerSort(ref target, order, min, half);InnerSort(ref target, order, half +1, max);Merge(ref target, order, min, half, max);}}privatevoidMerge(ref int[] target, int order, int min, int half, int max){ int value =0; int? first =null, second =null; int[] temp =newint[max - min +1]; int firstIndex = min, secondIndex = half +1;for(int index =0; index < temp.Length; index++){if(!first.HasValue&& firstIndex <= half) first = target[firstIndex++];if(!second.HasValue&& secondIndex <= max) second = target[secondIndex++];if(first.HasValue&& second.HasValue){if((order ==1&& first > second)||(order ==-1&& first < second)){ value = second.Value; second =null;}else{ value = first.Value; first =null;}}else{if(first.HasValue){ value = first.Value; first =null;}else{ value = second.Value; second =null;}} temp[index]= value;}for(int index =0; index < temp.Length; index++){ target[index + min]= temp[index];}}}}
En C o C++ (Acá aprovecho la equivalencia entre un puntero y un vector para hacer más simple el código, aunque entiendo que la forma de arriba es para quienes no estén familiarizados con los punteros):
template<typename T>voidmergeSort(T*v, unsigned int n){//Caso base (ordeno un array si es de dos elementos o no hago nada si es uno)switch(n){case2:if(v[0]> v[1])changeValue(v[0], v[1]);case1:return;}//recursiónT*first = v,*second = v + n/2;mergeSort(first, n/2);//Primer mitad (n/2 primeros elementos)mergeSort(second, n - n/2);//Segunda mitad (el resto de los elementos)//mergeT aux[n];for(unsigned int i =0; i < n; i++){if( first == v + n/2||(second != v + n &&*first >*second)) aux[i]=*(second++);else aux[i]=*(first++);}for(unsigned int i =0; i < n; i++) v[i]= aux[i];}
