Algoritmo de clasificación de burbujas: iterativo y recursivo | C, Java, Python
Dada una array de enteros, ordénela usando el algoritmo de clasificación de burbujas.
Descripción general de la clasificación de burbujas
Bubble sort es un establo, algoritmo de ordenación en el lugar nombrados por elementos más pequeños o más grandes, "burbujean" en la parte superior de la lista. Aunque el algoritmo es simple, es demasiado lento y poco práctico para la mayoría de los problemas, incluso en comparación con tipo de insercióny no se recomienda para entradas grandes.
La única ventaja significativa que tiene el tipo de burbujas sobre la mayoría de las otras implementaciones, incluso Ordenación rápida, pero no la ordenación por inserción, es la capacidad de detectar si la lista ya está ordenada. Cuando la lista ya está ordenada (en el mejor de los casos), la clasificación por burbujas se ejecuta en tiempo lineal.
¿Cómo funciona Bubble Sort?
Cada pasada de clasificación de burbujas recorre la lista que se va a clasificar, compara cada par de elementos adyacentes y los intercambia si están en el orden incorrecto. Al final de cada pasada, el siguiente elemento más grande "burbujeará" hasta su posición correcta. Estos pases a través de la lista se repiten hasta que no se necesitan intercambios, lo que indica que la lista está ordenada. En el peor de los casos, podríamos terminar haciendo una n-1 pasar, donde n es el tamaño de entrada.
3 5 8 4 1 9 -2
pass 1 3 5 4 1 8 -2 9
pass 2 3 4 1 5 -2 8 9
pass 3 3 1 4 -2 5 8 9
pass 4 1 3 -2 4 5 8 9
pass 5 1 -2 3 4 5 8 9
pass 6 -2 1 3 4 5 8 9
Se puede ver una ilustración detallada de cómo funciona cada pase. aquí.
Implementación de clasificación por inserción
A continuación se muestra una implementación iterativa del algoritmo de clasificación de burbujas en C, Java y Python. La implementación se puede optimizar fácilmente observando que el n'th pasar encuentra el n'th elemento más grande y lo coloca en su lugar final. Entonces, el bucle interno puede evitar mirar el último n-1 elementos cuando se ejecuta para el n'th tiempo. Otra optimización es detener el algoritmo cuando el ciclo interno no hizo ningún intercambio.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <stdio.h> // Función de utilidad para intercambiar valores en dos índices en una array void swap(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Función para imprimir `n` elementos de la array `arr` void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } // Función para realizar la ordenación de burbujas en una array dada `arr[]` void bubbleSort(int arr[], int n) { // `n-1` pasa for (int k = 0; k < n - 1; k++) { // los últimos elementos `k` ya están ordenados, por lo que el ciclo interno puede // evita mirar los últimos elementos `k` for (int i = 0; i < n - 1 - k; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } // el algoritmo se puede terminar si el ciclo interno no hizo ningún intercambio } } int main(void) { int arr[] = { 3, 5, 8, 4, 1, 9, -2 }; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); printArray(arr, n); return 0; } |
Resultado:
-2 1 3 4 5 8 9
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
import java.util.Arrays; class Main { // Función de utilidad para intercambiar valores en dos índices en la array public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Función para realizar la ordenación de burbujas en una array dada `arr[]` public static void bubbleSort(int[] arr) { // `n-1` pasa donde `n` es la longitud de la array for (int k = 0; k < arr.length - 1; k++) { // los últimos elementos `k` ya están ordenados, por lo que el ciclo interno puede // evita mirar los últimos elementos `k` for (int i = 0; i < arr.length - 1 - k; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } // el algoritmo se puede terminar si el ciclo interno // no hizo ningún intercambio } } public static void main(String[] args) { int[] arr = { 3, 5, 8, 4, 1, 9, -2 }; bubbleSort(arr); // imprime la array ordenada System.out.println(Arrays.toString(arr)); } } |
Resultado:
[-2, 1, 3, 4, 5, 8, 9]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
# Función de utilidad para intercambiar valores en dos índices de la lista def swap(A, i, j): temp = A[i] A[i] = A[j] A[j] = temp # Función # para realizar la ordenación de burbujas en una lista def bubbleSort(A): # `len(A)-1` pasa for k in range(len(A) - 1): # Los últimos elementos `k` ya están ordenados, por lo que el ciclo interno puede # evita mirar los últimos elementos `k` for i in range(len(A) - 1 - k): if A[i] > A[i + 1]: swap(A, i, i + 1) #, el algoritmo se puede terminar si el bucle interno no hizo ningún intercambio if __name__ == '__main__': A = [3, 5, 8, 4, 1, 9, -2] bubbleSort(A) # imprime la lista ordenada print(A) |
Resultado:
[-2, 1, 3, 4, 5, 8, 9]
El algoritmo de clasificación de burbujas también se puede implementar de forma recursivamente. A continuación se muestra la implementación recursivamente del algoritmo de clasificación de burbujas en C, Java y Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <stdio.h> // Función de utilidad para intercambiar valores en dos índices en una array void swap(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Función para imprimir `n` elementos de la array `arr` void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } // Función recursivo para realizar la ordenación de burbujas en el subarray `arr[i…n]` void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } if (n - 1 > 1) { bubbleSort(arr, n - 1); } } int main(void) { int arr[] = { 3, 5, 8, 4, 1, 9, -2 }; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); printArray(arr, n); return 0; } |
Resultado:
-2 1 3 4 5 8 9
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import java.util.Arrays; class Main { // Función de utilidad para intercambiar valores en dos índices en la array public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Función recursivo para realizar la ordenación de burbujas en el subarray `arr[i…n]` public static void bubbleSort(int[] arr, int n) { for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } if (n - 1 > 1) { bubbleSort(arr, n - 1); } } public static void main(String[] args) { int[] arr = { 3, 5, 8, 4, 1, 9, -2 }; bubbleSort(arr, arr.length); // imprime la array ordenada System.out.println(Arrays.toString(arr)); } } |
Resultado:
[-2, 1, 3, 4, 5, 8, 9]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
# Función de utilidad para intercambiar valores en dos índices de la lista def swap(A, i, j): temp = A[i] A[i] = A[j] A[j] = temp # Función recursivo para realizar clasificación de burbujas en la sublista `A[i…n]` def bubbleSort(A, n): for i in range(n - 1): if A[i] > A[i + 1]: swap(A, i, i + 1) if n - 1 > 1: bubbleSort(A, n - 1) if __name__ == '__main__': A = [ 3, 5, 8, 4, 1, 9, -2 ] bubbleSort(A, len(A)) # imprime la lista ordenada print(A) |
Resultado:
[-2, 1, 3, 4, 5, 8, 9]
Rendimiento de clasificación por inserción
La complejidad de tiempo en el peor de los casos del tipo de burbuja es O(n2), dónde n es el tamaño de la entrada. El peor de los casos ocurre cuando la array se ordena de forma inversa. En el mejor de los casos, la complejidad temporal del tipo de burbuja es O(n). El mejor de los casos ocurre cuando la array ya está ordenada y el algoritmo se modifica para dejar de ejecutarse cuando el ciclo interno no realizó ningún intercambio. La implementación optimizada se puede ver aquí.
El espacio auxiliar utilizado por la versión iterativa es O(1) y O(n) por la versión recursivo para la pila de llamadas.
Referencias: https://en.wikipedia.org/wiki/Bubble_sort
Algoritmo de clasificación de selección: iterativo y recursivo | C, Java, Python
Algoritmo de clasificación por inserción: iterativo y recursivo | C, Java, Python