martes, 26 de mayo de 2009

METODO DE ORDENACION QUICKSORT

METODO DE QUICK SORT*

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: