Método de ordenamiento: “Quicksort”

Instituto Politécnico Nacional

Unidad Profesional Interdisciplinaria en Ingenierías y Tecnologías Avanzadas[pic 1][pic 2]

“UPIITA”

Ingeniería Telemática

                        [pic 3]

Estructura de datos

Método de ordenamiento:

“Quicksort”

Profesor: 

Galván Rodriguez Julio Esteban

Integrantes

• Guzmán Hernández Julio Cesar 
• López López Arturo
• Rodríguez Venegas Thomas Francisco

Grupo: 1TV5

¿Qué es?

Quicksort (en inglés, ordenamiento rápido). Es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a [pic 4]

El método Quicksort fue ideado por el científico ingle Anthony Hoare en 1960. Hoare se hallaba en Rusia trabajando en un proyecto de traducción en computadora (de ruso a ingles). El primer uso del método fue para ordenar las palabras en ruso y facilitar la traducción. Posteriormente se desarrolló para la informática. El método de Quicksort fue una mejora del método de intercambio Directo.

Descripción del algoritmo

El algoritmo trabaja de la siguiente forma:

• Elegir un elemento del arreglo de elementos a ordenar, al que llamaremos pivote.

• Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

• La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Demostración del método Quicksort

• Suponemos que el número de elementos a ordenar es potencia de dos, es decir, n = 2k.
• Podemos ver que k = log2(n), donde k es el número de divisiones que realizará el algoritmo.
• En la primera fase del algoritmo habrán n comparaciones, en la segunda fase el algoritmo creará dos sublistas aproximadamente de tamaño n/2. El número total de comparaciones de estas dos sublistas es: 2(n/2) = n.
• En la tercera fase el algoritmo procesará 4 sublistas más, por tanto el número total de comparaciones en esta fase es 4(n/4) = n.

¿Qué tan eficiente es el método Quicksort?

• Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
• En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es  O*(n·log n).
• En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.
• En el caso promedio, el orden es O(n·log n).

No es extraño, pues, que la mayoría de las optimizaciones que se aplican al algoritmo se centren en la elección del pivote.

Ejemplo

[pic 5]

Como se mencionó en la descripción del algoritmo, se necesita de un elemento del arreglo al que llamaremos ‘pivote’, en este ejemplo se tomara al número 62 por comodidad, ya que es el número más próximo a la media.

1. Una vez elegido este elemento, nos posicionamos en el lado izquierdo del arreglo en el numero 78 y en el lado derecho en el numero 22, del lado izquierdo del elemento deben de estar todos los numero menores a el y del lado izquierdo los mayores.
2. Empezamos a comparar por el lado izquierdo, tomamos el número 78 y lo comparamos con el pivote que es 62, 78 es mayor a 62 por lo que no cumple con nuestra condición de ser menor, así que pasamos al lado derecho.
3. Ahora compararemos el numero 22 con el pivote 62, este numero es menor a el pivote por lo que tampoco cumple con la condición propuesta, por lo que ahora debemos de hacer un cambio, el numero 78 del lado izquierdo lo cambiamos con el 22 del derecho, para que se pueda cumplir la condición.
4. Una vez hecho esto, podemos seguir, ahora regresamos al lado izquierdo recorriéndonos una posición, en este caso es el numero 21, este es menor al pivote por lo que se mantiene en su posición y pasamos al siguiente elemento del arreglo.
5. A partir de aquí el proceso se repite, si el elemento seleccionado cumple con la condición propuesta (menores en el lado izquierdo y mayores en el derecho), este mantendrá su posición, caso contrario se hará un cambio de posición al lugar que le corresponda.
6. Al ordenar los elementos con el pivote seleccionado (62), se obtendrá lo siguiente:

22,21,14,15   62  87,74,85,76,97,84,78

...