Algoritmo Quicksort

MÉTODO QUICKSORT

Video demostrativo:

 Tipos de Algoritmos

Para poder ordenar una cantidad determinada de números almacenados en un vector o matriz, existen distintos métodos (algoritmos) con distintas características y complejidad.

Existe desde el método más simple, como el Bubblesort (o Método Burbúja), que son simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo.

Algoritmos basados en métodos Iterativos:

Estos métodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado.

Dentro de los Algoritmos iterativos encontramos:

•  Burbuja
•  Inserción
•  Selección
•  Shellsort

Algoritmos basados en métodos Recursivos:

Estos métodos son aún más complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica “Divide y Vencerás”, que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos.

Mediante llamadas recursivas a sí mismos, es posible que el tiempo de ejecución y de ordenación sea más óptimo.

Dentro de los algoritmos recursivos encontramos:

• Ordenamiento por Mezclas (merge)
• Ordenamiento Rápido (quick)

Método Quicksort

El método Quicksort basa su estrategia en la idea intuitiva de que es más fácil ordenar una gran estructura de datos subdividiéndolas en otras más pequeñas introduciendo un orden relativo entre ellas. En otras palabras, si dividimos el arreglo a ordenar en dos subarreglos de forma que los elementos del subarreglo inferior sean más pequeños que los del subarreglo superior, y aplicamos el método reiteradamente, al final tendremos el arreglo inicial totalmente ordenado. Existen además otros métodos conocidos, el de ordenación por montículo y el de shell.

El algoritmo Quicksort fue desarrollado en 1962 por C.A.R. Hoare, antes de que se implementaran los primeros lenguajes con capacidad para ejecutar funciones recursivas.

El ordenamiento por partición (Quick Sort) se puede definir en una forma más conveniente como un procedimiento recursivo.

Tiene aparentemente la propiedad de trabajar mejor para elementos de entrada desordenados completamente, que para elementos semiordenados. Esta situación es precisamente la opuesta al ordenamiento de burbuja.

Este tipo de algoritmos se basa en la técnica «divide y vencerás», o sea es más rápido y fácil ordenar dos arreglos o listas de datos pequeños, que un arreglo o lista grande.

Normalmente al inicio de la ordenación se escoge un elemento aproximadamente en la mitad del arreglo, así al empezar a ordenar, se debe llegar a que el arreglo este ordenado respecto al punto de división o la mitad del arreglo.

Se podrá garantizar que los elementos a la izquierda de la mitad son los menores y los elementos a la derecha son los mayores.

Los siguientes pasos son llamados recursivos con el propósito de efectuar la ordenación por partición al arreglo izquierdo y al arreglo derecho, que se obtienen de la primera fase. El tamaño de esos arreglos en promedio se reduce a la mitad.

Así se continúa hasta que el tamaño de los arreglos a ordenar es 1, es decir, todos los elementos  ya están ordenados.

En promedio para todos los elementos de entrada de tamaño n, el método hace O(n log n) comparaciones, el cual es relativamente eficiente.

Descripción del Algoritmo:

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

La idea central de este algoritmo consiste en lo siguiente:

•  Se toma un elemento x de una posición cualquiera del arreglo.
• Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.
•   Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.
•   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. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
•   Repetir este proceso de forma recursiva para cada sub-lista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
•   Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

Análisis del algoritmo:

Estabilidad: No es estable.

Requerimientos de Memoria: No requiere memoria adicional en su forma recursiva. En su forma iterativa la necesita para la pila.

•Ventajas:

Muy rápido.

No requiere memoria adicional.

•Desventajas:

Implementación un poco más complicada.

Recursividad (utiliza muchos recursos).

Mucha diferencia entre el peor y el mejor caso.

Complejidad computacional del Quicksort:

En el mejor de los casos tiene un costo de O(n*log (n)). Que es cuando el pibote siempre queda al medio del arreglo.

En el peor de los casos tiene un costo de O(n^2). Cuando el pivote siempre se inclina hacia a un lado, es decir, genera un arreglo de sólo un elemento y una segunda con el resto de elementos.

En el caso promedio también tiene un costo de O(n*log (n)). Se produce cuando el pibote se inclina más hacia un lado y los 2 subarreglos tienen distinto tamaño de elementos.

Eligiendo el Pivote

Elegir el primero o el último de la lista nunca es una buena idea ya que los elementos de la lista no están uniformemente distribuidos. Por otro lado, si contamos con un buen generador de números aleatorios, podemos elegir un pivote al azar de entre todos los elementos de la lista. Esta estrategia es segura puesto que es improbable que un pivote al azar dé como resultado una partición mala, pero tiene como contrapartida que en algunas ocasiones si puede arrojar un resultado de O(n2), además, la elección de números aleatorios puede incrementar el tiempo de ejecución del algoritmo.

Una buena estrategia para solucionar la selección del pivote ampliamente extendida es la conocida como “a tres bandas”. En esta estrategia lo que se persigue es hacer una media con los valores de tres de los elementos de la lista. Por ejemplo si nuestra lista es [ 8, 4, 9, 3, 5, 7, 1, 6, 2 ] la media sería ( 8 + 2 + 5 ) / 3 = 5 lo que daría lugar a las siguientes particiones:

L1 = [ 8, 9, 7, 6 ]

L2 = [ 5 ]

L3 = [ 1, 2, 4, 3 ]

Esta estrategia no nos asegura que siempre nos dará la mejor selección del pivote, sino que estadísticamente, la elección del pivote sea buena.

Video demostrativo: