Introducción al algoritmo de clasificación de burbujas

La clasificación es una de las operaciones más básicas que puede aplicar a los datos. Puede ordenar elementos en diferentes lenguajes de programación utilizando varios algoritmos de clasificación como Clasificación rápida, Clasificación de burbujas, Clasificación de combinación, Clasificación de inserción, etc. Bubble Sort es el algoritmo más simple entre todos estos.

En este artículo, aprenderá sobre el funcionamiento del algoritmo Bubble Sort, el pseudocódigo del Bubble Sort. algoritmo, su complejidad temporal y espacial, y su implementación en varios lenguajes de programación como C ++, Python, C y JavaScript.

¿Cómo funciona el algoritmo de clasificación de burbujas?

Bubble Sort es el algoritmo de clasificación más simple que recorre repetidamente la lista, compara elementos adyacentes y los intercambia si están en el orden incorrecto. Este concepto se puede explicar de manera más eficiente con la ayuda de un ejemplo. Considere una matriz sin clasificar con los siguientes elementos: {16, 12, 15, 13, 19}.

Ejemplo:

Aquí se comparan los elementos adyacentes y si no están en orden ascendente, se intercambian.

Pseudocódigo del algoritmo de clasificación de burbujas

En pseudocódigo, el algoritmo de clasificación de burbujas se puede expresar como:

bubbleSort (Arr [], tamaño)
// bucle para acceder a cada elemento de la matriz
para i = 0 a tamaño-1 hacer:
// bucle para comparar elementos de la matriz
para j = 0 a tamaño-i-1 hacer:
// compara los elementos adyacentes
si Arr [j]> Arr [j + 1] entonces
// intercambiarlos
intercambio (Arr [j], Arr [j + 1])
terminara si
final para
final para
final

El algoritmo anterior procesa todas las comparaciones incluso si la matriz ya está ordenada. Se puede optimizar aún más deteniendo el algoritmo si el bucle interno no provocó ningún cambio. Esto reducirá el tiempo de ejecución del algoritmo.

Por lo tanto, el pseudocódigo del algoritmo de clasificación de burbujas optimizado se puede expresar como:

bubbleSort (Arr [], tamaño)
// bucle para acceder a cada elemento de la matriz
para i = 0 a tamaño-1 hacer:
// comprobar si se produce un intercambio
intercambiado = falso
// bucle para comparar elementos de la matriz
para j = 0 a tamaño-i-1 hacer:
// compara los elementos adyacentes
si Arr [j]> Arr [j + 1] entonces
// intercambiarlos
intercambio (Arr [j], Arr [j + 1])
intercambiado = verdadero
terminara si
final para
// si no se intercambiaron elementos, eso significa que la matriz está ordenada ahora, rompa el ciclo.
si (no intercambiado) entonces
rotura
terminara si
final para
final

Complejidad temporal y espacio auxiliar del algoritmo de clasificación de burbujas

La complejidad de tiempo del peor caso del algoritmo de clasificación de burbujas es O (n ^ 2). Ocurre cuando la matriz está en orden descendente y desea ordenarla en orden ascendente o viceversa.

La complejidad de tiempo en el mejor de los casos del algoritmo de clasificación de burbujas es O (n). Ocurre cuando la matriz ya está ordenada.

Relacionados: ¿Qué es la notación Big-O?

La complejidad de tiempo de caso promedio del algoritmo de clasificación de burbujas es O (n ^ 2). Ocurre cuando los elementos de la matriz están en orden desordenado.

El espacio auxiliar necesario para el algoritmo de clasificación de burbujas es O (1).

Implementación en C ++ del algoritmo de clasificación de burbujas

A continuación se muestra la implementación en C ++ del algoritmo Bubble Sort:

