Ordenar elementos de un vector


En este artículo voy a tratar un tema que aunque no representa nada moderno, sí trata sobre cómo hacer códigos eficientes, y eso es algo importante siempre. El problema es bastante simple, así que no voy a descubrir América con este artículo, pero espero ayudar a muchos.

Vamos a ordenar los elementos de un vector, y lo vamos a hacer de dos maneras. Vamos a usar un algoritmo de fuerza bruta, simple pero lento, y otro mucho más eficiente (el mergesort), que reduce mucho el tiempo de ejecución. Discutiré los tiempos (más técnicamente, orden de complejidad, que no es lo mismo) de cada uno y cómo se llega a ellos.

A lo que vamos. Apostaría una comida a que todo el que haya aprendido a programar en algún momento se ha enfrentado a la simple tarea de recibir un vector de números y tener que ordenarlo. Y seguramente a todo el mundo se le ocurriese, como se me ocurrió a mi, la simple tarea de recorrer el vector por pares de elementos, y si vemos un par desordenado, lo cambiamos y punto. Así de simple. El pseudo-código de ese algoritmo sería como sigue:

vector[n] //Vector de n elementos desordenados.

for i=1..(n-1)
     for j=(i+1)..n
          if vector[i]>vector[j]
               aux = vector[i];
               vector[i] = vector[j];
               vector[j] = aux;
          end
     end
end

Ya está. Como vemos, es un algoritmo muy simple. Pasamos por el vector, y por cada uno de sus elementos recorremos los siguientes, cambiando los elementos cuando nos encontremos con una inversión (una inversión es un par de elementos desordenados).

Analicemos este algoritmo. Vamos a hacer una cosa que se llama análisis asintótico, que aplicado a algoritmos equivale a encontrar su tiempo de ejecución, y nos permite saber cómo de rápido o lento es lo que hacemos. Es más simple de lo que suena, consiste simplemente en encontrar, en este caso, cuántas operaciones realizará el ordenador para ordenar un vector de n elementos, usando el algoritmo de arriba.

Matemáticamente, consistirá en comparar dos funciones, la que represente el número de operaciones de nuestro algoritmo, con otra tipo mucho más simple, que consistirá simplemente en eliminar constantes y coeficientes reales que no dependan de n.

Nuestro algoritmo recorre el vector con dos bucles for anidados, si lo analizamos, vemos que recorre exactamente una vez cada par de elementos. Si separamos el vector en todos los posibles subconjuntos de dos elementos, lo estaremos separando en todos los pares de números del vector. ¿Cuántos subconjuntos hay? Esto es combinatoria simple, y lo podemos saber con el número combinatorio, eligiendo 2 elementos de un conjunto de n. El número total será:

\binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n^2-n}{2}

Así que un único bucle equivalente recorrería (n²-n)/2 elementos. Si volvemos a mirar el algoritmo, vemos que por cada uno de esos pares estamos realizando primero un if, y si el if se cumple tres asignaciones a variables. En el peor de los casos, es decir, que el vector esté completamente invertido y que siempre entre al if, entonces para cada par de elementos realizará 4 operaciones (un if y 3 asignaciones), así que el número total de operaciones del algoritmo es, en el peor de los casos:

4 \frac{n^2-n}{2} = 2(n^2-n)

En este caso sería fácil calcular ahora el número de operaciones en el mejor de los casos, es decir, cuando el vector ya está ordenador, y nunca entra al if, entonces realizaría sólo las operaciones de más arriba:

\frac{n^2-n}{2}

Y ahora podemos hallar el tiempo medio, haciendo la media de las dos:

\frac{5(n^2-n)}{4}

De todos modos, se suele dejar el tiempo en el peor caso. Y ahora buscamos una función tal que en el paso al límite, cuando n tiende a infinito, el límite sea finito y distinto de cero, buscando así un límite asintótico de la función. Esto, más informalmente, significa quitar constantes y coeficientes, y términos de n de grado menor al mayor que tengamos. Lo que estamos hallando es el orden de complejidad, en vez del tiempo, y nos da una idea, a la hora de comparar algoritmos, de cuál nos puede beneficiar. En este caso quitamos el 2 y la n, y queda que nuestro algoritmo tiene un orden de ejecución de O(n^2). La O es la conocida como notación de O grande, en inglés Big Oh notation, busca info en la wiki.

¿Podemos encontrar un algoritmo mejor, que nos ordene el vector en mucho menos tiempo? La respuesta es un evidente sí, y de hecho ya lo he nombrado más arriba. El algoritmo se conoce como mergesort y es un algoritmo recursivo, que consiste en separar el vector en dos vectores de menor tamaño y ordenarlos por separado, consiguiendo así mucho menos tiempo. Fíjate en que si el algoritmo se ejecuta en O(n²), entonces meter un elemento más en el vector significa subir mucho el tiempo. Así que si lo separamos en dos, entonces el tiempo de cada uno no será la mitad, sino mucho menor.

El algoritmo mergesort funciona de la siguiente manera:

