Algoritmo del método de ordenamiento QuickSort

Algoritmo del método de ordenamiento QuickSort

“Divide y vencerás”

Ejemplo:

1. Selecciona un valor del arreglo como pivote es decir un numero por el cual todos los elementos van a ser comparados.
2. Se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.
3.  Luego se organizan los sub-arreglos que quedaron a mano derecha e izquierda.

Tenemos un arreglo que está definido con los valores {22, 40, 4,1 0, 12, 35} los pasos en quicksort para arreglarlo son los siguientes:

1.  Se toma como pivote el numero 22 recuerden puede ser cualquier número.
2.  La búsqueda de izquierda a derecha encuentra el valor 40 que es mayor a pivote y la búsqueda de derecha a izquierda encuentra el valor 35 no lo toma porque es mayor a el numero pivote (recuerden que la búsqueda de derecha a izquierda busca los menores) entonces continua y encuentra a 12 que es menor que el pivote y se intercambian el resultado sería {21,12,4,10,40,35}
3.  Si seguimos la búsqueda la primera encuentra el valor 40, y la segunda el valor 10, pero ya se han cruzado, así que paramos. Para terminar la división, se coloca el pivote en su lugar el numero encontrado por la segunda búsqueda, el 10 quedando: {10,12,4,22,40,35}
4. Ahora tenemos dividido el arreglo en dos arreglos más pequeños que son {10, 12, 4} y el {40,35}, y en ellos se repetirá el mismo proceso.

Representación Grafica QuickSort

De forma gráfica el proceso sería el siguiente:

La elección del pivote determinará la eficiencia de este algoritmo ya que determina la partición del array. Si consideramos que el array está desordenado, podemos elegir el primer elemento y el algoritmo funcionaría de forma eficiente. Pero si el array está casi ordenado, elegir el primer elemento como pivote sería una mala solución ya que obtendríamos un subarray muy pequeño y otro muy grande. Por la misma razón, elegir el último elemento del array como pivote también es una mala idea. Pretendemos conseguir que el tamaño de los subarrays sea lo más parecido posible.

Una alternativa a elegir el primer elemento es elegir como pivote un elemento al azar de entre todos los del array.

Otra estrategia es calcular la mediana de los valores de la izquierda, centro y derecha del vector.

Por ejemplo para el vector: 9 8 1 6 10 2 3, se calcula la mediana de los elementos que ocupan el primer lugar, el último y el centro o sea 9 3 6. La mediana es 6 que determinaría las particiones {1 3 2} {6} {8 10 9}.

Método de Ordenamiento QuickSort

Funcionamiento del método de Ordenamiento QuickSort

Para saber como funciona el método de QuickSort crearemos un proyecto de netbeans.

1. Declaramos un arreglo con valores desordenados como se aprecia en la linea 8 del código.

2. Mediante el uso de un ciclo =FOR= mostramos los valores del arreglo desordenado comparando que  la variable de inicio "i" sea menor a los elementos del arreglo declarado (linea 12).

Datos Personales

Quezada Peralta María Griselda 4° B   TIC

Criterios de Evaluación

Quezada Peralta María Griselda 4° B TIC
CRITERIO	EVALUACIÓN
Proyecto(s)	30%
Examen	30%
Tareas/Ejercicios	30%
Participación	10%