Uma introdução ao algoritmo de classificação de bolhas
A classificação é uma das operações mais básicas que você pode aplicar aos dados. Você pode classificar os elementos em diferentes linguagens de programação usando vários algoritmos de classificação como Quick Sort, Bubble Sort, Merge Sort, Insertion Sort, etc. Bubble Sort é o algoritmo mais simples entre todos eles.
Neste artigo, você aprenderá sobre o funcionamento do algoritmo Bubble Sort, o pseudocódigo do algoritmo Bubble Sort, sua complexidade de tempo e espaço e sua implementação em várias linguagens de programação como C ++, Python, C e JavaScript.
Como funciona o algoritmo de classificação de bolhas?
Bubble Sort é o algoritmo de classificação mais simples que percorre repetidamente a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. Este conceito pode ser explicado de forma mais eficiente com a ajuda de um exemplo. Considere uma matriz não classificada com os seguintes elementos: {16, 12, 15, 13, 19}.
Exemplo:
Aqui, os elementos adjacentes são comparados e, se não estiverem em ordem crescente, eles serão trocados.
Pseudocódigo do algoritmo de classificação de bolhas
Em pseudocódigo , o algoritmo Bubble Sort pode ser expresso 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
O algoritmo acima processa todas as comparações, mesmo se a matriz já estiver classificada. Ele pode ser otimizado ainda mais interrompendo o algoritmo se o loop interno não causar nenhuma troca. Isso reduzirá o tempo de execução do algoritmo.
Assim, o pseudocódigo do algoritmo de Bubble Sort otimizado pode ser expresso 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
Complexidade de tempo e espaço auxiliar do algoritmo de classificação de bolhas
O pior caso de complexidade de tempo do Bubble Sort Algorithm é O (n ^ 2). Ocorre quando a matriz está em ordem decrescente e você deseja classificá-la em ordem crescente ou vice-versa.
A complexidade de tempo do melhor caso do algoritmo de classificação de bolhas é O (n). Ocorre quando a matriz já está classificada.
A complexidade de tempo de caso médio do algoritmo de classificação de bolhas é O (n ^ 2). Ocorre quando os elementos da matriz estão em ordem confusa.
O espaço auxiliar necessário para o algoritmo Bubble Sort é O (1).
Implementação C ++ do Algoritmo de Classificação de Bolhas
Abaixo está a implementação C ++ do 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;
}
Resultado:
Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19Implementação em Python do algoritmo de classificação de bolhas
Abaixo está a implementação Python do 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)
Resultado:
Unsorted List:
16 12 15 13 19
Sorted List in Ascending Order:
12 13 15 16 19
Implementação C do algoritmo de classificação de bolhas
Abaixo está a implementação C do algoritmo Bubble Sort:
// 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;
}Resultado:
Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19Implementação de JavaScript do algoritmo de classificação de bolhas
Abaixo está a implementação JavaScript do 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);
Resultado:
Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 15 13 16 19Agora você entende o funcionamento do algoritmo de classificação de bolhas
Bubble Sort é o algoritmo de classificação mais simples e é usado principalmente para entender os fundamentos da classificação. O Bubble Sort também pode ser implementado recursivamente, mas não oferece vantagens adicionais para isso.
Usando Python, você pode implementar o algoritmo Bubble Sort com facilidade. Se você não está familiarizado com Python e deseja iniciar sua jornada, começar com um script "Hello World" é uma ótima escolha.
