Ordenamiento de burbuja
- Algoritmo de ordenamiento de burbuja
- Ejemplo de algoritmo de ordenación de burbujas
- Implementación del algoritmo de Ordenamiento de burbuja
- Complejidad del algoritmo de Ordenamiento de burbuja
La ordenamiento de burbuja es un algoritmo de ordenación simple. Funciona mediante la comparación repetida de elementos adyacentes y su intercambio si están en un orden incorrecto. Las comparaciones repetidas hacen que el elemento más pequeño/más grande se desplace hacia el final del array, por lo que este algoritmo recibe el nombre de ordenación burbuja. Aunque es ineficiente, sigue siendo la base de los algoritmos de ordenación.
Algoritmo de ordenamiento de burbuja
Supongamos que tenemos una array sin ordenar A[] que contiene n elementos.
-
Empezamos por el par de los dos primeros elementos (
A[0]yA[1]), comparamos sus valores y los intercambiamos si no están en el orden correcto. Haz lo mismo para el siguiente par (A[1]yA[2]) y muévete de forma similar para el resto de la array. El elemento más pequeño/más grande está en la última posición después de este paso. -
Repite los pasos anteriores
(n-2)veces para las iteraciones restantes. Reduzca el tamaño de la array en uno cada vez, ya que el último elemento ya está ordenado. El elemento más pequeño/más grande en esta iteración se mueve a la posición más a la derecha.
El paso 1 del algoritmo anterior también se denomina pase. Para ordenar un array de tamaño n, se necesitan n-1 pases.
Ejemplo de algoritmo de ordenación de burbujas
Supongamos que tenemos el array (5,3,4,2,1). Vamos a ordenarlo utilizando el algoritmo de ordenamiento de burbuja.
- Primer pase:
| (5 3 4 2 1) | → | (3 5 4 2 1) | (3 < 5 intercambiados) |
| (3 5 4 2 1) | → | (3 4 5 2 1) | (4 < 5 intercambiados) |
| (3 4 5 2 1) | → | (3 4 2 5 1) | (2 < 5 intercambiados) |
| (3 4 2 5 1) | → | (3 4 2 1 5) | (1 < 5 intercambiado) |
- Segundo pase:
| (3 4 2 1 5) | → | (3 4 2 1 5) | |
| (3 4 2 1 5) | → | (3 2 4 1 5) | (2 < 4 intercambiados) |
| (3 2 4 1 5) | → | (3 2 1 4 5) | (1 < 4 intercambiado) |
- Tercer pase:
| (3 2 1 4 5) | → | (2 3 1 4 5) | (2 < 3 intercambiado) |
| (2 3 1 4 5) | → | (2 1 3 4 5) | (1 < 3 intercambiado) |
- Cuarto pase:
| (2 1 3 4 5) | → | (1 2 3 4 5) | (1 < 2 intercambiado) |
Obtenemos el array ordenado después de la cuarta pasada - (1 2 3 4 5)
Implementación del algoritmo de Ordenamiento de burbuja
#include <iostream>
using namespace std;
void bubble_sort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
int n = 5;
int arr[5] = {5, 3, 4, 2, 1};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
bubble_sort(arr, n); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
Complejidad del algoritmo de Ordenamiento de burbuja
Complejidad de tiempo
- Caso medio
En promedio, se realizan n-i comparaciones en la i-ésimo pasada de la ordenamiento de burbuja. Por tanto, si hay n pases, la complejidad temporal media puede venir dada por
(n-1) + (n-2) + (n-3) ..... + 1 = n*(n-1)/2
Por tanto, la complejidad temporal es del orden de O(n2).
- El peor caso
El peor caso se da cuando el array está ordenado de forma inversa, y hay que realizar el máximo número de comparaciones e intercambios.
La complejidad temporal del peor caso es O(n2).
- El mejor caso
El mejor caso se da cuando la array ya está ordenada, y entonces sólo se necesitan N comparaciones.
La complejidad temporal del mejor caso es O(n).
Complejidad espacial
La complejidad espacial de este algoritmo es O(n) porque no se necesita más memoria que una variable temporal.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn