QuickSort

Este método fue desarrollado por Sir Charles Antony Richard Hoare. Usa comparaciones y no es estable.

Datos de QuickSort

No es estable
Usa comparaciones
Peor caso: n2
Promedio: n log(n)

Resumen del Algoritmo

Para implementarlo es necesario hacer lo siguiente:

  1. Si hay que ordenar cero datos entonces ya están ordenados y no hay que hacer nada.
  2. Elegir un pivote
  3. Reordenar todos los elementos de modo que los que son menores que el pivote estén antes del pivote y los mayores estén después. Esta operación se conoce como partición. El pivote después de esto quedará en su posición definitiva.
  4. Aplicar QuickSort a la partición de los menores y a la partición de los mayores (por separado).

Ordenar elementos repetidos

Los elementos que tienen el mismo valor que el pivote se pueden colocar en cualquiera de los dos grupos, pero no es necesario usar el mismo grupo siempre. Si un elemento es menor al pivote entonces se coloca en el grupo de los menores, si es mayor al pivote se coloca en el grupo de los mayores.

El Pivote

El pivote es el elemento que se elije para separar los datos a ordenar en dos grupos: el grupo de menores y el grupo de mayores.
La selección del pivote puede ayudar a acelerar el algoritmo, pero si es muy complicado obtener este pivote el ordenamiento se podría ralentizar.
Formas comunes de elegir este pivote son:

  1. Elegir el primer elemento de la lista. Esto es muy sencillo de hacer, en Logo se puede usar “item 1 :variable“, para arreglos y listas, o “first :variable” para listas.
  2. Elegir un elemento al azar. En Logo, si los datos están en una lista se puede usar la instrucción “pick“, la cual elije un elemento al azar. Pick también puede ser simulado usando “item (random count :var) :var“, si la variable es un arreglo.
  3. Tomar tres elementos, el primero, el último y el del medio. Luego, de esos tres, el del centro se selecciona como pivote.
  4. Igual que la anterior pero tomando más elementos de muestra.
  5. El pivote ideal: Se toma el elemento “del centro” de la lista de datos. Para QuickSort este da los mejores resultados, pero la búsqueda del pivote tomaría la mayor parte del tiempo de cómputo, por lo que no es muy práctico.

Implementación

Es posible implementar este método tanto con listas como con arreglos. Las listas simplifican el proceso de partición, sin embargo, es posible hacer esto directamente sobre el array (sin duplicar datos).

A continuacioń se muestra una implementación que utiliza listas.

Leave a Reply