// Implementación en C ++ del
// algoritmo optimizado de clasificación de burbujas
#incluir 
usando el espacio de nombres std;
// Función para realizar Bubble Sort
void bubbleSort (int arr [], int size) {
// Bucle para acceder a cada elemento de la matriz
para (int i = 0; i // Variable para comprobar si se produce un intercambio
bool swapped = falso;
// bucle para comparar dos elementos adyacentes de la matriz
para (int j = 0; j // Comparación de dos elementos de matriz adyacentes
si (arr [j]> arr [j + 1]) {
// Intercambia ambos elementos si están
// no en el orden correcto
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
intercambiado = verdadero;
}
}
// Si no se intercambiaron elementos, eso significa que la matriz está ordenada ahora,
// luego rompe el bucle.
si (intercambiado == falso) {
rotura;
}
}
}
// Imprime los elementos de la matriz
void printArray (int arr [], int size) {
para (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Encontrar la longitud de la matriz
int tamaño = tamaño de (arr) / tamaño de (arr [0]);
// Imprimiendo la matriz sin clasificar dada
cout << "Matriz sin clasificar:" << endl;
printArray (arr, tamaño);
// Llamando a la función bubbleSort ()
bubbleSort (arr, tamaño);
// Imprimiendo la matriz ordenada
cout << "Matriz ordenada en orden ascendente:" << endl;
printArray (arr, tamaño);
return 0;
}

Producción:

Matriz sin clasificar: 
16 12 15 13 19 
Matriz ordenada en orden ascendente:
12 13 15 16 19

Implementación en Python del algoritmo de clasificación de burbujas

A continuación se muestra la implementación de Python del algoritmo de clasificación de burbujas:

# Implementación en Python del
# algoritmo optimizado de clasificación de burbujas
# Función para realizar Bubble Sort
def bubbleSort (arr, tamaño):
# Bucle para acceder a cada elemento de la lista
para i en el rango (tamaño-1):
# Variable para comprobar si se produce un intercambio
swapped = Falso
# bucle para comparar dos elementos adyacentes de la lista
para j en rango (tamaño-i-1):
# Comparación de dos elementos de lista adyacentes
si arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
swapped = Verdadero
# Si no se intercambiaron elementos, eso significa que la lista está ordenada ahora,
# luego rompa el bucle.
si se intercambia == Falso:
rotura
# Imprime los elementos de la lista
def printArray (arr):
para el elemento en arr:
imprimir (elemento, fin = "")
impresión("")
arr = [16, 12, 15, 13, 19]
# Encontrar la longitud de la lista
tamaño = len (arr)
# Imprimiendo la lista desordenada dada
print ("Lista sin clasificar:")
printArray (arr)
# Llamando a la función bubbleSort ()
bubbleSort (arr, tamaño)
# Imprimir la lista ordenada
imprimir ("Lista ordenada en orden ascendente:")
printArray (arr)

Producción:

Lista sin clasificar:
16 12 15 13 19 
Lista ordenada en orden ascendente:
12 13 15 16 19

Relacionados: Cómo usar bucles for en Python

C Implementación del algoritmo de clasificación de burbujas

A continuación se muestra la implementación en C del algoritmo de clasificación de burbujas:

// C implementación de la
// algoritmo optimizado de clasificación de burbujas
#incluir 
#incluir 
// Función para realizar Bubble Sort
void bubbleSort (int arr [], int size) {
// Bucle para acceder a cada elemento de la matriz
para (int i = 0; i // Variable para comprobar si se produce un intercambio
bool swapped = falso;
// bucle para comparar dos elementos adyacentes de la matriz
para (int j = 0; j // Comparación de dos elementos de matriz adyacentes
si (arr [j]> arr [j + 1]) {
// Intercambia ambos elementos si están
// no en el orden correcto
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
intercambiado = verdadero;
}
}
// Si no se intercambiaron elementos, eso significa que la matriz está ordenada ahora,
// luego rompe el bucle.
si (intercambiado == falso) {
rotura;
}
}
}
// Imprime los elementos de la matriz
void printArray (int arr [], int size) {
para (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Encontrar la longitud de la matriz
int tamaño = tamaño de (arr) / tamaño de (arr [0]);
// Imprimiendo la matriz sin clasificar dada
printf ("Matriz sin clasificar: \ ⁠n");
printArray (arr, tamaño);
// Llamando a la función bubbleSort ()
bubbleSort (arr, tamaño);
// Imprimiendo la matriz ordenada
printf ("Matriz ordenada en orden ascendente: \ ⁠n");
printArray (arr, tamaño);
return 0;
}

Producción:

Matriz sin clasificar: 
16 12 15 13 19 
Matriz ordenada en orden ascendente: 
12 13 15 16 19

Implementación de JavaScript del algoritmo de clasificación de burbujas

A continuación se muestra la implementación de JavaScript del algoritmo de clasificación de burbujas:

// Implementación JavaScript del
// algoritmo optimizado de clasificación de burbujas
// Función para realizar Bubble Sort
function bubbleSort (arr, size) {
// Bucle para acceder a cada elemento de la matriz
para (sea i = 0; I// Variable para comprobar si se produce un intercambio
var swapped = false;
// bucle para comparar dos elementos adyacentes de la matriz
para (sea j = 0; j// Comparación de dos elementos de matriz adyacentes
si (arr [j]> arr [j + 1]) {
// Intercambia ambos elementos si están
// no en el orden correcto
sea ​​temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
intercambiado = verdadero;
}
// Si no se intercambiaron elementos, eso significa que la matriz está ordenada ahora,
// luego rompe el bucle.
si (intercambiado == falso) {
rotura;
}
}
}
}
// Imprime los elementos de la matriz
function printArray (arr, size) {
para (sea i = 0; Idocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Encontrar la longitud de la matriz
var tamaño = longitud de arr.;
// Imprimiendo la matriz sin clasificar dada
document.write ("Matriz sin clasificar: 
");
printArray (arr, tamaño);
// Llamando a la función bubbleSort ()
bubbleSort (arr, tamaño);
// Imprimiendo la matriz ordenada
document.write ("Matriz ordenada en orden ascendente: 
");
printArray (arr, tamaño);

Producción:

Matriz sin clasificar:
16 12 15 13 19
Matriz ordenada en orden ascendente:
12 15 13 16 19

Ahora comprende el funcionamiento del algoritmo de clasificación de burbujas

Bubble Sort es el algoritmo de clasificación más simple y se utiliza principalmente para comprender los fundamentos de la clasificación. Bubble Sort también se puede implementar de forma recursiva, pero no ofrece ventajas adicionales para hacerlo.

Con Python, puede implementar el algoritmo Bubble Sort con facilidad. Si no está familiarizado con Python y desea iniciar su viaje, comenzar con un script "Hola mundo" es una excelente opción.

Cómo empezar a utilizar Python mediante un script "Hello World"

Python es uno de los lenguajes de programación más populares en uso en la actualidad. Siga este tutorial para comenzar con su primer script de Python.

Leer siguiente

Sobre el Autor