* Dentro de los métodos Indirectos

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 de los 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 cualquier elemento 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
sublista izquierda1 (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 Izda 7
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);

}

Prueba de Escritorio: