mergesort como ejemplo de divide y vencerás
DESCRIPTION
Mergesort como ejemplo de Divide y Vencerás. Ampliación de Informática Abril, 2002. /* PRACTICA 5. 18 DE ABRIL DE 2002. ALGORITMO MERGESORT COMO EJEMPLO DIVIDE Y VENCERAS SE USA FUNCION rand PARA GENERAR NUMEROS ALEATORIOS MERGESORT REALIZA LLAMADAS RECURSIVAS A SI MISMA PARA DIVIDIR - PowerPoint PPT PresentationTRANSCRIPT
Mergesort como ejemplo Mergesort como ejemplo de Divide y Vencerásde Divide y Vencerás
Ampliación de InformáticaAmpliación de InformáticaAbril, 2002Abril, 2002
Práctica 5. Mergesort como ejemplo de Divide y Vencerás
2
/* PRACTICA 5.18 DE ABRIL DE 2002.ALGORITMO MERGESORT COMO EJEMPLO DIVIDE Y VENCERASSE USA FUNCION rand PARA GENERAR NUMEROS ALEATORIOSMERGESORT REALIZA LLAMADAS RECURSIVAS A SI MISMA PARA DIVIDIREL VECTOR EN SUBVECTORES Y ORDENARLOS.DESPUES UTILIZA EL ALGORITMO FUSIONAR PARA MEZCLAR LAS DOSSUBMITADES ORDENADAS.EL ALGORITMO ESCRIBE_VECTOR MUESTRA EL CONTENIDO DE UN TROZODE VECTOR, ENTRE LAS POSICIONES [izda..dcha] */
Práctica 5. Mergesort como ejemplo de Divide y Vencerás
3
#include<stdio.h>#include<stdlib.h>main(){int i, n, v[11];void mergesort();void escribir_vector();
printf ("\nRealizo ordenacion por fusion"); printf ("\nTamaño del vector (máx. 11): "); scanf ("%d", &n); while (n > 0 && n <= 11) {
for (i=0; i < n; i++) v[i] = (1.0 * rand())/(RAND_MAX * 0.1); printf ("\nAntes: "); escribir_vector(v, 0, n-1); mergesort (v, 0, n-1); printf ("\nDespués: "); escribir_vector(v, 0, n-1); printf ("\nNumero de elementos (<=11): "); scanf ("%d", &n); }}
Práctica 5. Mergesort como ejemplo de Divide y Vencerás
4
void mergesort (int *v, int izda, int dcha) {int i, j, k, tmp, *u, *w;void fusionar();void escribir_vector();
/* Si la porcion del vector tiene tamaño 1, ha terminado */ switch (dcha - izda + 1) { case 1: printf ("\n Tamaño 1: %d", v[izda]); break; case 2: if (v[izda] > v[dcha] ) { tmp = v[izda]; v[izda]= v[dcha]; v[dcha] = tmp; };
printf ("\nTamaño 2: %d <= %d", v[izda], v[dcha]); break;
Práctica 5. Mergesort como ejemplo de Divide y Vencerás
5
default: /* Hay más de dos elementos, se crean dos mitades */
/* Reservamos sitio para las dos mitades */u = (int *) calloc ((dcha - izda + 1)/2, sizeof(int));
w = (int *) calloc ((dcha - izda + 1)/2 + 1, sizeof(int)); if (u == NULL || w ==NULL) exit(-1);
printf ("\nSubmitad izquierda [%d,%d]=", izda, (dcha+izda)/2); escribir_vector (v, izda, (izda+dcha)/2); for (i=izda, j=0; i<=(izda+dcha)/2;i++, j++) u[j] = v[i];
printf ("\nSubmitad derecha [%d,%d]=", (dcha+izda)/2 + 1, dcha);
escribir_vector (v, (dcha+izda)/2+1, dcha); for (k=0, i=(dcha+izda)/2+1; i <= dcha; i++) w[k++] = v[i];
Práctica 5. Mergesort como ejemplo de Divide y Vencerás
6
mergesort (u, 0, j-1) ; /* Ordeno por fusión parte izda.*/ mergesort (w, 0, k-1); /* Ordeno por fusión parte dcha.*/
printf ("\nIntenta fusionar: \n"); escribir_vector (u, 0, j-1); escribir_vector (w, 0, k-1);
fusionar (u, w, v, izda, dcha, j-1, k-1); /* Todas las mitades serán contiguas*/
printf ("\nTras fusionar\n"); escribir_vector (v, izda, dcha);
/* Cuando ya están fusionados en v, DEBO liberar las dos mitades creadas */
free( (void *) u); free ((void *) w); } /* switch*/
return; } /* mergesort */
Práctica 5. Mergesort como ejemplo de Divide y Vencerás
7
mergesort (u, 0, j-1) ; /* Ordeno por fusión parte izda.*/ mergesort (w, 0, k-1); /* Ordeno por fusión parte dcha.*/
printf ("\nIntenta fusionar: \n"); escribir_vector (u, 0, j-1); escribir_vector (w, 0, k-1);
fusionar (u, w, v, izda, dcha, j-1, k-1); /* Todas las mitades serán contiguas*/
printf ("\nTras fusionar\n"); escribir_vector (v, izda, dcha);
/* Cuando ya están fusionados en v, DEBO liberar las dos mitades creadas */
free( (void *) u); free ((void *) w); } /* switch*/
return; } /* mergesort */
Práctica 5. Mergesort como ejemplo de Divide y Vencerás
8
void fusionar (int *izdo, int *dcho, int *final, int izda, int dcha, int M, int N) {int i, j, k; /* para recorrer las dos mitades */k = izda; i = 0; j = 0;/* Mientras haya elementos en los dos, tomo el menor o dos si son iguales;ambas mitades ya están ordenadas */while ((i <= M) && (j <= N)) {
if (izdo[i] < dcho[j]) final[k++] = izdo[i++];else{ if (izdo[i] > dcho[j]) final[k++] = dcho[j++];
else { final[k++] = izdo[i++]; final[k++] = dcho[j++]; }}
} /* while *//* Cuando sólo queden elementos en uno, me quedo con todos los que falten, porque ya estarán ordenados */while (i <= M) final[k++] = izdo[i++]; /*sólo queda mitad izda.*/while (j <= N) final[k++] = dcho[j++]; /* sólo queda mitad dcha.*/
} /* fusionar()*/