Otro algoritmo de orden


He decidido hacer otro artículo sobre un algoritmo para ordenar los elementos de un vector, ya que ando corto de ideas, y esto puede ser interesante. Ya hablamos del mergesort en un artículo anterior. Aquí voy a presentar un algoritmo llamado quicksort, inventado por Tony Hoare.

El algoritmo es bajo mi punto de vista, mucho más elegante que el mergesort, en el sentido de que es más simple, más fácil de implementar, y no tienes que tener cuidado con los casos en el que el vector no es divisible en la manera en la que tu algoritmo divide, porque aquí siempre lo es.

Con respecto al tiempo. Tiene de media un tiempo algorítmico medio de {O}(n\log n) . En el peor caso, el tiempo es de {O}(n^2), pero es muy raro que pase eso. Además en el tiempo medio es un pelín más rápido que mergesort en cuestión de constantes.

El algoritmo funciona “partiendo” el vector en vectores más pequeños alrededor de un elemento del vector llamado pivote. El pivote puede ser cualquier elemento, una vez elegido, se ordenará el vector sólo con respecto a ese pivote, de manera que los elementos a la izquierda del pivote, sin estar ordenados entre ellos, sean todos menores que el pivote, y los que están a la derecha, sean todos mayores. Una vez hecho esto, se cogen los (sub)vectores a la izquierda y derecha del pivote y se llama recursivamente a la función para que ordene estos vectores, luego se juntan todos.

El pivote puede ser cualquier elemento, aunque lo ideal es que caiga lo más al centro que podamos, porque conseguimos tiempos menores. Como vemos, la complejidad de este algoritmo está en el momento de partir el vector, esto es, ordenar los elementos de manera que a la derecha del pivote sean mayores y a la izquierda menores. El resto son llamadas recursivas sin más misterio.

¿Cómo lo partiremos? Está claro que hay que hacerlo en tiempo lineal, ya que es posible y bastante simple, y si no en cada llamada recursiva estaríamos teniendo un tiempo cuadrático y el tiempo global no podría ser logarítmico-lineal, como es este. Hay muchas maneras de partir el vector, yo voy a dar aquí un pseudo-código, pero si no lo miras y piensas por tu cuenta, seguro que se te ocurrirán varias maneras de hacerlo, el mérito de este algoritmo fue que se le ocurriese no esta parte.

pivote = elegir_pivote;

swap(pivote,vector[0]);

i=j=1; //Empiezan en el segundo elemento del vector.
for i=1..n
    if vector[i]<pivote
        swap(vector[i],vector[j]);
        j++;
    end
end
swap(vector[j-1],pivote);

¿Cómo funciona? Es fácil. Lo primero elegimos un elemento pivote, hay muchas maneras de hacerlo, puedes simplemente coger el primer elemento del vector. Ahora movemos el pivote al primer puesto del vector, para que esté al principio, y con un bucle recorremos el resto de elementos, desde el segundo, hasta el final. Cada vez que nos encontramos un elemento menor que el pivote, lo cambiamos con el elemento de índice j, y le sumamos uno a j. La variable j, se quedará, si te fijas bien, en el primer elemento que sea mayor que el pivote, ya que le sumamos uno cada vez que encontramos un elemento menos que el pivote. Cuando acabe tendremos primero el pivote, luego, hasta j-1, los menores que el pivote, y desde j hasta n los mayores que el pivote, ya sólo hay que cambiar el elemento j-1 con el pivote, y tendremos el vector con los elementos menores que el pivote, luego el pivote, y luego los mayores.

Ya sólo habría que ordenar cada vector a los lados del pivote, por lo que es evidente que el pivote ya está colocado en su sitio. Pues sacamos dichos vectores y llamamos recursivamente a la función con esos vectores.

¿Cómo elegir un pivote? Como he dicho antes, puedes simplemente coger el primero del vector, pero no es recomendable. Se puede demostrar matemáticamente que la mejor manera de hacerlo es coger pivotes al azar, porque conseguirás una media de ejecución de O(n\log n). Así que puedes hacer que coja un elemento al azar, lo mueva a la primera posición, y luego partas el vector.

Pues ya está prueba a crear un código con el algoritmo, verás que sencillo es y que “elegante” queda… 😉

Un saludo.

Anuncios
Esta entrada fue publicada en Manuales, Tutoriales y etiquetada , , , , , . Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s