O que é um Bubble Sort?
Bubble Sort é um algoritmo de classificação usado para classificar itens de lista em ordem crescente, comparando dois valores adjacentes. Se o primeiro valor for maior do que o segundo valor, o primeiro valor assume a posição do segundo valor, enquanto o segundo valor assume a posição do primeiro valor. Se o primeiro valor for inferior ao segundo valor, nenhuma troca será feita.
Este processo é repetido até que todos os valores em uma lista tenham sido comparados e trocados, se necessário. Cada iteração é geralmente chamada de passagem. O número de passes em uma classificação por bolha é igual ao número de elementos em uma lista menos um.
Neste tutorial de classificação por bolha em Python, você aprenderá:
- O que é um Bubble Sort?
- Implementando o algoritmo de classificação de bolhas
- Algoritmo de classificação de bolha otimizado
- Representação visual
- Exemplos Python
- Explicação do código
- Vantagens do tipo bolha
- Desvantagens do tipo bolha
- Análise de complexidade de classificação de bolhas
Implementando o algoritmo de classificação de bolhas
Vamos dividir a implementação em três (3) etapas, a saber, o problema, a solução e o algoritmo que podemos usar para escrever código para qualquer linguagem.
O problema
Uma lista de itens é fornecida em ordem aleatória, e gostaríamos de organizá-los de maneira ordenada
Considere a seguinte lista:
[21,6,9,33,3]
A solução
Percorra a lista comparando dois elementos adjacentes e trocando-os se o primeiro valor for maior do que o segundo valor.
O resultado deve ser o seguinte:
[3,6,9,21,33]
Algoritmo
O algoritmo de classificação por bolha funciona da seguinte maneira
Etapa 1) Obtenha o número total de elementos. Obtenha o número total de itens na lista fornecida
Etapa 2) Determine o número de passagens externas (n - 1) a serem feitas. Seu comprimento é lista menos um
Etapa 3) Execute os passes internos (n - 1) vezes para o passe externo 1. Obtenha o valor do primeiro elemento e compare-o com o segundo valor. Se o segundo valor for menor que o primeiro valor, troque as posições
Etapa 4) Repita as passagens da etapa 3 até chegar à passagem externa (n - 1). Obtenha o próximo elemento na lista e repita o processo que foi executado na etapa 3 até que todos os valores tenham sido colocados em sua ordem crescente correta.
Etapa 5) Retorne o resultado quando todas as passagens tiverem sido feitas. Retorna os resultados da lista classificada
Etapa 6) Otimize o Algoritmo
Evite passagens internas desnecessárias se a lista ou os valores adjacentes já estiverem classificados. Por exemplo, se a lista fornecida já contém elementos que foram classificados em ordem crescente, podemos interromper o loop mais cedo.
Algoritmo de classificação de bolha otimizado
Por padrão, o algoritmo de classificação por bolha em Python compara todos os itens da lista, independentemente de a lista já estar classificada ou não. Se a lista fornecida já estiver classificada, comparar todos os valores é uma perda de tempo e recursos.
Otimizar a classificação por bolha nos ajuda a evitar iterações desnecessárias e economizar tempo e recursos.
Por exemplo, se o primeiro e o segundo itens já estiverem classificados, não há necessidade de iterar pelo restante dos valores. A iteração é encerrada e a próxima é iniciada até que o processo seja concluído, conforme mostrado no exemplo de classificação por bolha abaixo.
A otimização é feita usando as seguintes etapas
Etapa 1) Crie uma variável de sinalização que monitora se alguma troca ocorreu no loop interno
Etapa 2) Se os valores trocaram de posição, continue para a próxima iteração
Etapa 3) Se os benefícios não trocaram de posição, termine o loop interno e continue com o loop externo.
Uma classificação de bolha otimizada é mais eficiente, pois executa apenas as etapas necessárias e ignora as desnecessárias.
Representação visual
Dada uma lista de cinco elementos, as imagens a seguir ilustram como a classificação da bolha itera através dos valores ao classificá-los
A imagem a seguir mostra a lista não classificada
Primeira Iteração
Passo 1)
Os valores 21 e 6 são comparados para verificar qual é maior que o outro.
21 é maior que 6, então 21 assume a posição ocupada por 6, enquanto 6 assume a posição ocupada por 21
Nossa lista modificada agora se parece com a acima.
Passo 2)
Os valores 21 e 9 são comparados.
21 é maior que 9, então trocamos as posições de 21 e 9
A nova lista é agora como acima
Etapa 3)
Os valores 21 e 33 são comparados para encontrar o maior.
O valor 33 é maior que 21, portanto, nenhuma troca ocorre.
Passo 4)
Os valores 33 e 3 são comparados para encontrar o maior.
O valor 33 é maior que 3, então trocamos suas posições.
A lista ordenada no final da primeira iteração é como a anterior
Segunda Iteração
A nova lista após a segunda iteração é a seguinte
Terceira Iteração
A nova lista após a terceira iteração é a seguinte
Quarta Iteração
A nova lista após a quarta iteração é a seguinte
Exemplos Python
O código a seguir mostra como implementar o algoritmo Bubble Sort em Python.
def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)
Executar o programa de classificação de bolhas acima em Python produz os seguintes resultados
[6, 9, 21, 3, 33]
Explicação do código
A explicação para o código do programa Python Bubble Sort é a seguinte
AQUI,
- Define uma função bubbleSort que aceita um parâmetro theSeq. O código não produz nada.
- Obtém o comprimento da matriz e atribui o valor a uma variável n. O código não produz nada
- Inicia um loop for que executa o algoritmo de classificação de bolhas (n - 1) vezes. Este é o loop externo. O código não produz nada
- Define uma variável de sinalização que será usada para determinar se uma troca ocorreu ou não. Isso é para fins de otimização. O código não produz nada
- Inicia o loop interno que compara todos os valores na lista do primeiro ao último. O código não produz nada.
- Usa a instrução if para verificar se o valor do lado esquerdo é maior do que o do lado direito imediato. O código não produz nada.
- Atribui o valor de theSeq [j] a uma variável temporal tmp se a condição for avaliada como verdadeira. O código não produz nada
- O valor doSeq [j + 1] é atribuído à posição doSeq [j]. O código não produz nada
- O valor da variável tmp é atribuído à posição theSeq [j + 1]. O código não produz nada
- A variável flag recebe o valor 1 para indicar que ocorreu uma troca. O código não produz nada
- Usa uma instrução if para verificar se o valor do sinalizador da variável é 0. O código não produz nada
- Se o valor for 0, chamaremos a instrução break que sai do loop interno.
- Retorna o valor de theSeq após ter sido classificado. O código gera a lista classificada.
- Define uma variável el que contém uma lista de números aleatórios. O código não produz nada.
- Atribui o valor da função bubbleSort a um resultado variável.
- Imprime o valor do resultado variável.
Vantagens do tipo bolha
A seguir estão algumas das vantagens do algoritmo de classificação de bolha
- É fácil de entender
- Funciona muito bem quando a lista já está ou quase ordenada
- Não requer muita memória.
- É fácil escrever o código para o algoritmo
- Os requisitos de espaço são mínimos em comparação com outros algoritmos de classificação.
Desvantagens do tipo bolha
A seguir estão algumas das desvantagens do algoritmo de classificação de bolha
- Ele não funciona bem ao classificar listas grandes. Leva muito tempo e recursos.
- É usado principalmente para fins acadêmicos e não para aplicações no mundo real.
- O número de etapas necessárias para classificar a lista é da ordem n 2
Análise de complexidade de classificação de bolhas
Existem três tipos de Complexidade:
1) Complexidade da classificação
A complexidade de classificação é usada para expressar a quantidade de tempo de execução e espaço que leva para classificar a lista. A classificação por bolha faz (n - 1) iterações para classificar a lista, onde n é o número total de elementos na lista.
2) Complexidade de tempo
A complexidade de tempo do tipo de bolha é O (n 2 )
As complexidades de tempo podem ser categorizadas como:
- Pior caso - aqui é onde a lista fornecida está em ordem decrescente. O algoritmo realiza o número máximo de execuções, que é expresso como [Big-O] O (n 2 )
- Melhor caso - ocorre quando a lista fornecida já está classificada. O algoritmo realiza o número mínimo de execuções que é expresso como [Big-Omega] Ω (n)
- Caso médio - isso ocorre quando a lista está em ordem aleatória. A complexidade média é representada como [Big-theta] ⊝ (n 2 )
3) Complexidade do espaço
A complexidade do espaço mede a quantidade de espaço extra necessária para classificar a lista. A classificação por bolha requer apenas um (1) espaço extra para a variável temporal usada para trocar valores. Portanto, possui uma complexidade espacial de O (1).
Resumo
- O algoritmo de classificação por bolha funciona comparando dois valores adjacentes e trocando-os se o valor à esquerda for menor que o valor à direita.
- Implementar um algoritmo de classificação de bolhas é relativamente simples com Python. Tudo que você precisa usar são loops for e instruções if.
- O problema que o algoritmo de classificação por bolha resolve é pegar uma lista aleatória de itens e transformá-la em uma lista ordenada.
- O algoritmo de classificação de bolhas na estrutura de dados tem melhor desempenho quando a lista já está classificada, pois executa um número mínimo de iterações.
- O algoritmo de classificação por bolha não funciona bem quando a lista está na ordem inversa.
- O tipo de bolha tem uma complexidade de tempo de O (n 2 ) e uma complexidade de espaço de O (1)
- O algoritmo de classificação bubbler é mais adequado para fins acadêmicos e não para aplicações do mundo real.
- A classificação de bolha otimizada torna o algoritmo mais eficiente, ignorando iterações desnecessárias ao verificar valores que já foram classificados.