Clasificación de burbujas en Java

Bubble Sort es en la mayoría de los casos el primer algoritmo de clasificación que encontrará. En este artículo, profundizaremos en el algoritmo, cómo funciona y luego lo implementaremos en Java.

Introducción

La clasificación es un aspecto crucial de la digestión de datos. Para nosotros los humanos es mucho más natural ordenar cosas que tienen algo en común como la fecha de publicación, orden alfabético, artículos pertenecientes a un autor, de menor a mayor, etc...

Esto hace que sea mucho más fácil comprender los datos, ya que están lógicamente conectados en lugar de estar dispersos por todas partes.

La clasificación humana es intuitiva y simple y, por lo tanto, a menudo ineficiente. Por lo general, no estamos trabajando con más de dos elementos que deseamos ordenar. Las computadoras pueden almacenar grandes cantidades de datos y ubicaciones de elementos en su memoria, lo que les permite ordenar las colecciones de una manera que los humanos no pueden, sin mencionar la velocidad de acceso/movimiento de elementos.

Clasificación por burbujas {#clasificación por burbujas}

Bubble Sort es, en la mayoría de los casos, el primer algoritmo de clasificación que cualquier entusiasta de la informática encontrará. Son los algoritmos de clasificación más simples e intuitivos, que es una de las principales razones por las que se enseña a programadores/estudiantes novatos.

Funciona intercambiando elementos adyacentes, según un criterio de orden. Por ejemplo, si queremos ordenar los elementos de una colección del más pequeño al más grande, si el primer elemento es más grande que el segundo, se intercambian. Este simple intercambio se repite con índices adyacentes hasta que finalmente se ordena la colección.

La condición de salida para el algoritmo es cuando iteramos a través de toda la colección sin intercambiar un solo elemento, lo que significa que está completamente ordenado.

Aquí hay una representación visual de cómo funciona la ordenación de burbujas:

bubble sort visualization animation gif

Como puede ver, el nombre en sí proviene de la ilusión visual de los elementos "burbujeando" en el lugar deseado. Si sigue un elemento determinado, por ejemplo, ‘8’, puede notarlo "burbujeando" en su lugar correcto en este ejemplo.

Implementación

Con una breve descripción general de la teoría detrás de Bubble Sort, implementémosla clasificando dos tipos diferentes de colecciones. Primero, ordenaremos una matriz simple, y luego ordenaremos una ArrayList con un objeto personalizado y un método compareTo().

Clasificación de matrices {#clasificación de matrices}

Comencemos ordenando una matriz simple de enteros:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public void bubbleSort(int[] array) {
    boolean sorted = false;
    int temp;
    while (!sorted) {
        sorted = true;
        for (int i = 0; i < array.length - 1; i++) {
            if (a[i] > a[i+1]) {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                sorted = false;
            }
        }
    }
}

El indicador sorted se usa para señalar si la matriz está ordenada o no. Si no hay motivo para intercambiar ningún elemento, o si a[i] siempre es menor que a[i+1] en una iteración dada, el indicador ordenado nunca se restablece a falso.

Dado que permanece verdadero, la matriz se ordena y salimos del bucle.

Ejecutando este fragmento de código:

1
2
3
int[] array = new int[]{5, 6, 7, 2, 4, 1, 7};
bubbleSort(array);
System.out.println(Arrays.toString(array));

Rendirá:

1
[1, 2, 4, 5, 6, 7, 7]

Nota: Dado que los arreglos se tratan como objetos en Java, tener un tipo de valor devuelto vacío es absolutamente válido cuando se ordenan los arreglos, y los contenidos no se copian al pie de la letra cuando se usan como argumento. En este caso, la matriz se ordena "en su lugar".

Clasificación de ArrayLists

Un escenario más común sería ordenar una ArrayList poblada por objetos no numéricos. Estos pueden ser empleados, resultados de una base de datos, usuarios, etc. Dado que no sabemos de antemano cómo ordenar estos objetos, la persona que llama deberá proporcionarlos a través del método comapreTo().

Definamos una clase para nuestros objetos que se almacenarán en una colección:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public class Element {
    private int id;

    public Element(int id) {
        this.id = id;
    }

    // Getters and setters

    public int compareTo(Element element) {
        int res = 0;
        if (this.id < element.getId()) {
            res =- 1;
        }
        if (this.id > element.getId()) {
            res = 1;
        }
        return res;
    }
}

Es una clase muy simple con un solo campo: id. También podemos @Override el método toString() si queremos imprimir los resultados, pero en aras de la brevedad, no hagamos eso aquí y simplemente usemos el método getId() en cambio.

Cuando se trata de ordenar ArrayLists, dado que estamos trabajando con objetos, es un poco diferente a ordenar matrices simples de valores primitivos, ya que no podemos usar operadores relacionales.

Ahora, nuestro método compareTo() simplemente compara los ids y devuelve -1 si el id del elemento actual es menor que el elemento con el que lo estamos comparando, 1 si id del elemento actual es mayor, o 0 si son iguales.

Realmente, puede implementar la funcionalidad de comparación de la forma que desee.

Ahora, implementemos Bubble Sort nuevamente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public void bubbleSortArrayList(List<Element> list) {
    Element temp;
    boolean sorted = false;

    while (!sorted) {
        sorted = true;
        for (int i = 0; i < list.size()-1; i++) {
            if (list.get(i).compareTo(list.get(i + 1)) > 0) {
                temp = list.get(i);
                list.set(i, list.get(i + 1));
                list.set(i + 1, temp);
                sorted = false;
            }
        }
    }
}

Este es un código bastante sencillo, prácticamente igual que el código del ejemplo con matrices, utilizando los métodos proporcionados por la interfaz List.

Ahora, completemos una ArrayList con algunos elementos:

1
2
3
4
5
6
7
8
9
List<Element> list = new ArrayList<>();

// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
    list.add(new Element(i));
}

// Move the elements to a random order
Collections.shuffle(list);

Y podemos ordenarlo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Print list before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));

