Divide y Vencerás

Clase 37 de 39 • Curso de Algoritmos con C 2017

Clase anteriorSiguiente clase

Emilio Castro

student•

Resumen:

Paradigma de diseño de algoritmos:
-Es una forma probada de hacer las cosas.

Divide y vencerás:

Es un algoritmo que consiste en tomar un problema grande y/o complejo, _dividirlo en sub-problemas _más simples, resolverlos. Finalmente los sub-problemas resueltos se fusionan formando un resultado final.

Pasos:

Divide: el problema en pequeñas instancias del problema mayor
Resuelve los sub-problemas de forma recursiva.
Combina todas las soluciones para obtener la solución final.

Ejemplo de algoritmo que aplica el divide y vencerás:_ Merge Sort._

-Es un algoritmo de ordenamiento de la forma n log^2 n.

Divide: separa tu arreglo (vector) de números en pares.
Resuelve: ordena cada par.
Combina: recursivamente los vuelve (a cada par) a generar en un vector ordenado.

Ricardo Celis

teacher•

Excelente resumen Emilio! Cómo vas con el programa?

Emilio Castro

student•

Muy bien, me encantó el curso!
Gracias Ricardo y Platzi!

Javier Ramirez

student•

Este es mi merge Sort

#include<stdio.h>
 
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
 
int main()
{
    int a[30],n,i;
    printf("Enter no of elements:");
    scanf("%d",&n);
    printf("Enter array elements:");
    
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        
    mergesort(a,0,n-1);
    
    printf("\nSorted array is :");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
        
    return 0;
}
 
void mergesort(int a[],int i,int j)//divide el array a la mitad
{
    int mid;// mid es la mitad del array
    // a es el array, i es el inicio del array y j es el final del array       
    if(i<j)
    {
        mid=(i+j)/2;
        mergesort(a,i,mid);        //mitad izquierda
        mergesort(a,mid+1,j);    //mitad derecha
        merge(a,i,mid,mid+1,j);    //une las dos mitades
    }
}
 
