Bubble Algoritmo de clasificación en Java: Ejemplo y programa de clasificación de matrices
james hartman
⚡ Resumen inteligente
Bubble Algoritmo de clasificación en Java Compara repetidamente elementos adyacentes de un array y los intercambia hasta que la secuencia esté ordenada. Este artículo explica el mecanismo de funcionamiento, el pseudocódigo y el funcionamiento completo. Java Implementación, variante optimizada, análisis de complejidad y comparaciones prácticas con otras técnicas de ordenación.
¿Qué es Bubbl¿Clasificar?
BubblEl algoritmo eSort es un algoritmo de ordenación sencillo basado en comparaciones que compara el primer elemento del array con el siguiente. Si el elemento actual es numéricamente mayor que el siguiente, se intercambian. Asimismo, el algoritmo recorre todos los elementos del array.
El algoritmo toma su nombre de la forma en que el valor más grande en la región sin ordenar asciende gradualmente hasta su posición final, como una burbuja que sube a la superficie del agua. Tras la primera pasada completa, el elemento más grande ocupa el último índice. Después de la segunda pasada, el segundo elemento más grande queda fijado en su lugar, y el proceso se repite hasta que el arreglo esté completamente ordenado.
En este artículo, crearemos un Java programa para implementar Bubble Ordenar. Compruebe el resultado del código que le ayudará a comprender la lógica del programa y, a continuación, revise la versión optimizada y el análisis de complejidad que se presentan a continuación.
Cómo hace el Bubbl¿Funciona el algoritmo de ordenación?
Bubble Sort funciona mediante pasadas repetidas sobre el array. Cada pasada va desde el primer índice hasta el final de la región actualmente sin ordenar, comparando valores vecinos e intercambiando.ping siempre que aparezcan en el orden incorrecto. Debido a que el valor restante más grande siempre se desplaza al extremo derecho de la región no ordenada, la región se reduce exactamente una posición después de cada pasada.
El proceso completo se puede dividir en cuatro pasos repetibles:
- Comparar: Examine el elemento en el índice j-1 con respecto al elemento en el índice j.
- Intercambio: Si el elemento de la izquierda es mayor que el de la derecha, intercambie los dos valores utilizando una variable temporal.
- Avanzar: Muévase una posición a la derecha y repita el proceso hasta llegar al final de la región sin ordenar.
- Repetición: Inicie una nueva pasada sobre una región que sea un elemento más corta y deténgase después de n-1 pasadas o cuando una pasada no realice ningún intercambio.
La mesa de abajo traces el array de ejemplo {860, 8, 200, 9} que se utiliza en el programa más adelante en esta página. Muestra exactamente qué valor se sitúa en su posición final al final de cada iteración.
| Pasó | Matriz al inicio del paso | Comparaciones realizadas | Matriz al final de la pasada | Elemento bloqueado |
|---|---|---|---|---|
| 1 | 860, 8, 200, 9 | 3 | 8, 200, 9, 860 | 860 |
| 2 | 8, 200, 9, 860 | 2 | 8, 9, 200, 860 | 200 |
| 3 | 8, 9, 200, 860 | 1 | 8, 9, 200, 860 | 9 |
| 4 | 8, 9, 200, 860 | 0 | 8, 9, 200, 860 | 8 |
Observe que en la tercera pasada se realiza una comparación, pero no un intercambio. Una implementación optimizada detecta esta condición y se detiene inmediatamente, lo cual constituye la mejora más valiosa que se puede aplicar a este algoritmo.
BubblPseudocódigo del algoritmo de ordenación
Antes de escribir Java La sintaxis ayuda a expresar la lógica en pseudocódigo independiente del lenguaje. La versión que se muestra a continuación incluye la bandera de salida anticipada, por lo que abarca tanto el comportamiento clásico como el optimizado.
procedure bubbleSort(array A, integer n) for i from 0 to n - 2 do swapped := false for j from 1 to n - i - 1 do // compare the adjacent pair if A[j - 1] > A[j] then swap A[j - 1] and A[j] swapped := true end if end for // no swap in a full pass means the array is sorted if swapped = false then break end if end for end procedure
El bucle externo controla el número de pasadas, y el bucle interno controla las comparaciones dentro de una sola pasada. El límite superior del bucle interno es n – i – 1 porque las últimas i posiciones ya contienen sus valores finales.
Java Programa para implementar Bubble Ordenar
El siguiente programa ordena un array de enteros en orden ascendente. Se han mantenido instrucciones de impresión adicionales dentro de los bucles a propósito, porque leer el paso a paso... trace es la forma más rápida para que un principiante entienda cómo se acumulan los swaps.
package com.guru99; public class BubbleSort { public static void main(String[] args) { int arr[] = {860, 8, 200, 9}; System.out.println("---Array BEFORE Bubble Sort---"); printArray(arr); bubbleSort(arr); //sorting array elements using bubble sort System.out.println("---Array AFTER Bubble Sort---"); printArray(arr); } static void bubbleSort(int[] array) { int n = array.length; int temp = 0; for(int i = 0; i < n; i++) // Looping through the array length { System.out.println("Sort Pass Number " + (i + 1)); for(int j = 1; j < (n - i); j++) { System.out.println("Comparing " + array[j - 1] + " and " + array[j]); if(array[j - 1] > array[j]) { //swap elements temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; System.out.println(array[j] + " is greater than " + array[j - 1]); System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } } } static void printArray(int[] array){ for(int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Salida:
---Array BEFORE Bubble Sort--- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Swapping Elements: New Array After Swap 8 860 200 9 Comparing 860 and 200 860 is greater than 200 Swapping Elements: New Array After Swap 8 200 860 9 Comparing 860 and 9 860 is greater than 9 Swapping Elements: New Array After Swap 8 200 9 860 Sort Pass Number 2 Comparing 8 and 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 8 and 9 Sort Pass Number 4 ---Array AFTER Bubble Sort--- 8 9 200 860
Code explicación: El Ordenar burbujas El método recibe el array por referencia, por lo que quien lo llama ve el resultado ordenado sin ningún valor de retorno. La variable temp mantiene un valor durante el intercambio de tres líneas, razón por la cual el algoritmo solo necesita O(1) de memoria adicional. La expresión n – i En el bucle interno, la condición garantiza que las posiciones ya ordenadas al final nunca se vuelvan a visitar.
Optimizado Bubble Ordenar programa en Java
El programa anterior siempre realiza n-1 pasadas, incluso cuando el array se ordena prematuramente. Añadir un simple indicador booleano soluciona esta ineficiencia. Si una pasada completa finaliza sin ningún intercambio, se garantiza que el array esté ordenado y el bucle externo puede detenerse inmediatamente.
package com.guru99; public class OptimizedBubbleSort { public static void main(String[] args) { int arr[] = {5, 12, 33, 47, 58}; bubbleSort(arr); System.out.println(java.util.Arrays.toString(arr)); } static void bubbleSort(int[] array) { int n = array.length; int passes = 0; for (int i = 0; i < n - 1; i++) { boolean swapped = false; for (int j = 1; j < n - i; j++) { if (array[j - 1] > array[j]) { int temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; swapped = true; } } passes++; // Early exit: the array is already sorted if (!swapped) { break; } } System.out.println("Passes executed: " + passes); } }
Salida:
Passes executed: 1 [5, 12, 33, 47, 58]
El array de entrada ya estaba ordenado, por lo que la versión optimizada terminó después de una sola pasada en lugar de cuatro. En datos casi ordenados, este cambio convierte una carga de trabajo cuadrática en una casi lineal, que es la razón principal. BubblLa instrucción `e Sort` todavía aparece en código real de vez en cuando.
Complejidad temporal y complejidad espacial de Bubble Ordenar
La complejidad describe cómo aumenta el tiempo de ejecución a medida que aumenta el tamaño de la entrada. Para Bubble Ordenar el recuento de comparaciones en la versión no optimizada está fijado en n(n-1)/2, lo que lo sitúa firmemente en la clase cuadrática.
| Escenario | Condición de entrada | Complejidad de tiempo | Complejidad espacial |
|---|---|---|---|
| Mejores casos | Matriz ya ordenada, versión optimizada | O (n) | O (1) |
| Caso medio | Elementos en orden aleatorio | O (n²) | O (1) |
| Peor de los casos | Matriz ordenada en orden inverso | O (n²) | O (1) |
Debido a que cada intercambio ocurre dentro del arreglo original y solo se utiliza una variable temporal, Bubble Sort es un algoritmo in situ con un espacio auxiliar de O(1). Además, es un algoritmo de ordenación estable, lo que significa que dos registros que contienen la misma clave conservan su orden relativo original después de la ordenación.
Ventajas y desventajas de la Bubble Ordenar
Comprender ambas perspectivas te ayuda a decidir cuándo el algoritmo es una opción aceptable y cuándo debe ser reemplazado.
Ventajas
- Sencillez: La lógica se resume en unas diez líneas, lo que facilita redactarla correctamente en situaciones de entrevista.
- Operación in situ: No se asigna ninguna matriz auxiliar, por lo que el uso de memoria no aumenta con el tamaño de la entrada.
- Estabilidad: Las claves iguales conservan su orden original, lo cual es importante al ordenar registros por un campo secundario.
- Detección de salida temprana: El indicador de intercambio identifica una matriz ya ordenada en una sola pasada.
Desventajas
- Crecimiento cuadrático: En el peor de los casos, ordenar 10,000 elementos requiere casi 50 millones de comparaciones.
- Escritura excesiva: El algoritmo realiza muchos más intercambios que el algoritmo de ordenación por selección, que consume mucha memoria debido a las lentas operaciones de escritura.
- Mala escalabilidad: Las cargas de trabajo de producción casi siempre favorecen Quicksort, Merge Sort o el método integrado Arrays.sort.
💡 Consejo: En producción Java código, prefiero Arrays.sort () para primitivos y Colecciones.ordenar() para listas. Ambos utilizan algoritmos altamente optimizados, Dual-Pivot Quicksort y TimSort respectivamente, que superan a un algoritmo escrito a mano. Bubble Ordenar por órdenes de magnitud.
Bubble Sort frente a otros métodos de ordenación Algorithms
La siguiente tabla compara Bubble Clasifica con las técnicas de clasificación que los principiantes encontrarán a continuación, para que puedas ver exactamente dónde gana cada una.
| Algoritmo | Mejores casos | Caso promedio | Peor de los casos | Espacio | Estable |
|---|---|---|---|---|---|
| Bubble Ordenar | O (n) | O (n²) | O (n²) | O (1) | Sí: |
| Selección Ordenar | O (n²) | O (n²) | O (n²) | O (1) | No |
| Tipo de inserción | O (n) | O (n²) | O (n²) | O (1) | Sí: |
| Ordenación rápida | O (n log n) | O (n log n) | O (n²) | O (log n) | No |
| Ordenar montón | O (n log n) | O (n log n) | O (n log n) | O (1) | No |
BubblEl algoritmo de ordenación por inserción y el algoritmo de ordenación por inserción comparten el mismo caso óptimo lineal, pero el algoritmo de ordenación por inserción realiza menos intercambios en datos parcialmente ordenados. El algoritmo de ordenación por selección siempre realiza exactamente n-1 intercambios, lo que lo convierte entracEs eficaz cuando las escrituras son costosas, aunque sacrifica la estabilidad. Para cualquier matriz de más de unos pocos cientos de elementos, Quicksort o Heap Sort son la opción correcta.
Una vez que se sienta cómodo con los patrones de recorrido de matrices utilizados aquí, la misma estructura de bucle aparece en muchos ejercicios clásicos como el Serie de Fibonacci en Java y conectar Java programa de palíndromos. Revviendo Java arrays y el más ancho Java tutoriales reforzará los fundamentos en los que se basa este algoritmo.
