I) OBJETIVOS
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:
V) REFERENCIAS BIBLIOGRÁFICAS
|