void merge(int a[],int i1,int j1,int i2,int j2)
{
    int temp[50];    //array temporal
    int i,j,k;
    i=i1;    //inicio de la primera mitad del array
    j=i2;    //inicio de la segunda mitad del array
    k=0;
    
    while(i<=j1 && j<=j2) // mientras i sea mas pequeno o igual que el final de la primera mitad
                          // y j sea mas pequeno que el final de la segunda mitad, has lo siguiente
    {
        if(a[i]<a[j])// Este if es solo para la primera iteracion, cuando los arrays estan separados totalmente 
            temp[k++]=a[i++]; //si a[i] es mas pequeno que a[j] agrega primero el a[i]
        else
            temp[k++]=a[j++]; //si a[j] es mas pequeno que a[i] agrega primero el a[j]
    }
    
    while(i<=j1)// estos dos whiles son para el resto de los arrays, ya cuando se estan uninendo, es decir la segunda iteracion en adelante   
        temp[k++]=a[i++];
        
    while(j<=j2)    
        temp[k++]=a[j++];
        
    //Transferri elementos del temp[] al a[]
    for(i=i1,j=0;i<=j2;i++,j++)
        a[i]=temp[j];
}```

Luis Fernando Méndez González

student•

Yo quiero el link de lo de Toyota 😦

Freddy Córdova Arana

student•

Gracias, también quería verlo 😃

David Auza

student•

No tengo mucha idea de si lo que hice es lo solicitado en el reto jeje pero logré con código que mi máquina siguiera las instrucciones necesarias para ordenar el arreglo mostrado en el ejemplo, siguiendo el proceso de dividir el arreglo original en varios y luego unirlos e irlos ordenando. Sé que no es lo más óptimo que se puede hacer, pero lo hice desde mis conocimientos en programación que considero todavía son básicos. Si no era lo esperado agradezco se me indique 😃:

#include <stdio.h>

int main()
{
  int vector_entrada[] = {14, 7, 3, 12, 9, 11, 6, 2};
  int *firstHalf = vector_entrada;
  int *secondHalf = vector_entrada + 4;
  int *div1 = firstHalf;
  int *div2 = secondHalf;
  int *div3, *div4, *div5, *div6, *div7, *div8, *div9, *div10, *div11, *div12, *div13, *div14;

  int unión1[2], unión2[2], unión3[2], unión4[2], unión5[4], unión6[4], unión7[8];

  printf("\n");
  printf("Arreglo original = ");
  for (int i = 0; i < 8; i++)
  {
    if (i != 7)
    {
      printf("%d, ", vector_entrada[i]);
    }
    else
    {
      printf("%d\n", vector_entrada[i]);
    }
  }
  printf("\n");

  printf("División 1 = ");
  for (int i = 0; i < 4; i++)
  {
    if (i != 3)
    {
      printf("%d, ", div1[i]);
    }
    else
    {
      printf("%d          ", div1[i]);
    }
  }

  printf("División 2 = ");
  for (int i = 0; i < 4; i++)
  {
    if (i != 3)
    {
      printf("%d, ", div2[i]);
    }
    else
    {
      printf("%d\n", div2[i]);
    }
  }
  printf("\n");

  firstHalf = div1;
  secondHalf = div1 + 2;
  div3 = firstHalf;
  div4 = secondHalf;

  printf("División 3 = ");
  for (int i = 0; i < 2; i++)
  {
    if (i != 1)
    {
      printf("%d, ", div3[i]);
    }
    else
    {
      printf("%d    ", div3[i]);
    }
  }

  printf("División 4 = ");
  for (int i = 0; i < 2; i++)
  {
    if (i != 1)
    {
      printf("%d, ", div4[i]);
    }
    else
    {
      printf("%d    ", div4[i]);
    }
  }

  firstHalf = div2;
  secondHalf = div2 + 2;
  div5 = firstHalf;
  div6 = secondHalf;

  printf("División 5 = ");
  for (int i = 0; i < 2; i++)
  {
    if (i != 1)
    {
      printf("%d, ", div5[i]);
    }
    else
    {
      printf("%d    ", div5[i]);
    }
  }

  printf("División 6 = ");
  for (int i = 0; i < 2; i++)
  {
    if (i != 1)
    {
      printf("%d, ", div6[i]);
    }
    else
    {
      printf("%d\n", div6[i]);
    }
  }
  printf("\n");

  firstHalf = div3;
  secondHalf = div3 + 1;
  div7 = firstHalf;
  div8 = secondHalf;

  printf("División 7 = %d  ", div7[0]);
  printf("División 8 = %d  ", div8[0]);

  firstHalf = div4;
  secondHalf = div4 + 1;
  div9 = firstHalf;
  div10 = secondHalf;

  printf("División 9 = %d  ", div9[0]);
  printf("División 10 = %d  ", div10[0]);

  firstHalf = div5;
  secondHalf = div5 + 1;
  div11 = firstHalf;
  div12 = secondHalf;

  printf("División 11 = %d  ", div11[0]);
  printf("División 12 = %d  ", div12[0]);

  firstHalf = div6;
  secondHalf = div6 + 1;
  div13 = firstHalf;
  div14 = secondHalf;

  printf("División 13 = %d  ", div13[0]);
  printf("División 14 = %d\n\n", div14[0]);

  printf("Unión 1 = ");
  if (div7[0] > div8[0])
  {
    unión1[0] = div8[0];
    unión1[1] = div7[0];
  }
  else
  {
    unión1[0] = div7[0];
    unión1[1] = div8[0];
  }
  printf("%d, %d    ", unión1[0], unión1[1]);

  printf("Unión 2 = ");
  if (div9[0] > div10[0])
  {
    unión2[0] = div10[0];
    unión2[1] = div9[0];
  }
  else
  {
    unión2[0] = div9[0];
    unión2[1] = div10[0];
  }
  printf("%d, %d    ", unión2[0], unión2[1]);

  printf("Unión 3 = ");
  if (div11[0] > div12[0])
  {
    unión3[0] = div12[0];
    unión3[1] = div11[0];
  }
  else
  {
    unión3[0] = div11[0];
    unión3[1] = div12[0];
  }
  printf("%d, %d    ", unión3[0], unión3[1]);

  printf("Unión 4 = ");
  if (div13[0] > div14[0])
  {
    unión4[0] = div14[0];
    unión4[1] = div13[0];
  }
  else
  {
    unión4[0] = div13[0];
    unión4[1] = div14[0];
  }
  printf("%d, %d    \n\n", unión4[0], unión4[1]);

  printf("Unión 5 = ");
  unión5[0] = unión1[0];
  unión5[1] = unión1[1];
  unión5[2] = unión2[0];
  unión5[3] = unión2[1];
  if (unión5[0] > unión5[2])
  {
    int temp = unión5[0];
    unión5[0] = unión5[2];
    unión5[2] = temp;
  }
  if (unión5[0] > unión5[3])
  {
    int temp = unión5[0];
    unión5[0] = unión5[3];
    unión5[3] = temp;
  }
  if (unión5[1] > unión5[2])
  {
    int temp = unión5[1];
    unión5[1] = unión5[2];
    unión5[2] = temp;
  }
  if (unión5[1] > unión5[3])
  {
    int temp = unión5[1];
    unión5[1] = unión5[3];
    unión5[3] = temp;
  }
  if (unión5[2] > unión5[3])
  {
    int temp = unión5[2];
    unión5[2] = unión5[3];
    unión5[3] = temp;
  }
  printf("%d, %d, %d, %d    ", unión5[0], unión5[1], unión5[2], unión5[3]);

  printf("Unión 6 = ");
  unión6[0] = unión3[0];
  unión6[1] = unión3[1];
  unión6[2] = unión4[0];
  unión6[3] = unión4[1];
  if (unión6[0] > unión6[2])
  {
    int temp = unión6[0];
    unión6[0] = unión6[2];
    unión6[2] = temp;
  }
  if (unión6[0] > unión6[3])
  {
    int temp = unión6[0];
    unión6[0] = unión6[3];
    unión6[3] = temp;
  }
  if (unión6[1] > unión6[2])
  {
    int temp = unión6[1];
    unión6[1] = unión6[2];
    unión6[2] = temp;
  }
  if (unión6[1] > unión6[3])
  {
    int temp = unión6[1];
    unión6[1] = unión6[3];
    unión6[3] = temp;
  }
  if (unión6[2] > unión6[3])
  {
    int temp = unión6[2];
    unión6[2] = unión6[3];
    unión6[3] = temp;
  }
  printf("%d, %d, %d, %d    \n\n", unión6[0], unión6[1], unión6[2], unión6[3]);

  printf("Unión 7 = ");
  unión7[0] = unión5[0];
  unión7[1] = unión5[1];
  unión7[2] = unión5[2];
  unión7[3] = unión5[3];
  unión7[4] = unión6[0];
  unión7[5] = unión6[1];
  unión7[6] = unión6[2];
  unión7[7] = unión6[3];
  if (unión7[0] > unión7[4])
  {
    int temp = unión7[0];
    unión7[0] = unión7[4];
    unión7[4] = temp;
  }
  if (unión7[0] > unión7[5])
  {
    int temp = unión7[0];
    unión7[0] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[0] > unión7[6])
  {
    int temp = unión7[0];
    unión7[0] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[0] > unión7[7])
  {
    int temp = unión7[0];
    unión7[0] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[1] > unión7[4])
  {
    int temp = unión7[1];
    unión7[1] = unión7[4];
    unión7[4] = temp;
  }
  if (unión7[1] > unión7[5])
  {
    int temp = unión7[1];
    unión7[1] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[1] > unión7[6])
  {
    int temp = unión7[1];
    unión7[1] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[1] > unión7[7])
  {
    int temp = unión7[1];
    unión7[1] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[2] > unión7[4])
  {
    int temp = unión7[2];
    unión7[2] = unión7[4];
    unión7[4] = temp;
  }
  if (unión7[2] > unión7[5])
  {
    int temp = unión7[2];
    unión7[2] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[2] > unión7[6])
  {
    int temp = unión7[2];
    unión7[2] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[2] > unión7[7])
  {
    int temp = unión7[2];
    unión7[2] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[3] > unión7[4])
  {
    int temp = unión7[3];
    unión7[3] = unión7[4];
    unión7[4] = temp;
  }
  if (unión7[3] > unión7[5])
  {
    int temp = unión7[3];
    unión7[3] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[3] > unión7[6])
  {
    int temp = unión7[3];
    unión7[3] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[3] > unión7[7])
  {
    int temp = unión7[3];
    unión7[3] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[4] > unión7[5])
  {
    int temp = unión7[4];
    unión7[4] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[4] > unión7[6])
  {
    int temp = unión7[4];
    unión7[4] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[4] > unión7[7])
  {
    int temp = unión7[4];
    unión7[4] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[5] > unión7[6])
  {
    int temp = unión7[5];
    unión7[5] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[5] > unión7[7])
  {
    int temp = unión7[5];
    unión7[5] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[6] > unión7[7])
  {
    int temp = unión7[6];
    unión7[6] = unión7[7];
    unión7[7] = temp;
  }
  printf("%d, %d, %d, %d, %d, %d, %d, %d    \n\n", unión7[0], unión7[1], unión7[2], unión7[3], unión7[4], unión7[5], unión7[6], unión7[7]);
}

El resultado en la consola es el siguiente:

Andres Manco

student•

Estuve intentando un rato traducir los codigos que postearon a JavaScript y no me functiono, por alguna razon me estaban dando unos numeros "Undefined" pero encontre online la siguiente solucion que me gusto bastante, esta un poco mas corta tambien

Solucion en JavaScript

function merge(left, right){
    const arr = []

    while(left.length && right.length){
        if(left[0] < right[0]){
            arr.push(left.shift())
        }
        else{
            arr.push(right.shift())
        }
    }
    return [...arr, ...left, ...right]
}

function mergeSort(arr){
    const mid = arr.length/2

    if(arr.length < 2){
        return arr
    }
    const right = arr.splice(mid)
    return merge(mergeSort(arr), mergeSort(right))
}

const arr = [14, 7, 3, 12, 9, 11, 6, 2]
console.log(mergeSort(arr));

giordano díaz merino

student•

Hola para el reto use el codigo de javram5895 como referencia he implemente el pedido de el tamaño del array y los elementos de este por parte del usuario espero les sirva 😄

#include <stdio.h>
void datos();
void mergeSort(int a[],int i, int j);
void merge(int a[],int i1, int j1, int i2, int j2);


int a[50],n,i;

int main(){
	
	datos(a,n);
	mergeSort(a,0,n-1);
	
	printf("\n El arreglo ordenado es: \n");
	for(i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}


void datos(){
	
 	int i,elemento;
 	printf("Ingresa el numeros del arreglo: \n");
 	scanf("%d",&n);
 	
 	for(i=0; i<n ; i++){
 		
 		printf("Ingresa el elemento: ");
		scanf("%d",&elemento);
		a[i]=elemento;	
	 }
	 
	printf("El arreglo en desorden es: \n");
	
	for(i=0; i<n;i++){
		
		printf("%i ",a[i]);
		
	}
 	
 }
 
 void mergeSort(int a[],int i,int j){//divide el array a la mitad
 
 	int mid;//mid es la mitad del array a,i  es inicio y j final del array
 	
 	if(i<j){
 		
 		mid=(i+j)/2;
 		mergeSort(a,i,mid);//mitad izquierda
 		mergeSort(a,mid+1,j);//mitad derecha
 		merge(a,i,mid,mid+1,j);//une las dos mitades
 		
	 }
 }
 
 void merge(int a[],int i1, int j1, int i2, int j2){
 	
 	int temp[50];//array temporal
 	int i,j,k;
 	i=i1;  //inicio de la primera mitad del array
 	j=i2;  //inicio de la segunda mitad del array
 	k=0;
 	
 	while (i<=j1 && j<=j2){
 		
 		if(a[i]<a[j]){
 			temp[k++]=a[i++];
		 }
		 else{
		 	temp[k++]=a[j++];
		 }
	 }
	 
	while(i<=j1){
		temp[k++]=a[i++];
	}
	while(j<=j2){
		temp[k++]=a[j++];
	}
	
	for(i=i1,j=0;i<=j2;i++,j++){
		a[i]=temp[j];
	}
		
 }```

