Algo apasionante para algunos, divertido para otros, y completamente tonto para la mayoria es diseñar, inventar y estudiar algoritmos de ordenamiento. En mi caso, es algo que me interesa. No porque sea apasionante pasar tardes y tardes leyendo sobre esto, sino porque a la hora de probarlo es divertido ver como se ordena, y el hecho de buscar formas de superar el orden del tiempo de ejecución en cada algoritmo obtenido es un desafio bastante intersante.
A continuación presento una de las formas mas básicas, triviales e intuitivas de ordenamiento de una estructura. Es aplicable tambien a listas enlazadas, con ciertas modificaciones.
El algoritmo en cuestión se denomina Insertion-Sort, denominado así por la forma en que se toma cada elemento y se lo inserta en su nueva posición definitiva. Se ejecuta no-recursivamente sobre la estructura misma, y tiene un tiempo de ejecución del orden de N^2, siendo N el número de elementos en la estructura (ya hablaremos de esto al final).
Veamos:
procedimiento InsertionSort(Arreglo[] estructura){
N<- estructura.size() //retorna el número de elementos de la estructura
desde i=0 hasta N-1{
int index=i;
desde j=i hasta 0 {
if (estructura[index]<estructura[j]){
intercambiar(index,j,estructura)
index=j;
}
else break;//salimos porque encontramos la ubicacion final del elemento
}
}//fin procedimiento
Lo que hace, si no se entiende, es tomar cada uno de los elementos y compararlo con sus predecesores en la estructura. Si el elemento actual es menor, se intercambian. Así, una vez ubicado, no es necesario tocarlo nuevamente. Si se piensa a los elementos como burbujas, es como si los mas pesados fueran siendo desplazados hacia arriba por los mas livianos en cada iteración. El método intercambiar simplemente hace eso, intercambia los elementos ubicados en los indices pasados por parametro en la estructura señalada.
El método, implementado en Java luce así:
public static void insertionSort(int[]a){
int n=a.length;
for (int i=1;i<n;i++){
char cursor=a[i];
int j=i-1;
while((j>=0)&&(a[j]>cursor))
a[j+1]=a[j–];
a[j+1]=cursor;
}
}
A simple vista parece un algoritmo ideal: sencillo de pensar e implementar. Pero si nos ponemos a pensar, imaginemos que tenemos que ordenar algo asi como 5000 entradas (alumnos de una universidad), o peor aún, 36.000.000(votantes en un país). El algoritmo evalua cada elemento un0 a uno contra todos los otros (en realidad, contra sus predecesores). En el peor de los casos, el arreglo estará en orden decreciente y, como queremos ordenarlo de menor a mayor, cada elemento deberá moverse hacia su izquierda j-1 (j=posición del elemento en el arreglo) lugares (cabe aclarar, que el mejor escenario es un arreglo ya ordenado, donde se realizan solo N comparaciones). Esto da lugar a la siguiente ecuación:
T(N)= N. (1 + 2 + 3 + 4 + … + (N-1))
Luego, T(N) es del orden de N^2. Algo que, si bien no es el peor de los escenarios, podría ser mucho mejor.
Para la proxima analizaremos otros métodos mas lindos e interesantes, y prometo hablar algo acerca del orden de ejecución de algoritmos, para los que no entiendan a que se refiere que insertionSort sea O(N^2).
the radioliN 