Clasificaci贸n de burbujas en Java

     

    Introducci贸n

    Algo as铆 como es un aspecto cr铆tico de la digesti贸n de datos. Para nosotros, amigos, es mucho m谩s natural ordenar las cosas que tienen algo en com煤n, como la fecha de publicaci贸n, el orden alfab茅tico, los art铆culos por autor, de menor a mayor, etc.

    Esto hace que los datos sean mucho m谩s f谩ciles de entender, ya que est谩n conectados l贸gicamente en lugar de dispersos.

    La clasificaci贸n humana es intuitiva y simple y, por lo tanto, a menudo ineficaz. Por lo general, no trabajamos con m谩s de dos caracter铆sticas que queremos ordenar. Las computadoras son capaces de almacenar grandes cantidades de datos y ubicaciones de elementos en su memoria, lo que les permite ordenar colecciones de una manera que los humanos no podr铆an, sin mencionar la velocidad de acceso / movimiento de los elementos.

    Ordenamiento de burbuja

    Bubble Sort es, en la mayor铆a de los casos, el primer algoritmo de clasificaci贸n que encontrar谩 cualquier entusiasta de la inform谩tica. Es el algoritmo de clasificaci贸n m谩s simple e intuitivo, que es una de las principales razones por las que se ense帽a a nuevos programadores / estudiantes.

    Funciona intercambiando elementos adyacentes, seg煤n criterio de mando. Por ejemplo, si queremos ordenar los elementos de la 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 del algoritmo es cuando recorremos toda la colecci贸n sin intercambiar un solo elemento, lo que significa que est谩 completamente ordenado.

    Aqu铆 hay una demostraci贸n visual de c贸mo funciona la clasificaci贸n de burbujas:

    Como puede ver, el nombre en s铆 proviene de la ilusi贸n visual de elementos “burbujeantes” hacia donde se necesitan. Si sigue una funci贸n en particular, diga, 8 – puede notar que est谩 “burbujeando” en el lugar correcto en este ejemplo.

    Implementaci贸n

    Con una breve descripci贸n general de la teor铆a detr谩s de la clasificaci贸n de burbujas fuera del camino, apliqu茅mosla clasificando dos tipos diferentes de colecciones. Primero, ordenaremos un conjunto simple y luego ordenaremos ArrayList con un objeto personalizado y un compareTo() m茅todo.

    Ordenar matrices

    Comenzamos ordenando un conjunto de n煤meros enteros:

    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 es sorted se usa una bandera para indicar si la edici贸n est谩 editada o no. Si no hay raz贸n para cambiar ning煤n elemento o reemplazar a[i] siempre menos que a[i+1] en una iteraci贸n separada, el sorted una bandera nunca se reinicia false.

    Porque se queda true, la matriz se ordena y salimos del bucle.

    Pase este c贸digo:

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

    El resultado ser谩:

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

    Nota: Dado que las matrices se tratan como objetos en Java, s铆 void el tipo de retorno es completamente v谩lido al ordenar matrices, y el contenido no se copia al pie de la letra cuando se usa como argumento. En este caso, la edici贸n est谩 “en vigor”.

    Ordenar listas de matrices

    Un escenario m谩s com煤n ser铆a ordenar ArrayList poblado por objetos no num茅ricos. Estos pueden ser empleados, resultados de bases de datos, usuarios, etc. Dado que no sabemos de antemano c贸mo resolver estas cosas, la persona que llama tendr谩 que proporcionarlo a trav茅s del comapreTo() m茅todo.

    Definamos una clase para nuestros elementos que se almacenar谩n en una colecci贸n:

    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 谩rea: id. Nosotros tambien podemos @Override un toString() m茅todo si queremos imprimir los resultados, pero en aras de la nitidez, no lo hagamos aqu铆 y all谩 getId() m茅todo en su lugar.

    Para clasificar ArrayLists, dado que estamos trabajando con objetos, es un poco diferente a ordenar arreglos simples de valores primitivos, ya que no podemos usar operadores relativos.

    Ahora nuestro compareTo() el m茅todo compara el idsy devoluciones -1 Si el id el elemento actual es m谩s peque帽o que el elemento que estamos comparando, 1 Si el id del elemento de corriente superior, o 0 si son id茅nticos.

    De hecho, puede aplicar la funcionalidad comparativa de la forma que desee.

    Ahora volvamos a aplicar Bubble Sort:

    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 simple, casi id茅ntico al c贸digo del ejemplo con matrices, utilizando los m茅todos proporcionados por List interfaz.

    Ahora, hagamos una poblaci贸n ArrayList con algunos elementos:

    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:

    // 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, el resultado es:

    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,
    

    API de colecciones

    Una gran ventaja de la API de colecciones que se inicia con Java 8 son los m茅todos de asistente que le permiten ordenar las colecciones de forma r谩pida y sencilla. Solo necesitamos el Comparable interfaz para los elementos que queremos ordenar m谩s tarde.

    Cambiamos nuestro Element clase para que el Comparable interfaz:

    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, el Element la clase es casi la misma que antes. Esta vez, ponemos el Comparable interfaz y anularla compareTo() m茅todo con la misma l贸gica que antes.

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

    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 es sort() utiliza el m茅todo de la API de clasificaci贸n r谩pida de colecciones para ordenar la colecci贸n dada. Esto tiene enormes ventajas de rendimiento en comparaci贸n con Bubble Sort, pero lo guardaremos para otro art铆culo.

    Complejidad del tiempo

    O (n ^ 2) es la media temporal (media y peor) de Clasificaci贸n de burbujas. Esto es, desde el punto de vista realista, terrible para un algoritmo de clasificaci贸n.

    Si bien es terrible, as铆 es como funcion贸 el algoritmo al recolectar 10,000 objetos en una colecci贸n:

    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 ejecutar 10 veces:

    Hora (s) de clasificaci贸n de burbujas

    Primer intento0.5885202
    Segunda ejecuci贸n0,6647364
    La tercera carrera0.5748066
    Cuarta carrera0.5266222
    Quinta carrera0.522961
    La sexta carrera0.5033268
    S茅ptima carrera0.5044489
    Ocho carreras0,6409187
    La novena carrera0.6021427
    La d茅cima carrera0,694294

    Con un tiempo de ejecuci贸n medio de ~ 0,5 s 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 de alta carga que requiera un tiempo de respuesta r谩pido.

    Si est谩 haciendo comparaciones m谩s complejas que solo hacer una comparaci贸n idsy tienen una colecci贸n enorme, mucho m谩s que esta; s铆, si se usa un algoritmo avanzado con una complejidad de tiempo mucho mejor, afectar谩 en gran medida su rendimiento.

    Como referencia, el sort() Ordene el m茅todo de la API de colecciones de este mismo conjunto de 10,000 elementos en solo 0.01s de manera consistente. Por lo tanto, incluso si no hay una necesidad real de ordenar sus colecciones m谩s r谩pido que 0.5s, ahorrar谩 tiempo mientras codifica y mejora su aplicaci贸n usando un clasificador integrado provisto por la API de Colecciones.

    Conclusi贸n

    Bubble Sort es, en la mayor铆a de los casos, el primer algoritmo de clasificaci贸n que encontrar谩 cualquier entusiasta de la inform谩tica. Es el algoritmo de clasificaci贸n m谩s simple e intuitivo y es una de las principales razones por las que se ense帽a temprano.

    Hemos visto que este sencillo algoritmo de clasificaci贸n funciona intercambiando elementos adyacentes, de acuerdo con criterios de comando espec铆ficos. Por ejemplo, si queremos ordenar los elementos de la 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 para 铆ndices adyacentes hasta que finalmente se ordena la colecci贸n.

    Es muy eficiente y dado que los algoritmos mucho m谩s eficientes est谩n integrados en Java en la API de colecci贸n, le recomendamos que no utilice este algoritmo para ninguna aplicaci贸n de producci贸n.

    .

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *