PASCAL CON FREE PASCAL

Este algoritmo es quizás el más eficiente y en el que en la mayoría de los casos da mejores resultados. Fue desarrollada por Charles Antony Richard Hoare en 1960. Este algoritmo se basa en la recursividad y consiste en lo siguiente:

"Se elige un elemento de la lista a ordenar, al que se le llamará pivote, luego se colocan los elementos de la lista mayores que el pivote a la derecha y los menores a la izquierda, o viceversa si se quiere una lista en orden descendente. De esa manera el pivote quedará en el lugar que le corresponde en la lista. La lista queda separada en dos, se repite el proceso recursivamente para ordenar cada parte hasta que no queden más partes a ordenar".

Lo más importante del algoritmo es elegir bien el pivote, en la mayoría de los casos se elige el pivote que se encuentra en la mitad de la lista.

Para colocar los elementos a la derecha o izquierda del pivote, se procede del siguiente modo se recorre la lista por la izquierda hasta encontrar uno mayor al pivote (menor para un ordenamiento descendente) luego se recorre la lista por la derecha hasta encontrar uno menor al pivote (mayor para un ordenamiento descendente), se intercambian estos elementos, y así sucesivamente hasta que los recorridos se crucen. El lugar en donde se cruzan los recorridos es el lugar en donde se separa la lista en dos partes.

Veremos un ejemplo ordenando de menor a mayor (ascendentemente) la siguiente lista de números:

8, 7, 15, 17, 11, 5, 9, 12, 20, 3

El pivote es el elemento medio de la lista, que en este caso será el 11 que se encuentra en la posición 4, la posición se obtiene al dividir la posición del primer elemento con el último: (0+9) div 2. Se hacen los recorridos por la derecha y por la izquierda hasta encontrar, por la derecha uno mayor y por la izquierda uno menor al pivote.

Una vez que se subdivide la lista en estas dos partes, debemos hacer lo mismo con ambas partes, continuaremos con la parte derecha: 17, 12, 20, 15.

El pivote es el elemento medio de esta parte, que en este caso será el 12, para hallar la posición de este elemento se suman las posiciones del 17 y el 15, y se hace una division entera entre 2.

Se continua con la nueva parte derecha: 17, 20, 15.

Se continua con la ultima nueva parte derecha: 20 - 17.

Para la parte izquierda: 8, 7, 3, 9, 5; se procede del mismo modo, obteniendose de esta manera la lista ordenada. El procedimiento sería el siguiente:

procedure OrdenarA(var A: LNaturales; Izq,Der: int64) ;
 var
   auxIzq,auxDer: int64;   
   Pivote,aux:qword;
Begin 
   auxIzq:=Izq;
   auxDer:=Der;

   Pivote := A[(auxIzq + auxDer) div 2];  
   
   Repeat
     while A[auxIzq] < Pivote do Inc(auxIzq); //recorrido por la izquierda
     while A[auxDer] > Pivote do Dec(auxDer); //recorrido por la derecha
     if auxIzq <= auxDer then
     begin
       //intercambio
       aux := A[auxIzq];
       A[auxIzq] := A[auxDer];
       A[auxDer] := aux;
       
       Inc(auxIzq);
       Dec(auxDer);
     end;
   until auxIzq > auxDer;
   
   if auxDer > Izq then OrdenarA(A,Izq,auxDer);
   if auxIzq < Der then OrdenarA(A,auxIzq,Der); 
End;

Lo primero que hace el procedimiento es obtener el Pivote con la siguiente instrucción:

Pivote := A [(auxIzq + auxDer) div 2 ];

El bucle Repeat es el que controla la búsqueda de los elementos a intercambiar, el recorrido por la izquierda de la lista se hace con la ayuda de la variable auxIzq y el recorrido por la derecha con la variable auxDer, que siempre serán los extremos de cada parte a ordenar que se obtienen de los parámetros Izq y Der. El bucle Repeat finaliza cuando auxIzq se hace mayor que auxDer, de esa manera se determina el cruce de los recorridos.

Terminado el bucle repeat se comprueba si hay elementos a intercambiar por la izquierda o por la derecha, si los hay se vuelve a llamar al procedimiento recursivamente. Para comprobar si hay elementos a ordenar por la izquierda se comprueba si auxDer es mayor que el parámetro Izq, y para saber si hay elementos a ordenar por la derecha se comprueba si auxIzq es menor que el parámetro Der. La recursión del procedimiento finaliza cuando ya no haya más elementos a intercambiar.

El algoritmo ordena la lista de menor a mayor (ascendente), en caso quisiéramos hacerlo de mayor a menor (Descendente), sólo basta con cambiar las condiciones de los recorridos. Para un ordenamiento ascendente se debe usar:

while A [auxIzq ] < Pivote do Inc(auxIzq); //recorrido por la izquierda

while A [auxDer ] > Pivote do Dec(auxDer); //recorrido por la derecha

Y para un ordenamiento descendente se debe usar:

while A [auxIzq ] > Pivote do Inc(auxIzq); //recorrido por la izquierda

while A [auxDer ] < Pivote do Dec(auxDer); //recorrido por la derecha

El siguiente archivo comprimido: OrdenacionRapida.zip ,tiene 4 programas de ejemplo para los tipos de datos LNaturales, LEnteros, LReales y LPalabras de la unidad listas.