Es uno de los métodos mas rápidos y mas utilizados en la ordenación de arreglos y fue inventado por C. Horre.
La cantidad de código necesario es pequeña con la velocidad que proporciona.
La idea básica de la ordenación de un arreglo consiste:
1.- elegir el elemento pivote
2.- dividir a partir del arreglo original en 2 subarreglos de modo que un subarreglo o sublista están todos los elementos menores del pivote y en la otra sublista todos los elementos mayores del pivote, las sublistas deben ser ordenadas del mismo modo, lo que conduce a un algoritmo recursivo.
La elección del pivote es arbitraria aunque por comodidad es usual utilizar el termino central de la lista original aunque se puede utilizar el primero o el ultimo elemento de la misma, para ello se establecen 2 punteros; por ejemplo: i y j.... I apuntara al 1er elemento y j apuntara al último.
El siguiente paso es comparar si el elemento de i es menor que el pivote, si es menor se deberá ir incrementando i cuantas veces sea necesario, lo mismo sucederá para j, si el elemento es mayor que el pivote se deberá ir decrementando.
En caso de que el elemento de j sea menor que el pivote se hará un intercambio entre i y j y se incrementara a i y se decrementara a j.
En el momento en el que j sea menor que i se ha terminado la partición y se han generado 2 sublistas, en la 1ra sublista todos los elementos menores o igual al pivote y en la 2da todos los elementos mayores que el pivote.
Se repetirá la misma partición hasta que los elementos hayan quedado ordenados. Este método es conocido como: "DIVIDE Y VENCERÁS".
Ejemplo:
No hay comentarios:
Publicar un comentario