Bubble Sort - Conceptos de codificación N

¿Por qué se llama clasificación de burbujas?

Bubble Sort no es más que un algoritmo de comparación donde -

  • Al final de la primera iteración, el elemento de matriz más grande se coloca en el último índice
  • Al final de la segunda iteración, el segundo elemento más grande de la matriz se coloca en el penúltimo índice y así sucesivamente...

De esta manera, los elementos grandes se mueven a los últimos índices y, por lo tanto, los elementos pequeños se mueven a los índices de inicio, lo que también se denomina "burbuja" de elementos más pequeños al principio de la lista, por eso se llama clasificación de burbuja.

Ejemplo paso a paso

Tomemos la matriz de números "5 1 4 2 8" y clasifiquemos la matriz desde el número más pequeño hasta el número más grande utilizando la clasificación de burbujas. En cada etapa, los elementos escritos en audaz se están comparando. Se requerirán tres pases.

Primer pasaje:

( 5 1 4 2 8 ) —— ( 15 4 2 8 ), Aquí, el algoritmo compara los dos primeros elementos y los intercambia desde 5 > 1.

( 1 5 4 2 8 ) —— ( 1 4 5 2 8 ), Cambiar de 5 > 4

( 1 4 5 2 8 ) —— ( 1 4 2 5 8 ), Cambiar de 5 > 2

( 1 4 2 5 8 ) —— ( 1 4 2 5 8 ), ahora bien, como estos elementos ya están en orden (8 > 5), el algoritmo no los permuta.

Segundo pase:

( 1 4 2 5 8 ) —— ( 1 4 2 5 8 )

( 1 4 2 5 8 ) —— ( 1 2 4 5 8 ), Cambiar de 4 > 2

( 1 2 4 5 8 ) —— ( 1 2 4 5 8)

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

Ahora la matriz ya está ordenada, pero el algoritmo no sabe si está completa. El algoritmo necesita un pase completo sin intercambios para saber que está ordenado.

Tercer pase:

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

( 1 2 4 5 8 ) —— ( 1 2 4 5 8)

( 1 2 4 5 8 ) —— ( 1 2 4 5 8 )

package com.abc;

public class BubbleSort {

    public static void main(String[] args){
        int[] array = new int[]{5, 1, 12, -5, 16};
        BubbleSort.sort(array);
    }
    
    private static void sort(int[] array){
        int count = 0;
        for(int i = array.length ; i > 0 ; i --, count++){
            for(int j = 0 ; j < array.length-1 ; j++, count++){
                if(array[j] > array[j+1]){
                    swapNumbers(j, j+1, array);
                }
            }
        }
        printNumbers(array, count);
    }
    
    private static void swapNumbers(int i, int j, int[] array) {
        int temp;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    private static void printNumbers(int[] array, int count) {
        System.out.print("Sorted Array : {");
        for(int i : array){
            System.out.print(i + " ");
        }
        System.out.print("}, n : " + array.length + ", comparisons : " + count);
    }
}

Output

Sorted Array : {-5 1 5 12 16 }, n : 5, comparisons : 25

La complejidad temporal para el peor de los casos es O(n2). El algoritmo aún se puede mejorar:

private static void sort(int[] array){
    int count = 0;
    for(int i = array.length ; i > 0 ; i --, count++){
        for(int j = 0 ; j < i-1 ; j++, count++){
            if(array[j] > array[j+1]){
                swapNumbers(j, j+1, array);
            }
        }
    }
    printNumbers(array, count);
}

Output

Sorted Array : {-5 1 5 12 16 }, n : 5, comparisons : 15

Si quieres conocer otros artículos parecidos a Bubble Sort - Conceptos de codificación N puedes visitar la categoría Tutoriales.

Deja un comentario

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

Subir

Esta página web utiliza cookies para analizar de forma anónima y estadística el uso que haces de la web, mejorar los contenidos y tu experiencia de navegación. Para más información accede a la Política de Cookies . Ver mas