Es muy frecuente querer ordenar datos que tenemos en un array. Para conseguirlo, existen varios algoritmos sencillos, que no son especialmente eficientes, pero son fáciles de programar. La falta de eficiencia se refiere a que la mayoría de ellos se basan en dos bucles “for” anidados, de modo que en cada pasada quede ordenado un dato, y se dan tantas pasadas como datos existen, de modo que para un array con 1.000 datos, podrían llegar a tener que hacerse un millón de comparaciones.
Existen ligeras mejoras (por ejemplo, cambiar uno de los “for” por un “while”, para no repasar todos los datos si ya estaban parcialmente ordenados), así como métodos claramente más efectivos, pero más difíciles de programar, alguno de los cuales veremos más adelante.
Veremos tres de estos métodos simples de ordenación, primero mirando la apariencia que tiene el algoritmo, y luego juntando los tres en un ejemplo que los pruebe:
Método de burbuja
(Intercambiar cada pareja consecutiva que no esté ordenada)
Para i=1 hasta n-1
Para j=i+1 hasta n
Si A[i] > A[j]
Intercambiar ( A[i], A[j])
Para i=n descendiendo hasta 1
Para j=2 hasta i
Si A[j-1] > A[j]
Intercambiar ( A[j-1], A[j])
Selección directa
(En cada pasada busca el menor, y lo intercambia al final de la pasada)
Para i=1 hasta n-1
menor = i
Para j=i+1 hasta n
Si A[j] < A[menor]
menor = j
Si menor <> i
Intercambiar ( A[i], A[menor])
Inserción directa
(Comparar cada elemento con los anteriores -que ya están ordenados- y desplazarlo hasta su posición correcta).
Para i=2 hasta n
j=i-1
mientras (j>=1) y (A[j] > A[j+1])
Intercambiar ( A[j], A[j+1])
j = j - 1
(Es mejorable, no intercambiando el dato que se mueve con cada elemento, sino sólo al final de cada pasada, pero no entraremos en más detalles).
Ejercicios propuestos: