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. La clasificación de burbujas 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 algoritmo Bubble Sort, 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[], size)
// loop to access each array element
for i=0 to size-1 do:
// loop to compare array elements
for j=0 to size-i-1 do:
// compare the adjacent elements
if Arr[j] > Arr[j+1] then
// swap them
swap(Arr[j], Arr[j+1])
end if
end for
end for
end
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[], size)
// loop to access each array element
for i=0 to size-1 do:
// check if swapping occurs
swapped = false
// loop to compare array elements
for j=0 to size-i-1 do:
// compare the adjacent elements
if Arr[j] > Arr[j+1] then
// swap them
swap(Arr[j], Arr[j+1])
swapped = true
end if
end for
// if no elements were swapped that means the array is sorted now, then break the loop.
if(not swapped) then
break
end if
end for
end
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.
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:
// C++ implementation of the
// optimised Bubble Sort algorithm
#include <iostream>
using namespace std;
// Function to perform Bubble Sort
void bubbleSort(int arr[], int size) {
// Loop to access each element of the array
for (int i=0; i<(size-1); i++) {
// Variable to check if swapping occurs
bool swapped = false;
// loop to compare two adjacent elements of the array
for (int j = 0; j < (size-i-1); j++) {
// Comparing two adjacent array elements
if (arr[j] > arr[j + 1]) {
// Swap both elements if they're
// not in correct order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
// Prints the elements of the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Finding the length of the array
int size = sizeof(arr) / sizeof(arr[0]);
// Printing the given unsorted array
cout << "Unsorted Array: " << endl;
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
cout << "Sorted Array in Ascending Order:" << endl;
printArray(arr, size);
return 0;
}
Producción:
Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19Implementación en Python del algoritmo de clasificación de burbujas
A continuación se muestra la implementación de Python del algoritmo Bubble Sort:
# Python implementation of the
# optimised Bubble Sort algorithm
# Function to perform Bubble Sort
def bubbleSort(arr, size):
# Loop to access each element of the list
for i in range (size-1):
# Variable to check if swapping occurs
swapped = False
# loop to compare two adjacent elements of the list
for j in range(size-i-1):
# Comparing two adjacent list elements
if arr[j] > arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
swapped = True
# If no elements were swapped that means the list is sorted now,
# then break the loop.
if swapped == False:
break
# Prints the elements of the list
def printArray(arr):
for element in arr:
print(element, end=" ")
print("")
arr = [16, 12, 15, 13, 19]
# Finding the length of the list
size = len(arr)
# Printing the given unsorted list
print("Unsorted List:")
printArray(arr)
# Calling bubbleSort() function
bubbleSort(arr, size)
# Printing the sorted list
print("Sorted List in Ascending Order:")
printArray(arr)
Producción:
Unsorted List:
16 12 15 13 19
Sorted List in Ascending Order:
12 13 15 16 19
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 implementation of the
// optimised Bubble Sort algorithm
#include <stdio.h>
#include <stdbool.h>
// Function to perform Bubble Sort
void bubbleSort(int arr[], int size) {
// Loop to access each element of the array
for (int i=0; i<(size-1); i++) {
// Variable to check if swapping occurs
bool swapped = false;
// loop to compare two adjacent elements of the array
for (int j = 0; j < (size-i-1); j++) {
// Comparing two adjacent array elements
if (arr[j] > arr[j + 1]) {
// Swap both elements if they're
// not in correct order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
// Prints the elements of the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf(" n ");
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Finding the length of the array
int size = sizeof(arr) / sizeof(arr[0]);
// Printing the given unsorted array
printf("Unsorted Array: n");
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
printf("Sorted Array in Ascending Order: n");
printArray(arr, size);
return 0;
}Producción:
Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19Implementación de JavaScript del algoritmo de clasificación de burbujas
A continuación se muestra la implementación de JavaScript del algoritmo Bubble Sort:
// JavaScript implementation of the
// optimised Bubble Sort algorithm
// Function to perform Bubble Sort
function bubbleSort(arr, size) {
// Loop to access each element of the array
for(let i=0; i<size-1; i++) {
// Variable to check if swapping occurs
var swapped = false;
// loop to compare two adjacent elements of the array
for(let j=0; j<size-i-1; j++) {
// Comparing two adjacent array elements
if(arr[j] > arr[j+1]) {
// Swap both elements if they're
// not in correct order
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = true;
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
}
// Prints the elements of the array
function printArray(arr, size) {
for (let i=0; i<size; i++) {
document.write(arr[i] + " ");
}
document.write("<br>")
}
var arr = [16, 12, 15, 13, 19];
// Finding the length of the array
var size = arr.length;
// Printing the given unsorted array
document.write("Unsorted Array: <br>");
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
document.write("Sorted Array in Ascending Order: <br>");
printArray(arr, size);
Producción:
Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 15 13 16 19Ahora 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.
