Uma introdução ao algoritmo de classificação por bolha

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 Bubble Sort algoritmo, 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 [], tamanho)
// loop para acessar cada elemento do array
para i = 0 a tamanho-1 faça:
// faz um loop para comparar os elementos da matriz
para j = 0 a size-i-1 faça:
// compare os elementos adjacentes
se Arr [j]> Arr [j + 1] então
// troque-os
troca (Arr [j], Arr [j + 1])
fim se
fim para
fim para
fim

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 [], tamanho)
// loop para acessar cada elemento do array
para i = 0 a tamanho-1 faça:
// verifique se a troca ocorre
swapped = false
// faz um loop para comparar os elementos da matriz
para j = 0 a size-i-1 faça:
// compare os elementos adjacentes
se Arr [j]> Arr [j + 1] então
// troque-os
troca (Arr [j], Arr [j + 1])
swapped = true
fim se
fim para
// se nenhum elemento foi trocado, isso significa que o array está classificado agora, então interrompa o loop.
se (não trocado) então
pausa
fim se
fim para
fim

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.

Relacionado: O que é notação Big-O?

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:

// implementação C ++ do
// algoritmo de classificação por bolha otimizado
#incluir 
usando namespace std;
// Função para realizar Bubble Sort
void bubbleSort (int arr [], int size) {
// Loop para acessar cada elemento da matriz
para (int i = 0; i // Variável para verificar se ocorre troca
bool trocado = falso;
// faz um loop para comparar dois elementos adjacentes da matriz
para (int j = 0; j // Comparando dois elementos de array adjacentes
if (arr [j]> arr [j + 1]) {
// Troque os dois elementos se eles forem
// não está na ordem correta
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
trocado = verdadeiro;
}
}
// Se nenhum elemento foi trocado, isso significa que a matriz está classificada agora,
// então interrompa o loop.
if (swapped == false) {
pausa;
}
}
}
// Imprime os elementos do array
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};
// Encontrando o comprimento da matriz
tamanho int = sizeof (arr) / sizeof (arr [0]);
// Imprimindo o array não classificado fornecido
cout << "Matriz não classificada:" << endl;
printArray (arr, tamanho);
// Chamando a função bubbleSort ()
bubbleSort (arr, tamanho);
// Imprimindo a matriz classificada
cout << "Matriz classificada em ordem crescente:" << endl;
printArray (arr, tamanho);
return 0;
}

Resultado:

Matriz não classificada: 
16 12 15 13 19 
Matriz classificada em ordem crescente:
12 13 15 16 19

Implementação em Python do algoritmo de classificação de bolhas

Abaixo está a implementação Python do algoritmo Bubble Sort:

# Implementação Python do
# algoritmo de classificação por bolha otimizado
# Função para realizar Bubble Sort
def bubbleSort (arr, tamanho):
# Loop para acessar cada elemento da lista
para i no intervalo (tamanho-1):
# Variável para verificar se ocorre troca
swapped = False
# loop para comparar dois elementos adjacentes da lista
para j no intervalo (tamanho-i-1):
# Comparando dois elementos de lista adjacentes
se arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
swapped = True
# Se nenhum elemento foi trocado, isso significa que a lista está classificada agora,
# então interrompa o loop.
se trocado == Falso:
pausa
# Imprime os elementos da lista
def printArray (arr):
para o elemento em chegada:
imprimir (elemento, fim = "")
impressão("")
arr = [16, 12, 15, 13, 19]
# Encontrar o comprimento da lista
tamanho = len (arr)
# Imprimindo a lista não classificada fornecida
imprimir ("Lista não classificada:")
printArray (arr)
# Chamando a função bubbleSort ()
bubbleSort (arr, tamanho)
# Imprimindo a lista classificada
imprimir ("Lista classificada em ordem crescente:")
printArray (arr)

Resultado:

Lista não classificada:
16 12 15 13 19 
Lista classificada em ordem crescente:
12 13 15 16 19

Relacionado: Como usar loops For em Python

Implementação C do algoritmo de classificação de bolhas

Abaixo está a implementação C do algoritmo Bubble Sort:

// implementação C do
// algoritmo de classificação por bolha otimizado
#incluir 
#incluir 
// Função para realizar Bubble Sort
void bubbleSort (int arr [], int size) {
// Loop para acessar cada elemento da matriz
para (int i = 0; i // Variável para verificar se ocorre troca
bool trocado = falso;
// faz um loop para comparar dois elementos adjacentes da matriz
para (int j = 0; j // Comparando dois elementos de array adjacentes
if (arr [j]> arr [j + 1]) {
// Troque os dois elementos se eles forem
// não está na ordem correta
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
trocado = verdadeiro;
}
}
// Se nenhum elemento foi trocado, isso significa que a matriz está classificada agora,
// então interrompa o loop.
if (swapped == false) {
pausa;
}
}
}
// Imprime os elementos do array
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};
// Encontrando o comprimento da matriz
tamanho int = sizeof (arr) / sizeof (arr [0]);
// Imprimindo o array não classificado fornecido
printf ("Matriz não classificada: \ ⁠n");
printArray (arr, tamanho);
// Chamando a função bubbleSort ()
bubbleSort (arr, tamanho);
// Imprimindo a matriz classificada
printf ("Matriz classificada em ordem crescente: \ ⁠n");
printArray (arr, tamanho);
return 0;
}

Resultado:

Matriz não classificada: 
16 12 15 13 19 
Matriz classificada em ordem crescente: 
12 13 15 16 19

Implementação de JavaScript do algoritmo de classificação de bolhas

Abaixo está a implementação JavaScript do algoritmo Bubble Sort:

// implementação de JavaScript do
// algoritmo de classificação por bolha otimizado
// Função para realizar Bubble Sort
function bubbleSort (arr, size) {
// Loop para acessar cada elemento da matriz
para (deixe i = 0; eu// Variável para verificar se ocorre troca
var trocada = falso;
// faz um loop para comparar dois elementos adjacentes da matriz
para (seja j = 0; j// Comparando dois elementos de array adjacentes
if (arr [j]> arr [j + 1]) {
// Troque os dois elementos se eles forem
// não está na ordem correta
deixe temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
trocado = verdadeiro;
}
// Se nenhum elemento foi trocado, isso significa que a matriz está classificada agora,
// então interrompa o loop.
if (swapped == false) {
pausa;
}
}
}
}
// Imprime os elementos do array
function printArray (arr, size) {
para (deixe i = 0; eudocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// Encontrando o comprimento da matriz
var size = arr.length;
// Imprimindo o array não classificado fornecido
document.write ("Matriz não classificada: 
");
printArray (arr, tamanho);
// Chamando a função bubbleSort ()
bubbleSort (arr, tamanho);
// Imprimindo a matriz classificada
document.write ("Matriz classificada em ordem crescente: 
");
printArray (arr, tamanho);

Resultado:

Matriz não classificada:
16 12 15 13 19
Matriz classificada em ordem crescente:
12 15 13 16 19

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

Como começar a usar Python usando um script "Hello World"

Python é uma das linguagens de programação mais populares em uso hoje. Siga este tutorial para começar com seu primeiro script Python.

Leia a seguir

Sobre o autor