Sergio Velasquez

student•

He aca mi codigo. Se diferencia de otros en que el merge y el mergeSort utilizan como parametros el tamaño de los arreglos, y dentro del mergeSort se declaran 2 arrays (Left, Right), los cuales son utilizados para ir asignando los valores de cada división y subdivision del arreglo de entrada.
Quizas es un poco mas extenso, que otros, pero siento que es un poco mas facil de entender en principio.

void printArray(int vector_entrada[], int size)
{
    int i;
    for ( i = 0; i < size; i++)
    {
        printf("%d\n", vector_entrada[i]);
    }
    printf("fin del arreglo\n");

}

void merge(int vector_entrada[], int Left[],int Right[],int size, int leftSize, int rightSize)
{
    int leftIndex = 0;
    int rightIndex = 0;
    int index = 0;

    for (index = 0; index < size; index++)
    {
        if (leftIndex==leftSize)
        {
          vector_entrada[index] = Right[rightIndex];
          rightIndex++;
        }
        else if (rightIndex==rightSize)
        {
          vector_entrada[index] = Left[leftIndex];
          leftIndex++;
        }
        else if (Left[leftIndex]>=Right[rightIndex])
        {
          vector_entrada[index] = Right[rightIndex];
          rightIndex++;
        }
        else if(Right[rightIndex]>=Left[leftIndex])
        {
          vector_entrada[index] = Left[leftIndex];
          leftIndex++;
        }
    }
}   

void mergeSort(int vector_entrada[], int n)
{

    if (n == 1)
    {
      return;
    }

    int middle = n/2;
    int leftSize = middle;
    int rightSize = n - leftSize;
    int index, rightIndex;
    int Left[leftSize], Right[rightSize];

    for (index = 0; index < middle; index++)
    {
         Left[index] = vector_entrada[index];
    }
    rightIndex = 0;
    for (index = middle; index < n; index++)
    {
        Right[rightIndex] = vector_entrada[index];
        rightIndex++;
    }
    mergeSort(Left,middle);
    mergeSort(Right,rightSize);
    merge(vector_entrada, Left,Right,n,leftSize,rightSize);
}

int main()
{
  int vector_entrada[]= {0,2,10,5,-6,7,20,2};
  int n = sizeof(vector_entrada)/sizeof(vector_entrada[0]);
  mergeSort(vector_entrada,n);
  printf("Arreglo ordenado = \n");
  printArray(vector_entrada, n);
  printf("\n");
  return 0;
}```

Nicolás Díaz

student•

La función exponencial(color rojo) no seria “n” el exponente?, siendo la base fija, en este caso el “2”, ya que la gráfica se mueve en función del tiempo?

Jesus Fernandez Alpizar

student•

anexo mi codigo,

#include <stdio.h>

int leer_arreglo(int vector_entrada[], int tot_pos)
{
	int i;
	
	for(i=0;i<tot_pos;i++)
	{
		printf("Dame la posicion %d :",i+1);
		scanf("%d",&vector_entrada[i]);
		printf("  \n");
	}
}

int printArray(int vector_entrada[], int size)
{
	int h;
	
	for (h=0;h<=size;h++) 
	{
		printf("%d ",vector_entrada[h]);	
	}
	printf("arreglo\n");	
}

int cambiar_pos(int *n1, int *n2)
{
	int temp,temp2; 

	temp= *n1;
	*n1 = *n2;
	*n2 = temp;	
}

int Ordena_arreglo(int l,int v_of,int c_pos, int a, int b,int v_e[])
{
    
  int i,j;
   printf("Ordena arreglo  \n");
   printf("b %d a %d \n",b,a);
   	i=a;
   do
   { 
        j=b;
        while (j>i)
	 	{
		    if (v_e[j-1]>v_e[j])
			 {
			  cambiar_pos(&v_e[j-1],&v_e[j]);
			} 	 
			j=j-1; 	  
    	}
    	printArray(v_e,b);
    	printf("\n");
    	i++;
    }while (i<b);
    c_pos=c_pos+1;
    a=a+v_of;
    b= (c_pos * v_of)-1;
   
    if (b <= l)
	{
     Ordena_arreglo(l,v_of,c_pos,a,b,v_e);
	 }
}
        
int DividVence(int v_e[], int max_arr,int s_dv[],int apta_stk,int colum_pos,int ini_arv)
{
	
	/* *****revisar la recurrencia****** */
	int b,a;
	int fin_arv;
	int valor_offset,wt;
 
    while (apta_stk >0)
    {
    valor_offset=s_dv[apta_stk-1];
    fin_arv=(colum_pos * valor_offset)-1;
    printf("v_of %d fin_arv %d ini_arv %d apuntador %d\n",valor_offset,fin_arv,ini_arv,apta_stk);
    printf("Divide y Venseras proceso  \n");
   /* scanf("%d",wt);*/
    Ordena_arreglo(max_arr,valor_offset,colum_pos,ini_arv,fin_arv,v_e);
    
    apta_stk = apta_stk-1;
    }
}

int clear_arr(int v_e[], int max)
{
	int j;
	
	for (j=0;j<max;j++)
	 {
	 	v_e[j]=0;
	 }
}
    


int main()
{
	
	int v_e[8];
	int s_dv[4];
	int m = sizeof(s_dv)/sizeof(s_dv[0]);
	int n = sizeof(v_e)/sizeof(v_e[0]);
    int div_arr,i,inx,h;
    
    i=0;
    div_arr=n;
    
    while (div_arr>=2)
	{
		s_dv[i]= div_arr;
      	div_arr=div_arr/2;
		i++;
		inx=i;	
	}
    clear_arr(v_e,n);
    printf("Vector Limpio \n");
    printArray(v_e,n);
    
	printf("Stack = %d \n",inx);
	printArray(s_dv,inx);
 
 printf("h %d inx %d\n",h,inx);
 
    for (h=0;h<inx;h++)
	{
     leer_arreglo(v_e,n);
     
    printf("Divide y Venceras \n");
    
 	 DividVence(v_e,n,s_dv,inx,1,0);
 	
 	 printf("Arreglo ordenado = \n");
 	 printArray(v_e, n-1);
 	 printf("\n");
    }
	return 0;
}

Jesus Fernandez Alpizar

student•

anexo mi codigo,

#include &lt;stdio.h&gt;

int leer_arreglo(int vector_entrada[], int tot_pos)
{
	int i;
	
	for(i=0;i&lt;tot_pos;i++) {="" printf("dame="" la="" posicion="" %d="" :",i+1);="" scanf("%d",&amp;vector_entrada[i]);="" printf("="" \n");="" }="" }="" int="" printarray(int="" vector_entrada[],="" int="" size)="" {="" int="" h;="" for="" (h="0;h&amp;lt;=size;h++)" {="" printf("%d="" ",vector_entrada[h]);="" }="" printf("arreglo\n");="" }="" int="" cambiar_pos(int="" *n1,="" int="" *n2)="" {="" int="" temp,temp2;="" temp="*n1;" *n1="*n2;" *n2="temp;" }="" int="" ordena_arreglo(int="" l,int="" v_of,int="" c_pos,="" int="" a,="" int="" b,int="" v_e[])="" {="" int="" i,j;="" printf("ordena="" arreglo="" \n");="" printf("b="" %d="" a="" %d="" \n",b,a);="" i="a;" do="" {="" j="b;" while="" (j=""&gt;i)
	 	{
		    if (v_e[j-1]&gt;v_e[j])
			 {
			  cambiar_pos(&amp;v_e[j-1],&amp;v_e[j]);
			} 	 
			j=j-1; 	  
    	}
    	printArray(v_e,b);
    	printf("\n");
    	i++;
    }while (i&lt;b); c_pos="c_pos+1;" a="a+v_of;" b="(c_pos" *="" v_of)-1;="" if="" (b="" &lt;="l)" {="" ordena_arreglo(l,v_of,c_pos,a,b,v_e);="" }="" }="" int="" dividvence(int="" v_e[],="" int="" max_arr,int="" s_dv[],int="" apta_stk,int="" colum_pos,int="" ini_arv)="" {="" *="" *****revisar="" la="" recurrencia******="" *="" int="" b,a;="" int="" fin_arv;="" int="" valor_offset,wt;="" while="" (apta_stk=""&gt;0)
    {
    valor_offset=s_dv[apta_stk-1];
    fin_arv=(colum_pos * valor_offset)-1;
    printf("v_of %d fin_arv %d ini_arv %d apuntador %d\n",valor_offset,fin_arv,ini_arv,apta_stk);
    printf("Divide y Venseras proceso  \n");
   /* scanf("%d",wt);*/
    Ordena_arreglo(max_arr,valor_offset,colum_pos,ini_arv,fin_arv,v_e);
    
    apta_stk = apta_stk-1;
    }
}

int clear_arr(int v_e[], int max)
{
	int j;
	
	for (j=0;j&lt;max;j++) {="" v_e[j]="0;" }="" }="" int="" main()="" {="" int="" v_e[8];="" int="" s_dv[4];="" int="" m="sizeof(s_dv)/sizeof(s_dv[0]);" int="" n="sizeof(v_e)/sizeof(v_e[0]);" int="" div_arr,i,inx,h;="" i="0;" div_arr="n;" while="" (div_arr=""&gt;=2)
	{
		s_dv[i]= div_arr;
      	div_arr=div_arr/2;
		i++;
		inx=i;	
	}
    clear_arr(v_e,n);
    printf("Vector Limpio \n");
    printArray(v_e,n);
    
	printf("Stack = %d \n",inx);
	printArray(s_dv,inx);
 
 printf("h %d inx %d\n",h,inx);
 
    for (h=0;h

CIRO VLADIMIR ARREOLA CAMACHO

student•

a mi me sirvió mucho la explicación e implementación de este algoritmo (merge sort) que viene acá

para que se den una idea de la diferencia en el rendimiento de cada algoritmo, para el siguiente array de 20 elementos

int numeros[] = {1, 2, 3, 3, 5, 61, 7, 90, 100, 120, 300, 3, 3, 21, 23, 34, 87, 43, 23};

bubble-sort

$ ./bin/bubble-sort 
1 2 3 3 5 61 7 90 100 120 300 3 3 21 23 34 87 43 23 1 
1 1 2 3 3 3 3 5 7 21 23 23 34 43 61 87 90 100 120 300 
ordenado en 190 ciclos

merge-sort

./bin/merge-sort 
1 2 3 3 5 61 7 90 100 120 300 3 3 21 23 34 87 43 23 1 
1 1 2 3 3 3 3 5 7 21 23 23 34 43 61 87 90 100 120 300 
ordenado en 19 ciclos

aunque solo tomé en cuenta los ciclos de la función principal.
Para un análisis más detallado pueden ver el siguiente artículo (o basta con ver el GIF que compartieron en los comentarios de clases anteriores jeje)

Julio Cardenas

student•

Genere un vector aleatorio de 50,000 posiciones, lo ordeno de inmediato e hizo 768,028 comparaciones. Esto es muy cercano al valor teorico de 50,000*log2(50,000) = 780,482

Aqui les dejo mi codigo

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int maximo;
int i;
int j;
int auxiliar;
int comparaciones;
int movimientos;

int numeroAleatorio(int min, int max) {
    return (min + (rand() % (max + 1 - min)));
}

void merge(int *a, int inicio, int fin) {
    if (inicio >= fin) {
        comparaciones++;
        return;
    }
    int medio;
    int i;
    int j;
    int k;

    medio = (inicio + fin)/2;
    i = inicio;
    j = medio + 1;
    k = 0;

    merge(a, inicio, medio);
    merge(a, medio + 1, fin);
    int copia[fin];

    //hace merge de las dos mitades del vector
    while ((i <= medio) && (j <= fin)) {
        comparaciones++;
        if (a[i] < a[j]) {
            copia[k] = a[i];
            i++;
            k++;
            movimientos++;
        } else {
            copia[k] = a[j];
            j++;
            k++;
            movimientos++;
        }
    }

    //dependiendo de cual mitad acabo primero, termina la otra
    if (i > medio) {
        while (j <= fin){
            copia[k] = a[j];
            j++;
            k++;
            movimientos++;
        }
    }
    if (j > fin) {
        while (i <= medio){
            copia[k] = a[i];
            i++;
            k++;
            movimientos++;
        }
    }

    // finalmente se carga copia en el vector original
    for (i = inicio; i <= fin; i++) {
        a[i] = copia[i - inicio];
    }

}


int main() {
    printf("Por favor digite el tamaño del vector\n");
    scanf("%d",&maximo);

    int vector[maximo];
    srand(time(NULL));
    for (i = 0; i < maximo; i++) {
        vector[i] =numeroAleatorio(1, 500);
    }

    comparaciones = 0;
    movimientos = 0;

    merge(vector, 0, maximo - 1);

    for (i = 0; i < maximo; i++) {
        printf("posicion: %3d  valor: %3d\n", i, vector[i]);
    }

    printf("Para un vector de %5d posiciones se efectuaron %8d comparaciones y %8d movimientos\n", maximo, comparaciones, movimientos);
    return 0;
}

Luis Morales

student•

Esta es mi aportación del algoritmo Merge Sort:

#include <stdio.h>

int x;

int printArray(int arraySize, int *array, int sorted)
{
    printf("\n");
    if (sorted)
        printf("Sorted array: \n");
    else
        printf("Unsorted array: \n");

    for (x=0; x < arraySize; x++)
    {
        printf("%d ", array[x]);
    }

    return 0;
}

int * MergeSort(int *arrayArg, int arraySize)
{
    int array[arraySize];
    
    for (x = 0; x < arraySize; x++)
    {
        array[x] = *(arrayArg + x);
    }

    printf("");
    if (arraySize > 1)
    {
        int leftMiddleSize = arraySize / 2;
        int rightMiddleSize = arraySize - leftMiddleSize;

        int leftMiddleArray[leftMiddleSize];
        int rightMiddleArray[rightMiddleSize];
        int i;
        int counter = 0;

        for (i=0; i < leftMiddleSize; i++)
        {
            leftMiddleArray[i] = array[i];
        }
        
        for (i=0; i < rightMiddleSize; i++)
        {
            counter = i + leftMiddleSize;
            rightMiddleArray[i] = array[counter];
        }
        
        int *tempArray;

        tempArray = MergeSort(leftMiddleArray, leftMiddleSize);

        for (i=0; i < leftMiddleSize; i++)
        {
            leftMiddleArray[i] = *(tempArray + i);
        }

        tempArray = MergeSort(rightMiddleArray, rightMiddleSize);

        for (i=0; i < rightMiddleSize; i++)
        {
            rightMiddleArray[i] = *(tempArray + i);
        }

        int leftIndex = 0;
        int rightIndex = 0;

        // Merge array
        for (i = 0; i < arraySize; i++)
        {
            if (leftIndex >= leftMiddleSize)
            {
                array[i] = rightMiddleArray[rightIndex];
                rightIndex++;
            }
            else if (rightIndex >= rightMiddleSize)
            {
                array[i] = leftMiddleArray[leftIndex];
                leftIndex++;
            }
            else if (leftMiddleArray[leftIndex] < rightMiddleArray[rightIndex])
            {
                array[i] = leftMiddleArray[leftIndex];
                leftIndex++;
            }
            else
            {
                array[i] = rightMiddleArray[rightIndex];
                rightIndex++;
            }
       }
        
        arrayArg = &array[0];

    }

    return arrayArg;
}

int main(void)
{
    printf("WELCOME TO MERGE SORT\n");
    
    int arraySize;
    printf("Set the numbers amount you want to sort:\n");
    scanf("%d", &arraySize);
       
    int array[arraySize];

    int numberInserted;
    for (x=0; x < arraySize; x++)
    {
        printf("insert the %d number: ", x + 1);
        scanf("%d", &numberInserted);

        array[x] = numberInserted;

        printf("\n");
    }

    printArray(arraySize, array, 0);

    printf("\nOrdering array...\n");
    
    int *orderedArray;
    orderedArray = MergeSort(array, arraySize);

    for (x = 0; x < arraySize; x++)
    {
        array[x] = *(orderedArray + x);
    }

    printArray(arraySize, array, 1);

    return 0;
}

Diego Adrián Sánchez Gutiérrez

student•

bien al fin la explicación de recursividad

Gustavo Gonzalez

student•

Este algoritmo sirve solamente para casos donde la cantidad de datos es par?

Eulises Brazón

student•

Marge Sort, aqui esta un poco mas de la explicacion de este algoritmo de ordenamiento.

Alex Osuna

student•

Disculpen, pero el curso no puede depender de las sesiones en vivo, si estas no se graban para estar disponibles después, Simplemente no tiene sentido.

Ricardo Celis

teacher•

Pero si se graban, por ejemplo esta

Diego Forero

Team Platzi•

Todas las clases quedan grabadas, entran a proceso de post producción y luego son publicadas, por eso tardan a veces un poco en publicarse, pero todo siempre queda grabado y se publica.

Sergio Santiago González

student•

Pasos para implementar Divide y Vencerás.

Sergio Santiago González

student•

Funciones recursivas y el uso de la estructura de datos Stack.

Adrián Lucero

student•

para implementar el algoritmo de merge sort hay que usar la libreria de <vector> ?

Ricardo Celis

teacher•

Hola Rixda! No necesariamente, puedes hacerlo utilizando sólo:

#include<stdlib.h>
#include<stdio.h>

Adrián Lucero

student•

asi me quedo

#include<stdio.h>
 
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
 
int main()
{
    int a[30],n,i;
    printf("Enter no of elements:");
    scanf("%d",&n);
    printf("Enter array elements:");
    
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        
    mergesort(a,0,n-1);
    
    printf("\nSorted array is :");
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
        
    return 0;
}
 
void mergesort(int a[],int i,int j)//divide el array a la mitad
{
    int mid;// mid es la mitad del array
    // a es el array, i es el inicio del array y j es el final del array       
    if(i<j)
    {
        mid=(i+j)/2;
        mergesort(a,i,mid);        //mitad izquierda
        mergesort(a,mid+1,j);    //mitad derecha
        merge(a,i,mid,mid+1,j);    //une las dos mitades
    }
}
 
void merge(int a[],int i1,int j1,int i2,int j2)
{
    int temp[50];    //array temporal
    int i,j,k;
    i=i1;    //inicio de la primera mitad del array
    j=i2;    //inicio de la segunda mitad del array
    k=0;
    
    while(i<=j1 && j<=j2) // mientras i sea mas pequeno o igual que el final de la primera mitad
                          // y j sea mas pequeno que el final de la segunda mitad, has lo siguiente
    {
        if(a[i]<a[j])// Este if es solo para la primera iteracion, cuando los arrays estan separados totalmente 
            temp[k++]=a[i++]; //si a[i] es mas pequeno que a[j] agrega primero el a[i]
        else
            temp[k++]=a[j++]; //si a[j] es mas pequeno que a[i] agrega primero el a[j]
    }
    
    while(i<=j1)// estos dos whiles son para el resto de los arrays, ya cuando se estan uninendo, es decir la segunda iteracion en adelante   
        temp[k++]=a[i++];
        
    while(j<=j2)    
        temp[k++]=a[j++];
        
    //Transferri elementos del temp[] al a[]
    for(i=i1,j=0;i<=j2;i++,j++)
        a[i]=temp[j];
}```