// Sort the list
bubbleSort.bubbleSortArrayList(list);

System.out.println();

// Print sorted list
list.forEach(e -> System.out.print(e.getId() + ", "));

Como era de esperar, la salida es:

1
2
17, 13, 14, 5, 15, 22, 24, 7, 3, 9, 21, 10, 1, 11, 18, 20, 12, 8, 4, 19, 0, 23, 16, 2, 6,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,

La API de colecciones

Una gran cosa acerca de la API de colecciones que se incluye con Java 8 son los métodos auxiliares que le permiten ordenar las colecciones de forma rápida y sencilla. Solo necesitamos implementar la interfaz Comparable para los elementos que deseamos ordenar más adelante.

Cambiemos nuestra clase Elemento para que implemente la interfaz Comparable:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class Element implements Comparable<Element> {
    private int id;

    // Constructor, getters and setters

    @Override
    public int compareTo(Element element) {
        int res = 0;
        if (this.id < element.getId()) {
            res =- 1;
        }
        if (this.id > element.getId()) {
            res = 1;
        }
        return res;
    }
}

Como puede ver, la clase Elemento es más o menos la misma que antes. Esta vez, implementamos la interfaz Comparable y anulamos su método compareTo() con la misma lógica que antes.

Ahora, simplemente podemos llamar a Collections.sort() en nuestra lista:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
List<Element> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    list.add(new Element(i));
}

Collections.shuffle(list);

// Print shuffled list
list.forEach(e -> System.out.print(e.getId() + ", "));

// Sort the list
Collections.sort(list);

System.out.println();

// Print sorted list
list.forEach(e -> System.out.print(e.getId() + ", "));

El método sort() de la API de Colecciones usa Quick Sort para ordenar la colección dada. Esto da como resultado enormes beneficios de rendimiento en comparación con Bubble Sort, pero lo dejaremos para otro artículo.

Complejidad del tiempo {#complejidad del tiempo}

La complejidad temporal (tanto la media como la peor) de Bubble Sort es O(n^2). Esto es, observando de manera realista, horrible para un algoritmo de clasificación.

Aunque horrible, así es como se desempeñó el algoritmo al clasificar 10,000 objetos en una colección:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
List<Element> list = new ArrayList<>();
for (int i = 0; i < 10000; i++) {
    list.add(new Element(i));
}

Collections.shuffle(list);

// Print shuffled collection
list.forEach(e -> System.out.print(e.getId() + ", "));

long startTime = System.nanoTime();
bubbleSort.bubbleSortArrayList(list);
long endTime = System.nanoTime();

// Print sorted collection
list.forEach(e -> System.out.print(e.getId() + ", "));

System.out.println();

// Print runtime in nanoseconds
System.out.println("Bubble Sort runtime: " + (endTime - startTime));

Y aquí están los resultados en segundos después de ejecutarlo 10 veces:


Tiempo(s) de clasificación de burbujas Primera ejecución 0.5885202 Segunda ejecución 0.6647364 Tercera Ejecución 0.5748066 Cuarta Ejecución 0.5266222 Quinta carrera 0.522961 Sexta Ejecución 0.5033268 Séptima carrera 0.5044489 Ocho Correr 0.6409187 Novena Ejecución 0.6021427 Décima Carrera 0.694294


Con un tiempo de ejecución promedio de ~0.5s para 10,000 objetos, ¿realmente necesitará algoritmos que funcionen mejor? La mayoría de las veces, no realmente, a menos que tenga una aplicación con mucha carga que requiera un tiempo de respuesta rápido.

Si está haciendo comparaciones más complejas que simplemente comparar ids y tiene una gran colección, mucho más grande que esta, sí, usar un algoritmo avanzado con una complejidad de tiempo mucho mejor afectará significativamente su rendimiento.

Como referencia, el método sort() de la API de Colecciones clasificó esta misma matriz de 10 000 elementos en solo 0,01 s de manera consistente. Entonces, incluso si no hay una necesidad real de ordenar sus colecciones más rápido que 0.5 segundos, el uso de un clasificador integrado proporcionado por la API de colecciones le ahorrará tiempo al codificar y mejorará su aplicación.

Conclusión

Bubble Sort es, en la mayoría de los casos, el primer algoritmo de clasificación que cualquier entusiasta de la informática encontrará. Es el algoritmo de clasificación más simple e intuitivo, que es una de las principales razones por las que se enseña en un punto temprano.

Vimos que este algoritmo de clasificación simple funciona intercambiando elementos adyacentes, de acuerdo con un criterio de orden dado. Por ejemplo, si queremos ordenar los elementos de una colección del más pequeño al más grande, si el primer elemento es más grande que el segundo, se intercambian. Este intercambio simple se repite para los índices adyacentes hasta que finalmente se ordena la colección.

Es terriblemente ineficiente y dado que hay algoritmos mucho más eficientes integrados en Java en la API de Colecciones, le recomendamos que no use este algoritmo para ninguna aplicación de producción. n.