Quick Sort

El método Quick Sort o intercambio de partición funciona de la siguiente manera. Supongamos que tenemos un arreglo X de N elementos. Elegimos un elemnto a y lo colocamos en una posicíón j tal que todos los elemento en las posiciones de 1 a j-1 son menores que a, y todos los elementos en las posiciones desde j+1 a n son mayores que a. De esta manera el elemento a actúa como pibote. Por ejemplo, supongamos que tenemos el siguiente arreglo:

25 - 57 - 48 - 37 - 12 - 92 - 86 - 33

Tomamos el primer elemento (25) como pibote, y vamos tomando los siguientes elementos haciendonos la siguiente pregunta: ¿Es dicho elemento menor que a (25)? Si lo es lo colocamos a la izquierda, de lo contrario lo colocamos a la derecha (estamos ordenando los números de menor a mayor).

De esta manera el arreglo quedaría como:

[ ( 12 ) - 25 - ( 57 - 48 - 37 - 92 - 86 - 33 ) ]

De esta manera hemos creado dos subarreglos. De los cuales el primero ya esta ordenado, pues posse un solo elemento. Con el segundo subarreglo (de la derecha) procedemos de igula manera que en un pricipio. Elegimos el primer elemnto como pibote, y procedemos a mover a izquierda o derecha sus elementos según sena mayores o menores que el pibote

12 - 25 - [ ( 48 - 37 - 33 ) - 57 - ( 92 - 86 ) ]

Al procesar de nuevo los subarreglos obtendremos:

12 - 25 - [ ( 37 - 33 ) - 48 ] - 57 - [ ( 86 ) - 92 ]

Y por último:

12 - 25 - [ 33 - (37 ) ] - 48 - 57 - 86 - 92

Con lo cual el arreglo queda finalmente ordenado:

12 - 25 - 33 - 37 - 48 - 57 - 86 - 92