Administracion

Método de Quicksort

2. Método de ordenamiento Quicksort : (ordenación rápida) recibe el nombre de su autor, Tony Hoare. La idea del algoritmo es simple, se basa en la división en particiones de la lista a ordenar, por lo que se puede considerar que aplica la técnica divide y vencerás. El método es, posiblemente, el más pequeño de código, más rápido, más elegante, más interesante y eficiente delos algoritmos de ordenación conocidos.

Técnica del Método: El método se basa en dividir los n elementos de la lista a ordenar en dos partes o particiones separadas por un elemento: una partición izquierda, un elemento central denominado pivote o
elemento de partición, y una partición derecha. La partición o división se hace de tal forma que todos los elementos de la primera sublista(partición izquierda) son menores que todos los elementos de la segunda sublista (partición derecha). Las dos sublistas se ordenan entonces independientemente.
Para dividir la lista en particiones (sublistas) se elige uno de los elementos de la lista y se utiliza como pivote o elemento de partición. Si se elige una lista cualquiera con los elementos en orden aleatorio, se puede seleccionar cualquierelemento de la lista como pivote, por ejemplo, el primer elemento de la lista. Si la lista tiene algún orden parcial conocido, se puede tomar otra decisión para el pivote. Idealmente, el pivote se debe elegir de modo que se divida la lista exactamente por la mitad, de acuerdo al tamaño relativo de las claves.

Ejemplo:

1. Lista original           5 2 1 7 9 3 8 7
pivote elegido 5
sublistaizquierda1 (elementos menores que 5)   2 1 3
sublista derecha1 (elementos mayores o iguales a 5)   9 8 7

2. El algoritmo se aplica a la sublista izquierda
Sublista Izda  2 1 3
sublista Izda 1
pivote  2                                  
sublista Dcha 3

Sublista Izda
 Izda  pivote  Dcha
    1      2        3
3. El algoritmo se aplica a la sublista derecha
Sublista Dcha   9 8 7
sublista Izda7
pivote 8
sublista Dcha 9

Sublista Dcha
Izda        pivote       Dcha
   7            8              9

4. Lista ordenada final
Sublista izquierda        pivote             Sublista derecha
       1 2 3                      5                         7 8 9

Codificación del Método Quicksort
void quicksort(double a[], int primero, int ultimo)
{
int i, j, central;
double pivote;central = (primero + ultimo)/2;
pivote = a[central];
i = primero;
j = ultimo;
do {
while (a[i] < pivote) i++;
while (a[j] > pivote) j--;
if (i<=j)
{
double tmp;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
}while (i <= j);
if (primero < j)
quicksort(a, primero, j);
if (i < ultimo)
quicksort(a, i, ultimo);
}

Clasificación por partición (quicksort) |Volver arriba |
Explicación:
Este método fue desarrollado por C.A.R. Hoare en el año 1960 y es el método más rápido que se conoce hasta la fecha. Es un método de clasificación avanzada.
Se basa en que cuanto mayor sea la distancia entre los elementos que se intercambian más eficaz será la clasificación. Para ello se elige un pivote. Está demostrado que la eficacia del algoritmo es mayor si estallave es el elemento central, aunque lo ideal sería que el pivote fuera la mediana, pero claro, para saberla sería necesario ordenar antes el vector.
 
Se trata de buscar un elemento mayor que el pivote en la parte izquierda, y otro menor que el pivote en la parte derecha e intercambiarlos. S i en la parte izquierda o derecha no se encuentran valores superiores o inferiores al pivoterespectivamente lo que se intercambia es el pivote. Este proceso se repite hasta que se cruzan el índice de incremento y el de decremento, en este momento nos queda dividido el vector en 2 partes, la parte izquierda con los elementos menores que el pivote y la parte derecha con los mayores que el pivote. A cada una de estas partes se le llama partición. Esta operación se repite con cada partición hasta que...