viernes, 1 de noviembre de 2013

Ordenación rápida quicksort

El algoritmo de ordenación rápida, o quicksort, fue desarrollado por Antony Hoare en 1960, mientras estudiaba en la Universidad de Moscú. Hoare tenía un gran interés en los sistemas automáticos de traducción, y uno de los principales problemas con los que se encontró fue el de cómo ordenar de manera eficiente las palabras a traducir, que podían llegar a ser muchas. De ahí su interés en los alogirtmos de ordenación.
Quicksort es un algoritmo recursivo que se basa en el paradigma divide y vencerás para ordenar los números. Quicksort se compone de los siguientes pasos:
  • Elegir un elemento del vector al azar, al que llamaremos pivote.
  • Reordenar el vector de tal manera que los elementos menores que el pivote se encuentren a su izquierda, y los mayores a su derecha. Nótese que en este momento el pivote se encontraría en su posición final.
  • Aplicar recursivamente los pasos 1 y 2 a las subvectores que se encuentran a ambos lados del pivote.
Como en todo algoritmo recursivo, tenemos que indicar una condición de salida. En nuestro caso, esta condición se daría cuando tenemos un vector con uno o ningún elemento, en cuyo caso no hay que hacer nada.
El algoritmo quicksort es el siguiente:
función quicksort(vector)

    l := longitud(vector)
    si l <= 1 entonces
        retorna vector
    fin si

    mayores := []
    menores := []
    ma := 1
    me := 1

    pivote := vector[aleatorio(l)]
    repetir desde i:=1 hasta l
        si vector[i] < pivote entonces
            menores[me] := vector[i]
            me := me+1
        si no
            mayores[ma] := vector[i]
            ma := ma+1
          fin si
    fin repetir

    mayores := quicksort(mayores)
    menores := quicksort(menores)
    vector := menores + pivote + mayores
    retorna vector

fin función
Lo primero que hacemos en el algoritmo es comprobar si el vector que hemos recibido tiene uno o ningún elemento, en cuyo caso no hay que hacer nada, ya que se trataría de un vector ordenado; simplemente retornamos el mismo vector que hemos recibido (esta es la condición de parada de la recursividad). A continuación definimos dos vectores auxiliares, uno de ellos para almacenar los valores menores que el pivote, y otro para almacenar los valores mayores, y seleccionamos un elemento al azar del vector, que será nuestro pivote (suponemos para ello que disponemos de una función llamada aleatorio(), que recibe un número n como argumento, y nos devuelve un número aleatorio entre 1 y n). Mediante un bucle de tipo repetir vamos colocando en el correspondiente vector auxiliar aquellos valores que sean mayores o menores que el pivote. Una vez tengamos los vectores completos, lo que hay que hacer es aplicar recursivamente el mismo algoritmo a cada uno de estos vectores auxiliares. Y cuando cuando las llamadas recursivas al algoritmo hayan terminado su trabajo, tendremos otra vez que volver a concatenar los subvectores, que ya estarían ordenados, en un único vector (nuestro ordenador imaginario que ejecuta este pseudocódigo es tan chulo que el operador + aplicado a vectores lo que hace es concatenarlos uno detrás de otro).
La siguiente figura muestra un ejemplo de cómo trabaja el algoritmo. En gris están los pivotes que se seleccionan en cada llamada recursiva al algoritmo.