Implementación de clasificación de burbujas en Java

Existe una gran cantidad de algoritmos de clasificación, muchos de ellos son muy específicos y fueron desarrollados para resolver una gama limitada de problemas y trabajar con tipos específicos de datos. Pero entre toda esta diversidad, el algoritmo más simple es merecidamente el tipo burbuja, que puede implementarse en cualquier lenguaje de programación. A pesar de su simplicidad, es la base de muchos algoritmos bastante complejos. Otra ventaja igualmente importante es su sencillez y, por tanto, puede recordarse e implementarse inmediatamente, sin tener que disponer de literatura adicional.

Introducción

Toda la Internet moderna se compone de una gran cantidad de diferentes tipos de estructuras de datos recopiladas en bases de datos. Almacenan todo tipo de información, desde datos personales de los usuarios hasta el núcleo semántico de sistemas automatizados altamente inteligentes. No hace falta decir que la clasificación de datos juega un papel extremadamente importante en esta enorme cantidad de información estructurada. La clasificación puede ser un paso obligatorio antes de buscar información en la base de datos, y el conocimiento de los algoritmos de clasificación juega un papel muy importante en la programación.

Clasificando a través de ojos de máquina y ojos humanos

Imaginemos que necesita ordenar 5 columnas de diferentes alturas en orden ascendente. Estas columnas pueden significar cualquier tipo de información (precios de acciones, ancho de banda del canal de comunicación, etc.); puede presentar algunas de sus propias versiones de esta tarea para que quede más clara. Bueno, como ejemplo, ordenaremos a los Vengadores por altura: A diferencia de un programa de computadora, la clasificación no será difícil para usted, porque puede ver la imagen completa y puede determinar inmediatamente qué héroe debe moverse y dónde para que la clasificación por altura se complete con éxito. Probablemente ya hayas adivinado que para ordenar esta estructura de datos en orden ascendente, basta con intercambiar los lugares de Hulk y Iron Man:

¡Hecho!

Y esto completará la clasificación con éxito. Sin embargo, la computadora, a diferencia de usted, es algo estúpida y no ve toda la estructura de datos en su conjunto. Su programa de control sólo puede comparar dos valores a la vez. Para resolver este problema, tendrá que colocar dos números en su memoria y realizar una operación de comparación con ellos, para luego pasar a otro par de números, y así sucesivamente hasta haber analizado todos los datos. Por lo tanto, cualquier algoritmo de clasificación se puede simplificar mucho en tres pasos:

• Compara dos elementos;
• Intercambia o copia uno de ellos;
• Ir al siguiente elemento;

Diferentes algoritmos pueden realizar estas operaciones de diferentes maneras, pero pasaremos a considerar cómo funciona la clasificación de burbujas.

Algoritmo de clasificación de burbujas

La clasificación de burbujas se considera la más simple, pero antes de describir este algoritmo, imaginemos cómo clasificarías a los Vengadores por altura si pudieras, como una máquina, comparar solo dos héroes entre sí en un período de tiempo. Lo más probable es que haga lo siguiente (lo más óptimo):

• Te mueves al elemento cero de nuestra matriz (Black Widow);
• Compara el elemento cero (Black Widow) con el primero (Hulk);
• Si el elemento en la posición cero es mayor, los intercambias;
• De lo contrario, si el elemento en la posición cero es más pequeño, los dejas en su lugar;
• Muévete a una posición a la derecha y repite la comparación (compara a Hulk con el Capitán)

Después de revisar toda la lista de una sola vez con dicho algoritmo, la clasificación no se completará por completo. Pero, por otro lado, el elemento más grande de la lista se moverá a la posición del extremo derecho. Esto siempre sucederá, porque tan pronto como encuentres el elemento más grande, cambiarás constantemente de lugar hasta moverlo hasta el final. Es decir, tan pronto como el programa "encuentre" a Hulk en la matriz, lo moverá hasta el final de la lista: Es por eso que este algoritmo se llama clasificación de burbujas, porque como resultado de su operación, el elemento más grande de la lista estará en la parte superior de la matriz y todos los elementos más pequeños se desplazarán una posición hacia la izquierda: Para completar la clasificación, deberá volver al principio de la matriz y repetir los cinco pasos descritos anteriormente nuevamente, moviéndose nuevamente de izquierda a derecha, comparando y moviendo elementos según sea necesario. Pero esta vez necesitas detener el algoritmo un elemento antes del final de la matriz, porque ya sabemos que el elemento más grande (Hulk) está absolutamente en la posición más a la derecha: Entonces el programa debe tener dos bucles. Para mayor claridad, antes de pasar a revisar el código del programa, puedes ver una visualización de cómo funciona la clasificación de burbujas en este enlace: Visualización de cómo funciona la clasificación de burbujas

Implementación de clasificación de burbujas en Java

Para demostrar cómo funciona la clasificación en Java, aquí está el código del programa:

