Algoritmos de ordenación [I]

[forCode]

Bueno, como bien dice la entrada, hoy voy a hablar sobre algoritmos de ordenación. Cierto es que Java ya incluye algunas herramientas para la ordenación automática de los elementos en las colecciones, pero nunca está de más conocer qué algoritmos se usan, o qué algoritmos hay disponibles.

¿Qué es un algoritmo de ordenación?

Un algoritmo de ordenación es simplemente un conjunto finito de operaciones que nos permiten, como bien indica su nombre, ordenar. Sea cual sea la colección.

Como especifico en la introducción, Java ya implementa algún que otro método para la ordenación de colecciones, un buen ejemplo es la interfaz ‘SortedSet’ o la colección ‘TreeSet’, que permiten ordenar los elementos de acuerdo a su ordenación natural o implementando un ‘Comparator’. Pero esa interfaz no puede cubrir todos los casos, porque como ya sabemos pueden ser miles los casos que se pueden presentar de ordenación, y no todos ellos podrán ser cubiertos, quedando algunos sin cubrir, como la ordenación de una matriz de números enteros.

Existen muchos algoritmos de ordenación y sería imposible contemplarlos todos en un único post, así que escribiré una serie de posts en los que intentaré abarcar los máximos algoritmos posibles. Hoy os traigo uno conocido como «Ordenamiento de burbuja», es uno de los algoritmos más básicos y de los primeros que aprendemos los programadores (también de los primeros que algunos olvidan), ya que la eficiencia de estos algoritmos siempre está en una entredicha.

Funcionamiento

El algoritmo de ordenación de burbuja, simplemente recorre la colección ‘n-1’ veces, siendo ‘n’ el tamaño total de la colección. En cada recorrido se vuelve a recorrer ‘n-1’ veces. En el segundo recorrido anidado, comprueba si el elemento ‘i’ es mayor que el ‘i+1’ en el caso de que sea afirmativo, los índices se intercambian, de lo contrario, conservan sus índices.

Aquí podemos ver un ejemplo gráfico de cada recorrido anidado:

Este recorrido anidado se emplearía ‘n-1’ veces más, logrando así la ordenación total.

Código

Bien pasamos a la parte del código:

public void OrdenacionBurbuja(int[] lista){

int aux;

for (int i = 0; i<lista.length-1;i++){
    for (int j = 0; j<lista.length-1;j++){
        if (lista[j] > lista[j+1]){
            aux = lista[j+1];
            lista[j+1] = lista[j];
            lista[j]= aux;
            }
        }
    }
}

Como veis es una simple función, a la que le pasas una matriz y ésta función te ordena la matriz, no hace falta devolver nada, ya que te cambia automáticamente la matriz que pasaste.

Hasta aquí ha llegado el primero de los algoritmos de ordenación, muy básico e ineficiente, iremos viendo más, y más complejos…