Clasificación de burbuja Java

Si alguna vez ha oído hablar de los métodos de clasificación en la programación, lo más probable es que haya sido el algoritmo de clasificación de burbujas. Es un famoso. Todos los programadores conocen la clasificación de burbujas (o al menos han oído hablar de ella mientras aprenden) no porque sea el mejor algoritmo de clasificación del mundo, sino porque es el más fácil. Este algoritmo generalmente se usa con fines de aprendizaje o puede obtenerlo como una tarea en su entrevista de Java Junior. El algoritmo de clasificación Java Bubble es muy fácil de entender, sin embargo, no es eficiente. De todos modos, averigüémoslo.

que es clasificar

En primer lugar, debe comprender qué es la clasificación en general y qué podemos clasificar en los programas Java. Si podemos comparar dos o más elementos u objetos por cualquiera de sus atributos, significa que se pueden ordenar por este atributo. Por ejemplo, números en orden ascendente o descendente o palabras alfabéticamente. Por lo tanto, los elementos deben ser comparables entre sí. Por cierto, ¿los elementos de qué? En Java, podemos comparar los elementos de Colecciones. Por ejemplo, podemos ordenar Array o ArrayList de enteros, cadenas, etc.

¿Cómo funciona la clasificación de burbujas?

Digamos que necesitamos ordenar una matriz de números enteros en orden ascendente, es decir, desde el número más pequeño hasta el más grande. Primero, recorremos toda la matriz y comparamos cada 2 elementos vecinos. Si están en el orden incorrecto (el vecino izquierdo es más grande que el derecho), los intercambiamos. En la primera pasada al final aparecerá el elemento de mayor tamaño (si ordenamos de forma ascendente). Puede decir, el elemento más grande "aparece". Esa es la razón del nombre del algoritmo de clasificación de burbujas. Repetimos el primer paso desde el primero hasta el penúltimo elemento. Tenemos el segundo elemento más grande en el penúltimo lugar. Etcétera. Podemos mejorar un poco un algoritmo verificando si se realizó al menos un intercambio en el paso anterior. Si no es así, dejamos de correr a lo largo de la matriz.

Ejemplo de clasificación de burbujas

Ordenemos la matriz de enteros, la que puede ver a continuación en una imagen. Paso 1: vamos a través de la matriz. El algoritmo comienza con los dos primeros elementos (con índices 0 y 1), 8 y 7, y verifica si están en el orden correcto. Obviamente, 8 > 7, así que los intercambiamos. A continuación, observamos el segundo y tercer elemento (índices 1 y 2), ahora estos son 8 y 1. Por las mismas razones, los intercambiamos. Por tercera vez comparamos 8 y 2 y, al menos, 8 y 5. Hicimos cuatro intercambios en total: (8, 7), (8, 1), (8, 2) y (8, 5). Un valor de 8, el mayor de esta matriz, apareció al final de la lista en la posición correcta. El resultado del primer paso del funcionamiento del algoritmo de clasificación de burbujas es la siguiente matriz: Paso 2. Hacer lo mismo con (7,1), (7,2) y (7,5). 7 ahora está en la penúltima posición, y no necesitamos compararlo con la "cola" de la lista, ya está ordenado. El resultado del segundo paso del funcionamiento del algoritmo de clasificación de burbujas es la siguiente matriz: como puede ver, esta matriz ya está ordenada. De todos modos, el algoritmo Bubble Sort debería ponerse en marcha al menos una vez más. Paso 3. Estamos repasando la matriz una vez más. No hay nada que intercambiar aquí, por lo que si estamos usando el algoritmo Bubble Sort "mejorado" (verificando si se realizó al menos un intercambio en el paso anterior), este paso es el último.

Código Java de tipo burbuja

Realización de Java tipo burbuja

Vamos a crear dos métodos para la ordenación de burbujas. El primero, bubbleSort(int[] myArray) es plano. Se ejecuta a través de la matriz cada vez. El segundo, optimizadoBubbleSort(int myArray[]) se optimiza al detener el algoritmo si el bucle interno no provocó ningún intercambio. El contador le muestra cuántos pasos hizo mientras ordenaba. Aquí tenemos la realización de Java tipo Bubble:

import java.util.Arrays;

public class BubbleSortExample {

   //  Plane Bubble sort example

   public static int[] bubbleSort(int[] myArray) {

       int temp = 0;  //  temporary element for swapping
       int counter = 0;  //  element to count quantity of steps

       for (int i = 0; i < myArray.length; i++) {
           counter = i + 1;
           for (int j = 1; j < (myArray.length - i); j++) {

               if (myArray[j - 1] > myArray[j]) {
                   //  swap array’s elements using temporary element
                   temp = myArray[j - 1];
                   myArray[j - 1] = myArray[j];
                   myArray[j] = temp;
               }
           }
       }
       System.out.println("Steps quantity, non optimized = " + counter);
       return myArray;
   }
   //  An optimized version of Java Bubble Sorting

   static int[] optimizedBubbleSort(int myArray[]) {
       int temp;
       boolean swapped;
       int counter = 0;  //  element to count quantity of steps
       for (int i = 0; i < myArray.length - 1; i++) {
           counter = i + 1;
           swapped = false;
           for (int j = 0; j < myArray.length - i - 1; j++) {
               //  counter++;
               if (myArray[j] > myArray[j + 1]) {
                   //  swap arr[j] and arr[j+1]
                   temp = myArray[j];
                   myArray[j] = myArray[j + 1];
                   myArray[j + 1] = temp;
                   swapped = true;

               }
           }  //  counter = i;
           //  If there weren't elements to swap in inner loop, then break
           if (swapped == false) {

               break;

           }
       }
       System.out.println("steps quantity, optimized = " + counter);
       return myArray;
   }


   public static void main(String[] args) {
       int arr[] = {8, 7, 1, 2, 5};
       int arr1[] = {8, 7, 1, 2, 5};

       System.out.println("Array arr Before Bubble Sort");
       //  we use java.util.Arrays toString method to print the array
 System.out.println(Arrays.toString(arr));

       System.out.println("Array arr After Bubble Sort");
       System.out.println(Arrays.toString(bubbleSort(arr)));

       System.out.println("Array arr1 Before Bubble Sort");
       System.out.println(Arrays.toString(arr1));

       System.out.println("Array arr1 After Optimized Bubble Sort");
       System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
   }
}

El resultado del trabajo del algoritmo Java de clasificación de burbujas:

Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]

¿Qué tan eficiente es la clasificación de burbujas?

Bubble sort es uno de los algoritmos más fáciles de implementar pero no es eficiente. Requiere un par de bucles anidados. Incluso en una versión optimizada del algoritmo, en el peor de los casos (cada elemento del conjunto de datos está en orden inverso al deseado), el ciclo externo itera una vez para cada uno de los n elementos del conjunto de datos. El bucle interno itera n veces la primera vez, ( n-1 ) la segunda, y así sucesivamente. Por lo tanto, para ordenar todos los n elementos, los bucles deben ejecutarse n*(n-1)/2 veces. Se llama O(n ² )complejidad de tiempo y significa que el algoritmo hace alrededor de 500 000 comparaciones para 1000 elementos de una matriz. Sin embargo, el algoritmo de ordenación de burbujas es bastante efectivo en el uso de la memoria (la complejidad de la memoria es O(n) ) y es realmente bueno para conjuntos de datos pequeños casi ordenados.