• crea una matriz de 5 elementos;
• sube en él el ascenso de los vengadores;
• muestra el contenido de la matriz;
• implementa clasificación de burbujas;
• vuelve a mostrar la matriz ordenada.

Puede ver el código a continuación e incluso descargarlo en su IDE IntelliJ favorito . Se analizará a continuación:

class ArrayBubble{
    private long[] a;   // referencia de matriz
    private int elems;  //numero de elementos en el arreglo

    public ArrayBubble(int max){    // constructor de clases
        a = new long[max];          //crear una matriz con tamaño máximo
        elems = 0;                  //cuando se crea, la matriz contiene 0 elementos
    }

    public void into(long value){   // método para insertar un elemento en una matriz
        a[elems] = value;           //insertar valor en el arreglo a
        elems++;                    //aumenta el tamaño de la matriz
    }

    public void printer(){          // método para enviar una matriz a la consola
        for (int i = 0; i < elems; i++){    //para cada elemento de la matriz
            System.out.print(a[i] + " ");   // salida a la consola
            System.out.println("");         //una nueva línea
        }
        System.out.println("----Finalizar matriz de salida----");
    }

    private void toSwap(int first, int second){ // el método intercambia un par de números de matriz
        long dummy = a[first];      // poner el primer elemento en una variable temporal
        a[first] = a[second];       // poner el segundo elemento en lugar del primero
        a[second] = dummy;          //en lugar del segundo elemento, escribe el primero desde la memoria temporal
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  // Bucle exterior
            for (int in = 0; in < out; in++){       //bucle interno
                if(a[in] > a[in + 1])               //Si el orden de los elementos es incorrecto
                    toSwap(in, in + 1);             // llamar al método de intercambio
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Crear matriz matriz con 5 elementos

        array.into(163);       //llenar la matriz
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //mostrar elementos antes de ordenar
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // imprime la lista ordenada de nuevo
    }
}

A pesar de los comentarios detallados en el código, proporcionamos una descripción de algunos de los métodos presentados en el programa. Los métodos clave que realizan el trabajo principal del programa están escritos en la clase ArrayBubble. La clase contiene un constructor y varios métodos:

• into– método de inserción de elementos en una matriz;
• printer– muestra el contenido de la matriz línea por línea;

• toSwap– reorganiza los elementos si es necesario. Para ello se utiliza una variable temporal dummyen la que se escribe el valor del primer número y en lugar del primer número se escribe el valor del segundo. Luego, el contenido de la variable temporal se escribe en el segundo número. Ésta es una técnica estándar para intercambiar dos elementos;

  y finalmente el método principal:

• bubbleSorter– que hace el trabajo principal y clasifica los datos almacenados en la matriz, lo presentaremos nuevamente por separado:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  // Bucle exterior
          for (int in = 0; in < out; in++){       //bucle interno
              if(a[in] > a[in + 1])               //Si el orden de los elementos es incorrecto
                  toSwap(in, in + 1);             // llamar al método de intercambio
          }
      }
  }

Aquí debes prestar atención a dos contadores: externo oute interno in. El contador externoout comienza a enumerar valores desde el final de la matriz y disminuye gradualmente en uno con cada nueva pasada. outCon cada nueva pasada, la variable se desplaza más hacia la izquierda para no afectar los valores ya ordenados en el lado derecho de la matriz. El contador internoin comienza a enumerar valores desde el principio de la matriz y aumenta gradualmente en uno en cada nueva pasada. El incremento inse produce hasta llegar a out(el último elemento analizado en el pase actual). El bucle interno incompara dos celdas adyacentes iny in+1. Si inse almacena un número mayor que in+1, entonces se llama al método toSwap, que intercambia los lugares de estos dos números.

Conclusión

El algoritmo de clasificación de burbujas es uno de los más lentos. Si la matriz consta de N elementos, entonces se realizarán N-1 comparaciones en la primera pasada, N-2 en la segunda, luego N-3, etc. Es decir, el número total de pasadas será: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 Así, al ordenar, el algoritmo realiza comparaciones de aproximadamente 0,5x(N ^2). Para N = 5, el número de comparaciones será aproximadamente 10, para N = 10 el número de comparaciones aumentará a 45. Por lo tanto, a medida que aumenta el número de elementos, la complejidad de la clasificación aumenta significativamente: La velocidad del algoritmo se ve afectada no solo por la cantidad de pasadas, sino también por la cantidad de permutaciones que deben realizarse. Para datos aleatorios, el número de permutaciones promedia (N^2) / 4, que es aproximadamente la mitad del número de pasadas. Sin embargo, en el peor de los casos, el número de permutaciones también puede ser N^2 / 2; este es el caso si los datos se ordenan inicialmente en orden inverso. A pesar de que se trata de un algoritmo de clasificación bastante lento, es muy importante conocer y comprender cómo funciona y, como se mencionó anteriormente, es la base para algoritmos más complejos. ¡Juguete!