#include <stdio.h>

int main()
{
  int vector_entrada[] = {14, 7, 3, 12, 9, 11, 6, 2};
  int *firstHalf = vector_entrada;
  int *secondHalf = vector_entrada + 4;
  int *div1 = firstHalf;
  int *div2 = secondHalf;
  int *div3, *div4, *div5, *div6, *div7, *div8, *div9, *div10, *div11, *div12, *div13, *div14;

  int unión1[2], unión2[2], unión3[2], unión4[2], unión5[4], unión6[4], unión7[8];

  printf("\n");
  printf("Arreglo original = ");
  for (int i = 0; i < 8; i++)
  {
    if (i != 7)
    {
      printf("%d, ", vector_entrada[i]);
    }
    else
    {
      printf("%d\n", vector_entrada[i]);
    }
  }
  printf("\n");

  printf("División 1 = ");
  for (int i = 0; i < 4; i++)
  {
    if (i != 3)
    {
      printf("%d, ", div1[i]);
    }
    else
    {
      printf("%d          ", div1[i]);
    }
  }

  printf("División 2 = ");
  for (int i = 0; i < 4; i++)
  {
    if (i != 3)
    {
      printf("%d, ", div2[i]);
    }
    else
    {
      printf("%d\n", div2[i]);
    }
  }
  printf("\n");

  firstHalf = div1;
  secondHalf = div1 + 2;
  div3 = firstHalf;
  div4 = secondHalf;

  printf("División 3 = ");
  for (int i = 0; i < 2; i++)
  {
    if (i != 1)
    {
      printf("%d, ", div3[i]);
    }
    else
    {
      printf("%d    ", div3[i]);
    }
  }

  printf("División 4 = ");
  for (int i = 0; i < 2; i++)
  {
    if (i != 1)
    {
      printf("%d, ", div4[i]);
    }
    else
    {
      printf("%d    ", div4[i]);
    }
  }

  firstHalf = div2;
  secondHalf = div2 + 2;
  div5 = firstHalf;
  div6 = secondHalf;

  printf("División 5 = ");
  for (int i = 0; i < 2; i++)
  {
    if (i != 1)
    {
      printf("%d, ", div5[i]);
    }
    else
    {
      printf("%d    ", div5[i]);
    }
  }

  printf("División 6 = ");
  for (int i = 0; i < 2; i++)
  {
    if (i != 1)
    {
      printf("%d, ", div6[i]);
    }
    else
    {
      printf("%d\n", div6[i]);
    }
  }
  printf("\n");

  firstHalf = div3;
  secondHalf = div3 + 1;
  div7 = firstHalf;
  div8 = secondHalf;

  printf("División 7 = %d  ", div7[0]);
  printf("División 8 = %d  ", div8[0]);

  firstHalf = div4;
  secondHalf = div4 + 1;
  div9 = firstHalf;
  div10 = secondHalf;

  printf("División 9 = %d  ", div9[0]);
  printf("División 10 = %d  ", div10[0]);

  firstHalf = div5;
  secondHalf = div5 + 1;
  div11 = firstHalf;
  div12 = secondHalf;

  printf("División 11 = %d  ", div11[0]);
  printf("División 12 = %d  ", div12[0]);

  firstHalf = div6;
  secondHalf = div6 + 1;
  div13 = firstHalf;
  div14 = secondHalf;

  printf("División 13 = %d  ", div13[0]);
  printf("División 14 = %d\n\n", div14[0]);

  printf("Unión 1 = ");
  if (div7[0] > div8[0])
  {
    unión1[0] = div8[0];
    unión1[1] = div7[0];
  }
  else
  {
    unión1[0] = div7[0];
    unión1[1] = div8[0];
  }
  printf("%d, %d    ", unión1[0], unión1[1]);

  printf("Unión 2 = ");
  if (div9[0] > div10[0])
  {
    unión2[0] = div10[0];
    unión2[1] = div9[0];
  }
  else
  {
    unión2[0] = div9[0];
    unión2[1] = div10[0];
  }
  printf("%d, %d    ", unión2[0], unión2[1]);

  printf("Unión 3 = ");
  if (div11[0] > div12[0])
  {
    unión3[0] = div12[0];
    unión3[1] = div11[0];
  }
  else
  {
    unión3[0] = div11[0];
    unión3[1] = div12[0];
  }
  printf("%d, %d    ", unión3[0], unión3[1]);

  printf("Unión 4 = ");
  if (div13[0] > div14[0])
  {
    unión4[0] = div14[0];
    unión4[1] = div13[0];
  }
  else
  {
    unión4[0] = div13[0];
    unión4[1] = div14[0];
  }
  printf("%d, %d    \n\n", unión4[0], unión4[1]);

  printf("Unión 5 = ");
  unión5[0] = unión1[0];
  unión5[1] = unión1[1];
  unión5[2] = unión2[0];
  unión5[3] = unión2[1];
  if (unión5[0] > unión5[2])
  {
    int temp = unión5[0];
    unión5[0] = unión5[2];
    unión5[2] = temp;
  }
  if (unión5[0] > unión5[3])
  {
    int temp = unión5[0];
    unión5[0] = unión5[3];
    unión5[3] = temp;
  }
  if (unión5[1] > unión5[2])
  {
    int temp = unión5[1];
    unión5[1] = unión5[2];
    unión5[2] = temp;
  }
  if (unión5[1] > unión5[3])
  {
    int temp = unión5[1];
    unión5[1] = unión5[3];
    unión5[3] = temp;
  }
  if (unión5[2] > unión5[3])
  {
    int temp = unión5[2];
    unión5[2] = unión5[3];
    unión5[3] = temp;
  }
  printf("%d, %d, %d, %d    ", unión5[0], unión5[1], unión5[2], unión5[3]);

  printf("Unión 6 = ");
  unión6[0] = unión3[0];
  unión6[1] = unión3[1];
  unión6[2] = unión4[0];
  unión6[3] = unión4[1];
  if (unión6[0] > unión6[2])
  {
    int temp = unión6[0];
    unión6[0] = unión6[2];
    unión6[2] = temp;
  }
  if (unión6[0] > unión6[3])
  {
    int temp = unión6[0];
    unión6[0] = unión6[3];
    unión6[3] = temp;
  }
  if (unión6[1] > unión6[2])
  {
    int temp = unión6[1];
    unión6[1] = unión6[2];
    unión6[2] = temp;
  }
  if (unión6[1] > unión6[3])
  {
    int temp = unión6[1];
    unión6[1] = unión6[3];
    unión6[3] = temp;
  }
  if (unión6[2] > unión6[3])
  {
    int temp = unión6[2];
    unión6[2] = unión6[3];
    unión6[3] = temp;
  }
  printf("%d, %d, %d, %d    \n\n", unión6[0], unión6[1], unión6[2], unión6[3]);

  printf("Unión 7 = ");
  unión7[0] = unión5[0];
  unión7[1] = unión5[1];
  unión7[2] = unión5[2];
  unión7[3] = unión5[3];
  unión7[4] = unión6[0];
  unión7[5] = unión6[1];
  unión7[6] = unión6[2];
  unión7[7] = unión6[3];
  if (unión7[0] > unión7[4])
  {
    int temp = unión7[0];
    unión7[0] = unión7[4];
    unión7[4] = temp;
  }
  if (unión7[0] > unión7[5])
  {
    int temp = unión7[0];
    unión7[0] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[0] > unión7[6])
  {
    int temp = unión7[0];
    unión7[0] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[0] > unión7[7])
  {
    int temp = unión7[0];
    unión7[0] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[1] > unión7[4])
  {
    int temp = unión7[1];
    unión7[1] = unión7[4];
    unión7[4] = temp;
  }
  if (unión7[1] > unión7[5])
  {
    int temp = unión7[1];
    unión7[1] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[1] > unión7[6])
  {
    int temp = unión7[1];
    unión7[1] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[1] > unión7[7])
  {
    int temp = unión7[1];
    unión7[1] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[2] > unión7[4])
  {
    int temp = unión7[2];
    unión7[2] = unión7[4];
    unión7[4] = temp;
  }
  if (unión7[2] > unión7[5])
  {
    int temp = unión7[2];
    unión7[2] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[2] > unión7[6])
  {
    int temp = unión7[2];
    unión7[2] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[2] > unión7[7])
  {
    int temp = unión7[2];
    unión7[2] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[3] > unión7[4])
  {
    int temp = unión7[3];
    unión7[3] = unión7[4];
    unión7[4] = temp;
  }
  if (unión7[3] > unión7[5])
  {
    int temp = unión7[3];
    unión7[3] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[3] > unión7[6])
  {
    int temp = unión7[3];
    unión7[3] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[3] > unión7[7])
  {
    int temp = unión7[3];
    unión7[3] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[4] > unión7[5])
  {
    int temp = unión7[4];
    unión7[4] = unión7[5];
    unión7[5] = temp;
  }
  if (unión7[4] > unión7[6])
  {
    int temp = unión7[4];
    unión7[4] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[4] > unión7[7])
  {
    int temp = unión7[4];
    unión7[4] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[5] > unión7[6])
  {
    int temp = unión7[5];
    unión7[5] = unión7[6];
    unión7[6] = temp;
  }
  if (unión7[5] > unión7[7])
  {
    int temp = unión7[5];
    unión7[5] = unión7[7];
    unión7[7] = temp;
  }
  if (unión7[6] > unión7[7])
  {
    int temp = unión7[6];
    unión7[6] = unión7[7];
    unión7[7] = temp;
  }
  printf("%d, %d, %d, %d, %d, %d, %d, %d    \n\n", unión7[0], unión7[1], unión7[2], unión7[3], unión7[4], unión7[5], unión7[6], unión7[7]);
}