mergesort (vector)
     if vector.tamaño == 2
          if vector(1)>vector(2)
               aux = vector(1);
               vector(1) = vector(2);
               vector(2) = aux;
          end
          return vector; //Y se acaba la función
     end

     //Esto se ejecutará si mide más de 2
     a1,a2 //Vectores de la mitad del tamaño que el vector de entrada
     for i=1..vector.tamaño
          if i<vector.tamaño/2
               a1(i) = vector(i);
          else
               a2(i-vector.tamaño/2) = vector(i);
          end
     end //Todo este for lo único que hace es separar el vector en dos de la mitad del tamaño, partiéndolo por la mitad

     a1 = mergesort(a1);
     a2 = mergesort(a2);
     vector_ordenador = merge(a1,a2);
     return vector_ordenador;
  1. Le llega un vector que ordenar, lo mira, si es de longitud 2, lo ordena y lo devuelve.
  2. Si es mayor de 2, entonces lo divide en dos vectores partiéndolo por la mitad, y se llama a si mismo con esos vectores para que los ordene.
  3. Luego junta esos dos vectores en el original ordenando sus elementos.

Es evidente que no podemos juntarlos sin más. Los dos vectores menores se juntan en un proceso llamado merge (bastante evidente), que tiene la ventaja de ejecutarse en tiempo lineal O(n). El algoritmo es muy simple:

a1,a2 vectores de entrada
salida, vector de salida ordenado
for i=1..n
    if a1(j) < a2(k)
       salida(i) = a1(j);
       j++;
    else
       salida(i) = a2(k);
       k++;
    end
end

Cuidado, que no he tenido en cuenta lo que pasa si se llega al final y podría mejorarse. Eso es sólo para coger una idea de cómo va.

Bien. Tenemos de momento el algoritmo de unión (merge), que se ejecuta en tiempo O(n), lo que es fácil ver, porque hay un único bucle que va de 1 a n. ¿Cuántas veces tendrá que ejecutarse? Vamos a replantear el algoritmo de una manera que lo podamos visualizar mejor. Vamos a crear un árbol (conviene, de hecho, hacerlo normalmente con algoritmos recursivos). Empezamos con un vector de n elementos, en el nivel siguiente (después de la primera llamada recursiva), tendremos el doble de vectores que en el anterior, ya que nuestro algoritmo parte el vector en 2 y ordena cada mitad. Así que el número de vectores en cada nivel será, empezando en el nivel 0 con el vector completo: 2^j, para cada nivel j. En cada nivel tendremos que hacer el “merge” tantas veces como haga falta, dependerá del número de vectores, es decir, de cuanto valga 2^j, pero lo bueno es que la longitud del vector va cambiando, cada vez es la mitad, es decir, la longitud por nivel de cada vector es de n/2^j, así que el trabajo que hay que hacer por nivel es:

2^j*m*\frac{n}{2^j} = O(n)

m es el número de instrucciones del “merge”, una constante, y vemos que queda tan sólo una n, así que es lineal. Nos comemos las constantes porque buscamos un orden de complejidad, no un tiempo real. Vemos lo bueno del algoritmo y es que el tiempo de ejecución es independiente del nivel, ya que el número de problemas aumenta al doble, pero su tamaño se divide entre 2, así que el total, resulta que el trabajo del algoritmo por cada nivel es lineal, y de hecho constante. Dependerá sólo del número de elementos del vector inicial.

Ya tenemos el tiempo de ejecución por nivel O(n), así que el tiempo de ejecución total es fácil, sólo hay que calcular el número de niveles al que se llegará. Recordemos que irá dividiendo entre 2 hasta llegar a vectores de longitud 2 que pueda ordenar trivialmente. Si la longitud de cada vector por nivel es n/2^j, entonces el número de niveles lo podemos averiguar igualando lo anterior a la longitud del último nivel, que conocemos, ya que es 2 (cuando el algoritmo deja de dividir).

\frac{n}{2^j} = 2\quad\quad n = 2^{j+1}\quad\quad j = (\log_2 n)-1

Ya tenemos el número total de niveles, que va como O(log n) (log es en base 2). Cada nivel por el trabajo de merge O(n). El orden de complejidad del algoritmo es O(n log n).

Vemos que es mucho menor que el primer algoritmo del artículo, que va cuadráticamente. Este va como n log n. Para vectores muy grandes la diferencia será enorme, siendo este último muchísimo más rápido.

Como ejercicio, te propongo que calcules el tiempo real del algoritmo, que va en función del número de instrucciones. Te tiene que salir del tipo n log n, sólo que multiplicado por constantes o sumando constantes. Aquí te dejo un programa de ejemplo hecho por mi. (Sólo ordena vectores de un tamaño que vaya como 2^k).

http://pastebin.com/p6WZ5bC2

Debes incluir en el directorio un archivo con 65536 números desordenados, puedes comparar ambos algoritmos y ver la diferencia. Si no quieres hacer el archivo, prueba a simplemente cambiar el vector para ver que funciona y meter uno directamente antes de compilarlo.

Un saludo, y espero que alguien le sea útil.

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