Laboratorio 5: Algoritmos de ordenación rápida Quicksort

publicado a la‎(s)‎ 6 jun. 2012 18:04 por Hernan Nina Hanco   [ actualizado el 12 jun. 2012 12:47 ]
I) OBJETIVOS
  • Implementar el algoritmo de ordenación mas rápido Quicksort.

II) MARCO CONCEPTUAL


8.3. Clasificación rápida (QuickSort)

El primer algoritmo de O(n log n), que se estudia, y tal vez el más eficiente para clasificación interna. La esencia del método consiste en clasificar un arreglo A[1], …,A[N] tomando en el arreglo un valor clave v como elemento pivote, alrededor del cual reorganizar los elementos del arreglo. Es de esperar que el pivote esté cercano al valor medio de la clave del arreglo, de forma que esté precedido por una mitad de las claves y seguido por la otra mitad. Se permutan los elementos del arreglo con el fin de que para algún j, todos los registros con claves menores que v aparezcan en A[1], …,A[j], y todos aquellos con claves v o mayores aparezcan en A[j+1],…,A[N]. Después, se aplica recursivamente la clasificación rápida a A[1], …,A[j] y a A[j+1], …,A[N] para clasificar ambos grupos de elementos. Dado que todas las claves del primer grupo preceden a todas las claves del segundo grupo, todo el arreglo quedará ordenado.


III) PRÁCTICAS DE LABORATORIO

1) Implementar el algoritmo de búsqueda Quicksort

static void AlgoritmoQuickSort(ref int[] arreglo, int i, int j) { int pivote; // el valor del pivote int indice_pivote; // el indice de un elemento de A donde su clave es el pivote int k; // indice al inicio del grupo de elementos >= pivote indice_pivote = encuentra_pivote(arreglo, i, j); Console.WriteLine(indice_pivote); if (indice_pivote != -1) // no hacer nada si todas las claves son iguales { pivote = arreglo[indice_pivote]; k = particion(ref arreglo, i, j,pivote); AlgoritmoQuickSort(ref arreglo, i, k - 1); AlgoritmoQuickSort(ref arreglo, k, j); } } static int encuentra_pivote(int[] arreglo, int i, int j) { int primera_clave; // Valor de la primera clave encontrada int k; // va de izquierda a derecha buscando una clave diferente primera_clave = arreglo[i]; for (k = i + 1; k <= j;k++) // rastrea en busca de una clave distinta if (arreglo[k] > primera_clave) // Selecciona la clave mayor { return k; } else if (arreglo[k] < primera_clave) return i; return -1; // nunca se encuentra dos claves diferentes } static int particion(ref int[] arreglo, int i, int j, int pivote) { int z, d; // cursores z = i; d = j; do { intercambiar(ref arreglo[z],ref arreglo[d]); // ahora se inicia la fase de rastreo while (arreglo[z]<pivote) z++; while (arreglo[d]>=pivote) d--; } while (z<d); return z; }


IV) TAREA:

  1. Evaluación del tiempo de ejecución en el peor, medio y peor caso del algoritmo.
  2. Modificar el algoritmo de la practica para acelerar QuickSoft seleccionando de mejor manera el pivote (elección del pivote en la base a la mediana).
  3. Modificar el algoritmo de la practica para acelerar QuickSoft permitiendo arreglos pequeños y llamando a algoritmos mas simples de ordenación.

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