BotonMenu
BotonIndice

Visita : http://www.conoce3000.com
Paypal : https://www.paypal.me/conoce3000/1

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL

PASCAL CON FREE PASCAL


8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.4. ORDENAMIENTO RÁPIDO. (QUICK SORT)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.4. ORDENAMIENTO RÁPIDO. (QUICK SORT)
8. ALGORITMOS DE ORDENACIÓN Y BUSQUEDA.
8.4. ORDENAMIENTO RÁPIDO. (QUICK SORT)

SIGUIENTE

SIGUIENTE

SIGUIENTE


‒ Ordenamiento rápido. (Quick sort)

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.


Pivote = 11.
Posición del pivote = (0+9) div 2.

Recorridos
11
8 7 15 17 11 5 9 12 20 3
0 1 2 3 4 5 6 7 8 9
^ ^
En este primer recorrido se intercambia el 15 y el 3.

11
8 7 3 17 11 5 9 12 20 15
0 1 2 3 4 5 6 7 8 9
^ ^
En este segundo recorrido se intercambia el 17 y el 9.

11
8 7 3 9 11 5 17 12 20 15
0 1 2 3 4 5 6 7 8 9
^ ^
En este tercer recorrido se intercambia el 11 y el 5.

11
8 7 3 9 5 11 17 12 20 15
0 1 2 3 4 5 6 7 8 9
^ ^
En este cuarto recorrido, los recorridos se cruzan, y ya no es necesario hacer más intercambios. La lista se subdivide en dos partes:
parte izquierda: 8, 7, 3, 9, 5 y parte derecha: 17, 12, 20, 15.


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.


Pivote = 12.
Posición del pivote = (6+9) div 2.

Recorridos
12
8 7 3 9 5 11 17 12 20 15
0 1 2 3 4 5 6 7 8 9
^ ^
En este cuarto recorrido, los recorridos se cruzan, y ya no es necesario hacer más intercambios. La lista se subdivide en dos partes:
parte izquierda: 8, 7, 3, 9, 5 y parte derecha: 17, 12, 20, 15.

12
8 7 3 9 5 11 12 17 20 15
0 1 2 3 4 5 6 7 8 9
^ ^
En este segundo recorrido, los recorridos se vuelven a cruzar, y no se hacen más intercambios.
Se comprueba si hay nuevas partes a la derecha o izquierda.
Sólo habrá una nueva parte derecha que contendrá los elementos: 17, 20, 15. No habrá una nueva parte izquierda porque el pivote se coloco al inicio de toda la parte derecha de la lista.


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


Pivote = 17.
Posición del pivote = (7+9) div 2.

Recorridos
17
8 7 3 9 5 11 12 17 20 15
0 1 2 3 4 5 6 7 8 9
^ ^
En este primer recorrido se intercambia el 17 con el 15.

17
8 7 3 9 5 11 12 15 20 17
0 1 2 3 4 5 6 7 8 9
^ ^
En este segundo recorrido los recorridos se cruzan.
Se comprueba si hay nuevas partes a la derecha o izquierda.
Sólo hay una nueva parte derecha: 20 y 17


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


Pivote = 20.
Posición del pivote = (8+9) div 2.

Recorridos
20
8 7 3 9 5 11 12 15 20 17
0 1 2 3 4 5 6 7 8 9
^ ^
En este segundo recorrido los recorridos se cruzan.
Se comprueba si hay nuevas partes a la derecha o izquierda.
Sólo hay una nueva parte derecha: 20 y 17

20
8 7 3 9 5 11 12 15 17 20
0 1 2 3 4 5 6 7 8 9
^ ^
En este segundo recorrido los recorridos se cruzan.
Se comprueba si hay nuevas partes a la derecha o izquierda.
Al no haber nuevas partes ya no se hacen intercambios y toda la parte derecha queda ordenada.


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:


Descargar
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;
Código fuente 9: Algortimo Quick sort.
Descargar

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.




SIGUIENTE
SIGUIENTE
SIGUIENTE



 
‒ Comentarios y sugerencias.

Agradezco de antemano, todo comentario, sugerencia, y donativo (a través de Paypal me), que ayude a mejorar los contenidos educativos de Conoce 3000. Además, cualquier pregunta o duda que tengas lo puedes hacer por este medio. Pero, todo contenido que pueda resultar ofensivo, malicioso, racista, sexista, discriminatorio, obsceno, vulgar será eliminado.


Comments System WIDGET PACK






PORTADA |  INTERESANTE |  APUNTES |  LIBROS |  GALERIA


Creative Commons License


Todos los textos, imágenes y videos de Conoce3000 estan colocados bajo una licencia : Creative Commons Reconocimiento-NoComercial 3.0 Unported License.