Laboratorio 6: Algoritmo de Ordenación Mergesort

publicado a la‎(s)‎ 13 jun 2012, 17:29 por Hernan Nina Hanco   [ actualizado el 14 jun 2012, 12:48 ]
I) OBJETIVOS
  • Implementar el algoritmo de ordenación Mergesort.

II) MARCO CONCEPTUAL
Mergesort
El algoritmo mergesort consta de tres pasos:
  1. Si el número de elementos a ordenar es 0 ó 1, acabar.
  2. Ordenar recursivamente las dos mitades del arreglo
  3. Mesclar las dos mitades ordenadas en un vector ordenado
 
III) PRÁCTICAS DE LABORATORIO

Implementar el mergesort

/* * Ordenamiento por mergesort. */ static void mergeSort(ref int[] a, ref int[] r, int izq, int der) { if (izq < der) { int centro = (izq + der) / 2; mergeSort(ref a,ref r,izq,centro); mergeSort(ref a, ref r, centro+1, der); mezclar(ref a,ref r,izq,centro+1,der); } } static void mergeSort(ref int[] a) { int[] r = new int[a.Length]; mergeSort(ref a,ref r,0,a.Length-1); } static void mezclar(ref int[] a, ref int[] r, int posIzq, int posDer, int posFin) { int finIzq = posDer - 1; int posAux = posIzq; int numElementos = posFin - posIzq + 1; // Bucle principal while (posIzq<=finIzq && posDer <=posFin) if (a[posIzq] < a[posDer]) r[posAux++] = a[posIzq++]; else r[posAux++] = a[posDer++]; // Copiar el resto de la primera mitad while (posIzq <= finIzq) r[posAux++] = a[posIzq++]; // copiar resto de la segunda mitad while (posDer <= posFin) r[posAux++] = a[posDer++]; // copiar el arreglo temporal al original for (int i = 0; i < numElementos; i++, posFin--) a[posFin] = r[posFin]; }

IV) TAREA:
  1. Evaluación del tiempo de ejecución del mergesort.
  2. Implementar el algoritmo de ordenación de heapsort, y el análisis de complejidad basado en tiempo de ejecución.

V) REFERENCIAS BIBLIOGRÁFICAS
  • Estructura de datos y algoritmos, Alfred V. Aho, John E. Hopcroft, Jefrey D. Ullman.
Comments