function merge(left, right){
    const arr = []

    while(left.length && right.length){
        if(left[0] < right[0]){
            arr.push(left.shift())
        }
        else{
            arr.push(right.shift())
        }
    }
    return [...arr, ...left, ...right]
}

function mergeSort(arr){
    const mid = arr.length/2

    if(arr.length < 2){
        return arr
    }
    const right = arr.splice(mid)
    return merge(mergeSort(arr), mergeSort(right))
}

const arr = [14, 7, 3, 12, 9, 11, 6, 2]
console.log(mergeSort(arr));

#include <stdio.h>
void datos();
void mergeSort(int a[],int i, int j);
void merge(int a[],int i1, int j1, int i2, int j2);


int a[50],n,i;

int main(){
	
	datos(a,n);
	mergeSort(a,0,n-1);
	
	printf("\n El arreglo ordenado es: \n");
	for(i=0;i<n;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}


void datos(){
	
 	int i,elemento;
 	printf("Ingresa el numeros del arreglo: \n");
 	scanf("%d",&n);
 	
 	for(i=0; i<n ; i++){
 		
 		printf("Ingresa el elemento: ");
		scanf("%d",&elemento);
		a[i]=elemento;	
	 }
	 
	printf("El arreglo en desorden es: \n");
	
	for(i=0; i<n;i++){
		
		printf("%i ",a[i]);
		
	}
 	
 }
 
 void mergeSort(int a[],int i,int j){//divide el array a la mitad
 
 	int mid;//mid es la mitad del array a,i  es inicio y j final del array
 	
 	if(i<j){
 		
 		mid=(i+j)/2;
 		mergeSort(a,i,mid);//mitad izquierda
 		mergeSort(a,mid+1,j);//mitad derecha
 		merge(a,i,mid,mid+1,j);//une las dos mitades
 		
	 }
 }
 
 void merge(int a[],int i1, int j1, int i2, int j2){
 	
 	int temp[50];//array temporal
 	int i,j,k;
 	i=i1;  //inicio de la primera mitad del array
 	j=i2;  //inicio de la segunda mitad del array
 	k=0;
 	
 	while (i<=j1 && j<=j2){
 		
 		if(a[i]<a[j]){
 			temp[k++]=a[i++];
		 }
		 else{
		 	temp[k++]=a[j++];
		 }
	 }
	 
	while(i<=j1){
		temp[k++]=a[i++];
	}
	while(j<=j2){
		temp[k++]=a[j++];
	}
	
	for(i=i1,j=0;i<=j2;i++,j++){
		a[i]=temp[j];
	}
		
 }```

void printArray(int vector_entrada[], int size)
{
    int i;
    for ( i = 0; i < size; i++)
    {
        printf("%d\n", vector_entrada[i]);
    }
    printf("fin del arreglo\n");

}

void merge(int vector_entrada[], int Left[],int Right[],int size, int leftSize, int rightSize)
{
    int leftIndex = 0;
    int rightIndex = 0;
    int index = 0;

    for (index = 0; index < size; index++)
    {
        if (leftIndex==leftSize)
        {
          vector_entrada[index] = Right[rightIndex];
          rightIndex++;
        }
        else if (rightIndex==rightSize)
        {
          vector_entrada[index] = Left[leftIndex];
          leftIndex++;
        }
        else if (Left[leftIndex]>=Right[rightIndex])
        {
          vector_entrada[index] = Right[rightIndex];
          rightIndex++;
        }
        else if(Right[rightIndex]>=Left[leftIndex])
        {
          vector_entrada[index] = Left[leftIndex];
          leftIndex++;
        }
    }
}   

void mergeSort(int vector_entrada[], int n)
{

    if (n == 1)
    {
      return;
    }

    int middle = n/2;
    int leftSize = middle;
    int rightSize = n - leftSize;
    int index, rightIndex;
    int Left[leftSize], Right[rightSize];

    for (index = 0; index < middle; index++)
    {
         Left[index] = vector_entrada[index];
    }
    rightIndex = 0;
    for (index = middle; index < n; index++)
    {
        Right[rightIndex] = vector_entrada[index];
        rightIndex++;
    }
    mergeSort(Left,middle);
    mergeSort(Right,rightSize);
    merge(vector_entrada, Left,Right,n,leftSize,rightSize);
}

int main()
{
  int vector_entrada[]= {0,2,10,5,-6,7,20,2};
  int n = sizeof(vector_entrada)/sizeof(vector_entrada[0]);
  mergeSort(vector_entrada,n);
  printf("Arreglo ordenado = \n");
  printArray(vector_entrada, n);
  printf("\n");
  return 0;
}```

#include <stdio.h>

int leer_arreglo(int vector_entrada[], int tot_pos)
{
	int i;
	
	for(i=0;i<tot_pos;i++)
	{
		printf("Dame la posicion %d :",i+1);
		scanf("%d",&vector_entrada[i]);
		printf("  \n");
	}
}

int printArray(int vector_entrada[], int size)
{
	int h;
	
	for (h=0;h<=size;h++) 
	{
		printf("%d ",vector_entrada[h]);	
	}
	printf("arreglo\n");	
}

int cambiar_pos(int *n1, int *n2)
{
	int temp,temp2; 

	temp= *n1;
	*n1 = *n2;
	*n2 = temp;	
}

int Ordena_arreglo(int l,int v_of,int c_pos, int a, int b,int v_e[])
{
    
  int i,j;
   printf("Ordena arreglo  \n");
   printf("b %d a %d \n",b,a);
   	i=a;
   do
   { 
        j=b;
        while (j>i)
	 	{
		    if (v_e[j-1]>v_e[j])
			 {
			  cambiar_pos(&v_e[j-1],&v_e[j]);
			} 	 
			j=j-1; 	  
    	}
    	printArray(v_e,b);
    	printf("\n");
    	i++;
    }while (i<b);
    c_pos=c_pos+1;
    a=a+v_of;
    b= (c_pos * v_of)-1;
   
    if (b <= l)
	{
     Ordena_arreglo(l,v_of,c_pos,a,b,v_e);
	 }
}
        
int DividVence(int v_e[], int max_arr,int s_dv[],int apta_stk,int colum_pos,int ini_arv)
{
	
	/* *****revisar la recurrencia****** */
	int b,a;
	int fin_arv;
	int valor_offset,wt;
 
    while (apta_stk >0)
    {
    valor_offset=s_dv[apta_stk-1];
    fin_arv=(colum_pos * valor_offset)-1;
    printf("v_of %d fin_arv %d ini_arv %d apuntador %d\n",valor_offset,fin_arv,ini_arv,apta_stk);
    printf("Divide y Venseras proceso  \n");
   /* scanf("%d",wt);*/
    Ordena_arreglo(max_arr,valor_offset,colum_pos,ini_arv,fin_arv,v_e);
    
    apta_stk = apta_stk-1;
    }
}

int clear_arr(int v_e[], int max)
{
	int j;
	
	for (j=0;j<max;j++)
	 {
	 	v_e[j]=0;
	 }
}
    


int main()
{
	
	int v_e[8];
	int s_dv[4];
	int m = sizeof(s_dv)/sizeof(s_dv[0]);
	int n = sizeof(v_e)/sizeof(v_e[0]);
    int div_arr,i,inx,h;
    
    i=0;
    div_arr=n;
    
    while (div_arr>=2)
	{
		s_dv[i]= div_arr;
      	div_arr=div_arr/2;
		i++;
		inx=i;	
	}
    clear_arr(v_e,n);
    printf("Vector Limpio \n");
    printArray(v_e,n);
    
	printf("Stack = %d \n",inx);
	printArray(s_dv,inx);
 
 printf("h %d inx %d\n",h,inx);
 
    for (h=0;h<inx;h++)
	{
     leer_arreglo(v_e,n);
     
    printf("Divide y Venceras \n");
    
 	 DividVence(v_e,n,s_dv,inx,1,0);
 	
 	 printf("Arreglo ordenado = \n");
 	 printArray(v_e, n-1);
 	 printf("\n");
    }
	return 0;
}

#include &lt;stdio.h&gt;

int leer_arreglo(int vector_entrada[], int tot_pos)
{
	int i;
	
	for(i=0;i&lt;tot_pos;i++) {="" printf("dame="" la="" posicion="" %d="" :",i+1);="" scanf("%d",&amp;vector_entrada[i]);="" printf("="" \n");="" }="" }="" int="" printarray(int="" vector_entrada[],="" int="" size)="" {="" int="" h;="" for="" (h="0;h&amp;lt;=size;h++)" {="" printf("%d="" ",vector_entrada[h]);="" }="" printf("arreglo\n");="" }="" int="" cambiar_pos(int="" *n1,="" int="" *n2)="" {="" int="" temp,temp2;="" temp="*n1;" *n1="*n2;" *n2="temp;" }="" int="" ordena_arreglo(int="" l,int="" v_of,int="" c_pos,="" int="" a,="" int="" b,int="" v_e[])="" {="" int="" i,j;="" printf("ordena="" arreglo="" \n");="" printf("b="" %d="" a="" %d="" \n",b,a);="" i="a;" do="" {="" j="b;" while="" (j=""&gt;i)
	 	{
		    if (v_e[j-1]&gt;v_e[j])
			 {
			  cambiar_pos(&amp;v_e[j-1],&amp;v_e[j]);
			} 	 
			j=j-1; 	  
    	}
    	printArray(v_e,b);
    	printf("\n");
    	i++;
    }while (i&lt;b); c_pos="c_pos+1;" a="a+v_of;" b="(c_pos" *="" v_of)-1;="" if="" (b="" &lt;="l)" {="" ordena_arreglo(l,v_of,c_pos,a,b,v_e);="" }="" }="" int="" dividvence(int="" v_e[],="" int="" max_arr,int="" s_dv[],int="" apta_stk,int="" colum_pos,int="" ini_arv)="" {="" *="" *****revisar="" la="" recurrencia******="" *="" int="" b,a;="" int="" fin_arv;="" int="" valor_offset,wt;="" while="" (apta_stk=""&gt;0)
    {
    valor_offset=s_dv[apta_stk-1];
    fin_arv=(colum_pos * valor_offset)-1;
    printf("v_of %d fin_arv %d ini_arv %d apuntador %d\n",valor_offset,fin_arv,ini_arv,apta_stk);
    printf("Divide y Venseras proceso  \n");
   /* scanf("%d",wt);*/
    Ordena_arreglo(max_arr,valor_offset,colum_pos,ini_arv,fin_arv,v_e);
    
    apta_stk = apta_stk-1;
    }
}

int clear_arr(int v_e[], int max)
{
	int j;
	
	for (j=0;j&lt;max;j++) {="" v_e[j]="0;" }="" }="" int="" main()="" {="" int="" v_e[8];="" int="" s_dv[4];="" int="" m="sizeof(s_dv)/sizeof(s_dv[0]);" int="" n="sizeof(v_e)/sizeof(v_e[0]);" int="" div_arr,i,inx,h;="" i="0;" div_arr="n;" while="" (div_arr=""&gt;=2)
	{
		s_dv[i]= div_arr;
      	div_arr=div_arr/2;
		i++;
		inx=i;	
	}
    clear_arr(v_e,n);
    printf("Vector Limpio \n");
    printArray(v_e,n);
    
	printf("Stack = %d \n",inx);
	printArray(s_dv,inx);
 
 printf("h %d inx %d\n",h,inx);
 
    for (h=0;h

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int maximo;
int i;
int j;
int auxiliar;
int comparaciones;
int movimientos;

int numeroAleatorio(int min, int max) {
    return (min + (rand() % (max + 1 - min)));
}

void merge(int *a, int inicio, int fin) {
    if (inicio >= fin) {
        comparaciones++;
        return;
    }
    int medio;
    int i;
    int j;
    int k;

    medio = (inicio + fin)/2;
    i = inicio;
    j = medio + 1;
    k = 0;

    merge(a, inicio, medio);
    merge(a, medio + 1, fin);
    int copia[fin];

    //hace merge de las dos mitades del vector
    while ((i <= medio) && (j <= fin)) {
        comparaciones++;
        if (a[i] < a[j]) {
            copia[k] = a[i];
            i++;
            k++;
            movimientos++;
        } else {
            copia[k] = a[j];
            j++;
            k++;
            movimientos++;
        }
    }

    //dependiendo de cual mitad acabo primero, termina la otra
    if (i > medio) {
        while (j <= fin){
            copia[k] = a[j];
            j++;
            k++;
            movimientos++;
        }
    }
    if (j > fin) {
        while (i <= medio){
            copia[k] = a[i];
            i++;
            k++;
            movimientos++;
        }
    }

    // finalmente se carga copia en el vector original
    for (i = inicio; i <= fin; i++) {
        a[i] = copia[i - inicio];
    }

}


int main() {
    printf("Por favor digite el tamaño del vector\n");
    scanf("%d",&maximo);

    int vector[maximo];
    srand(time(NULL));
    for (i = 0; i < maximo; i++) {
        vector[i] =numeroAleatorio(1, 500);
    }

    comparaciones = 0;
    movimientos = 0;

    merge(vector, 0, maximo - 1);

    for (i = 0; i < maximo; i++) {
        printf("posicion: %3d  valor: %3d\n", i, vector[i]);
    }

    printf("Para un vector de %5d posiciones se efectuaron %8d comparaciones y %8d movimientos\n", maximo, comparaciones, movimientos);
    return 0;
}

#include <stdio.h>

int x;

int printArray(int arraySize, int *array, int sorted)
{
    printf("\n");
    if (sorted)
        printf("Sorted array: \n");
    else
        printf("Unsorted array: \n");

    for (x=0; x < arraySize; x++)
    {
        printf("%d ", array[x]);
    }

    return 0;
}

int * MergeSort(int *arrayArg, int arraySize)
{
    int array[arraySize];
    
    for (x = 0; x < arraySize; x++)
    {
        array[x] = *(arrayArg + x);
    }

    printf("");
    if (arraySize > 1)
    {
        int leftMiddleSize = arraySize / 2;
        int rightMiddleSize = arraySize - leftMiddleSize;

        int leftMiddleArray[leftMiddleSize];
        int rightMiddleArray[rightMiddleSize];
        int i;
        int counter = 0;

        for (i=0; i < leftMiddleSize; i++)
        {
            leftMiddleArray[i] = array[i];
        }
        
        for (i=0; i < rightMiddleSize; i++)
        {
            counter = i + leftMiddleSize;
            rightMiddleArray[i] = array[counter];
        }
        
        int *tempArray;

        tempArray = MergeSort(leftMiddleArray, leftMiddleSize);

        for (i=0; i < leftMiddleSize; i++)
        {
            leftMiddleArray[i] = *(tempArray + i);
        }

        tempArray = MergeSort(rightMiddleArray, rightMiddleSize);

        for (i=0; i < rightMiddleSize; i++)
        {
            rightMiddleArray[i] = *(tempArray + i);
        }

        int leftIndex = 0;
        int rightIndex = 0;

        // Merge array
        for (i = 0; i < arraySize; i++)
        {
            if (leftIndex >= leftMiddleSize)
            {
                array[i] = rightMiddleArray[rightIndex];
                rightIndex++;
            }
            else if (rightIndex >= rightMiddleSize)
            {
                array[i] = leftMiddleArray[leftIndex];
                leftIndex++;
            }
            else if (leftMiddleArray[leftIndex] < rightMiddleArray[rightIndex])
            {
                array[i] = leftMiddleArray[leftIndex];
                leftIndex++;
            }
            else
            {
                array[i] = rightMiddleArray[rightIndex];
                rightIndex++;
            }
       }
        
        arrayArg = &array[0];

    }

    return arrayArg;
}

int main(void)
{
    printf("WELCOME TO MERGE SORT\n");
    
    int arraySize;
    printf("Set the numbers amount you want to sort:\n");
    scanf("%d", &arraySize);
       
    int array[arraySize];

    int numberInserted;
    for (x=0; x < arraySize; x++)
    {
        printf("insert the %d number: ", x + 1);
        scanf("%d", &numberInserted);

        array[x] = numberInserted;

        printf("\n");
    }

    printArray(arraySize, array, 0);

    printf("\nOrdering array...\n");
    
    int *orderedArray;
    orderedArray = MergeSort(array, arraySize);

    for (x = 0; x < arraySize; x++)
    {
        array[x] = *(orderedArray + x);
    }

    printArray(arraySize, array, 1);

    return 0;
}

Divide y Vencerás

Introducción al Lenguaje C

¿Dónde aprender C?

Introducción al Lenguaje C

Estructura general de un programa en C y un hola mundo

Tipos de errores y datos en C

Variables en C

Operadores y expresiones en C

Ejemplo de operadores en C y reto

Entrada y salida de datos

Estructura secuencial

Estructura secuencial (if y if else)

Estructura selectiva (if, if else, else)

Estructura selectiva (switch)

Estructuras selectivas anidadas

Más Estructuras Selectivas Anidadas

Estructuras Repetitivas: While

Estructuras repetitivas: Do While

Estructuras Repetitivas: For

Platzi Terminal: Llevando a la Práctica lo Aprendido

Crear una tienda de Platzi dentro de la terminal

Crear una tienda de Platzi dentro de la terminal 2

Introducción a Algoritmos

El mundo de los algoritmos

Introducción al Curso de Algoritmos con C

¿Qué es un algoritmo?

Lenguajes de programación

Elementos de un algoritmo

User defined data types: Estructuras de datos y custom data types

Entrada y salida de información

Metodología para la solución de un algoritmo

Resolución del problema

El porqué del análisis de algoritmos

Cómo comparar algoritmos y ritmo de crecimiento

Estructuras de control y estructuras de control secuenciales

Estructuras de control selectivas

Estructuras de control repetitivas

Algoritmos más Utilizados

Sesiones en vivo del Curso de Algoritmos con C

Algoritmos de Ordenamiento

Algoritmo PID

Divide y Vencerás

Algoritmo de Dijkstra: Introducción a los Grafos

Algoritmos de búsqueda