En este tutorial, aprenderá cómo funciona la clasificación de burbujas. Además, encontrará ejemplos prácticos de clasificación de burbujas en C, C ++, Java y Python.
La clasificación de burbujas es un algoritmo que compara los elementos adyacentes e intercambia sus posiciones si no están en el orden previsto. El orden puede ser ascendente o descendente.
¿Cómo funciona Bubble Sort?
- A partir del primer índice, compare el primer y el segundo elemento, si el primer elemento es mayor que el segundo, se intercambian.
Ahora, compare el segundo y el tercer elemento. Cámbielos si no están en orden.
El proceso anterior continúa hasta el último elemento.
Compare los elementos adyacentes - El mismo proceso continúa para las iteraciones restantes. Después de cada iteración, el elemento más grande entre los elementos no clasificados se coloca al final.
En cada iteración, la comparación se realiza hasta el último elemento sin clasificar.
La matriz se ordena cuando todos los elementos sin clasificar se colocan en sus posiciones correctas.
Compare los elementos adyacentes 
Compare los elementos adyacentes 
Compare los elementos adyacentes
Algoritmo de clasificación de burbujas
bubbleSort (matriz) para i rightElement swap leftElement y rightElement end bubbleSort
Ejemplos de Python, Java y C / C ++
Python Java C C ++ # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)
// Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )
// Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Clasificación de burbujas optimizada
En el código anterior, todas las comparaciones posibles se realizan incluso si la matriz ya está ordenada. Aumenta el tiempo de ejecución.
El código se puede optimizar introduciendo una variable adicional intercambiada. Después de cada iteración, si no se realiza ningún intercambio, no es necesario realizar más bucles.
En tal caso, la variable swapped se establece como falsa. Por lo tanto, podemos evitar más iteraciones.
El algoritmo para la clasificación de burbujas optimizada es
bubbleSort (matriz) swapped <- falso para i rightElement swap leftElement y rightElement intercambiado <- true end bubbleSort
Ejemplos de clasificación de burbujas optimizada
Python Java C C + # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)
// Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )
// Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (
// Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Complejidad
Bubble Sort es uno de los algoritmos de clasificación más simples. Se implementan dos bucles en el algoritmo.
| Ciclo | Numero de comparaciones |
|---|---|
| Primero | (n-1) |
| 2do | (n-2) |
| Tercero | (n-3) |
| …. | … |
| último | 1 |
Número de comparaciones: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 casi igual an 2
Complejidad: O (n 2 )
Además, podemos analizar la complejidad simplemente observando el número de bucles. Hay 2 bucles, por lo que la complejidad esn*n = n2
Complejidades de tiempo:
-
Complejidad del peor de los casos: si queremos clasificar en orden ascendente y la matriz está en orden descendente, entonces ocurre el peor de los casos.
O(n2) -
Mejor complejidad de caso:
O(n)
si la matriz ya está ordenada, entonces no hay necesidad de ordenar. -
Complejidad de casos promedio: ocurre cuando los elementos de la matriz están en orden desordenado (ni ascendente ni descendente).
O(n2)
Complejidad espacial:
la complejidad espacial se O(1)debe a que se utiliza una temperatura variable adicional para el intercambio.
En el algoritmo optimizado, la variable intercambiada se suma a la complejidad del espacio, lo que lo hace O(2).
Aplicaciones de clasificación de burbujas
La clasificación de burbujas se utiliza en los siguientes casos en los que
- la complejidad del código no importa.
- se prefiere un código corto.
