Ordenamiento de Arrays con MergeSort en C

Curso Práctico de Estructuras de Datos y Algoritmos

Contenido del curso

Bienvenido al Curso

1
Algoritmos y Estructuras de Datos: Curso Básico
02:17 min

Introducción a los algoritmos

Algoritmos de ordenamiento

Recursividad

Divide and conquer y programación dinámica

Algoritmos 'Greedy'

Grafos y árboles

¿Cómo comparar Algoritmos?

41
Comparación de Algoritmos: Complejidad y Ritmo de Crecimiento
11:14 min

¿Qué sigue?

42
Resolución de Problemas Básicos con Algoritmos y Estructuras de Datos
02:26 min

Tomar examen

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 sorted

int main()
{
  int n,i;
  
  printf("Enter the size of array\n");  // input the elements
  scanf("%d",&n);
  printf("Enter the elements:");
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
  
  merge_sort(arr,0,n-1);  // sort the array
  
  printf("Sorted array:");  // print sorted array
  for(i=0;i<n;i++)
    printf("%d",arr[i]);
  
  return 0;
}

int merge_sort(int arr[],int low,int high)
{
  int mid;
  if(low<high)
  {
    mid=(low+high)/2;
   // Divide and Conquer
    merge_sort(arr,low,mid);
    merge_sort(arr,mid+1,high);
   // Combine
    merge(arr,low,mid,high);
  }
  
  return 0;
}

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++];
  }
  
  return 0;
}

Ordenamiento de Arrays con MergeSort en C

Victor Muchica Farfan

Estudiante

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.

Este video me ayudo a entender el algoritmo https://www.youtube.com/watch?v=TzeBrDU-JaY

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 elementos
  printf("Enter the size of array: ");
  scanf("%d",&n); //valor del tamaño del array
  printf("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 magia

  printf("Array Ordenado:");  //imprime arreglo ordenado
  for(i=0;i<n;i++)
    printf("%d,",arr[i]);

  return 0;
}

int merge_sort(int arr[],int low,int high)
{
  int mid;
  if(low<high)
  {
    mid=(low+high)/2;
   // Divide en 2 al array
    printf("ordena toda izquierda -> merge_sort(arr,%d,%d)\n",low,mid);
    merge_sort(arr,low,mid); //izquierda
    printf("ordena toda derecha -> merge_sort(arr,%d,%d)\n",mid+1,high);
    merge_sort(arr,mid+1,high); //derecha
   // Combina
    printf("\nmerge(arr,%d,%d,%d)\n",low,mid,high);
    merge(arr,low,mid,high);
  }
  return 0;
}

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 arr2
  printf("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++;
    }
  }
  return 0;
}

Lorena Mosquera González

Estudiante

Lo entendí mejor con tu código, muchas gracias! :)

Francisco Joel Morando Pinedo

JUAN FRANCISCO ochoa lomas

Gloriq Lopez

Alfredo Godinez

alexander garcia castañeda

Moisés Manuel Morín Hevia

Gonzalo Gramaglia

Daniel Santiago Perez Ducuara

Eduardo Kiriakos Piazza

Harrinson Quintero

Diego Portillo

Henry Caicedo Velasco

Elisa Zamarron Muñoz

Ignacio Saccomano

Henry Leonardo Rodríguez Pérez

Brayan García

Jorge Torres Arboleda

Reinaldo Mendoza

Juan Manuel Otero Rey

Juan Carlos Aranda Muñoz

Luis Xavier Perez Miramontes

Samar Jaffal

Efraín Hernández García

Ricardo Moreno

Irving Jerico Hernandez Diaz

Victor Hugo Vázquez Gómez

ariel alexander riaño soler

Wandy Rafael Santana Evangelista

Lucero Mendez

Miqueas Gamero

Bernardo Aguayo Ortega

Diego Antonio Gomez Diaz

juan osuna

Youssef Abarca

Félix Andersson

Franco Bottazzi

Ordenamiento de Arrays con MergeSort en C

Bienvenido al Curso

Algoritmos y Estructuras de Datos: Curso Básico

Introducción a los algoritmos

Cómo Funcionan las Computadoras y el Sistema Binario

Introducción a Lenguajes de Programación: Bajo y Alto Nivel

Estructuras de Datos para Rutas Más Cortas en Mapas

Algoritmo de Dijkstra para encontrar la ruta más corta

Metodología para Resolver Algoritmos Paso a Paso

Variables y Tipos de Datos en Programación

Creación de Tipos de Datos Personalizados en C

Configuración de Ubuntu en Windows 10 para C/C++

Implementación de User Defined Data Type en C: Estructuras paso a paso

Tipos de Datos Abstractos y Estructuras de Datos en Programación

Tipos Abstractos de Datos: Lista, Pila, Cola y Diccionario

Tipos Abstractos de Datos: Listas, Pilas y Colas

Clases y objetos

Colas y estructuras de datos: gestión de pedidos en restaurante

Implementación de Queues con Arrays en Visual Studio Code

Implementación de Abstract Data Type en C: Función enqueue

Implementación de la función dequeue en estructuras de datos en C

Implementación de Colas en C: Declaración y Uso de Funciones Básicas

Algoritmos de ordenamiento

Algoritmos de Ordenamiento: Conceptos y Aplicaciones Básicas

Funcionamiento del Algoritmo de Ordenamiento Burbuja

Implementación de Bubble Sort en C paso a paso

Implementación de Bubble Sort en C y función de impresión

Ordenamiento por Inserción en C: Algoritmo y Ejemplo Práctico

Algoritmos de Ordenamiento Descendente: Implementación Práctica

Recursividad

Recursividad en Programación: Entendiendo el Factorial

Factorial Recursivo en C: Implementación y Ejemplo

Inversión de cadenas con recursividad en Java

Recursividad en Python: Arte con Turtle y Funciones Recursivas

Divide and conquer y programación dinámica

Diseño y análisis de algoritmos: Divide y vencerás

Introducción a Programación Dinámica y Quicksort