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. 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.

Relacionado: ¿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:

 // 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 19

Implementació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

Relacionado: 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 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 19

Implementació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 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.