Bubble Algoritmo de classificação com Python usando exemplo de lista

O que é uma Bubble Classificar?

Bubble Classificar é um algoritmo de classificação usado para classificar itens de lista em ordem crescente, comparando dois valores adjacentes. Se o primeiro valor for superior ao segundo valor, o primeiro valor ocupa 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 de uma lista tenham sido comparados e trocados, se necessário. Cada iteração é geralmente chamada de passagem. O número de passagens em uma classificação por bolha é igual ao número de elementos em uma lista menos um.

Neste curso Bubble Classificando em Python tutorial você vai aprender:

Implementando o Bubble Algoritmo de classificação

Dividiremos 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

Itere pela lista comparando dois elementos adjacentes e trocando-os se o primeiro valor for maior 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

Passo 1) Obtenha o número total de elementos. Obtenha o número total de itens na lista fornecida

Passo 2) Determine o número de passagens externas (n – 1) a serem feitas. Seu comprimento é lista menos um

Passo 3) Execute passagens internas (n – 1) vezes para a passagem externa 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

Passo 4) Repita as passagens da etapa 3 até chegar à passagem externa (n – 1). Obtenha o próximo elemento da lista e repita o processo executado na etapa 3 até que todos os valores tenham sido colocados na ordem crescente correta.

Passo 5) Retorne o resultado quando todas as passagens forem concluídas. Retornar os resultados da lista ordenada

Passo 6) Algoritmo de otimização

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

Otimizado Bubble Algoritmo de classificação

Por padrão, o algoritmo para classificação por bolhas em Python compara todos os itens na lista, independentemente de a lista já estar ordenada ou não. Se a lista fornecida já estiver ordenada, comparar todos os valores é um desperdício 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 será necessário iterar pelo restante dos valores. A iteração é encerrada e a próxima é iniciada até que o processo seja concluído conforme mostrado abaixo Bubble Exemplo de classificação.

A otimização é feita usando as seguintes etapas

Passo 1) Crie uma variável de flag que monitore se ocorreu alguma troca no loop interno

Passo 2) Se os valores trocaram de posição, continue para a próxima iteração

Passo 3) Se os benefícios não trocaram de posição, encerre o loop interno e continue com o loop externo.

Uma classificação por bolha otimizada é mais eficiente, pois executa apenas as etapas necessárias e ignora aquelas que não são obrigatórias.

Representação visual

Dada uma lista de cinco elementos, as imagens a seguir ilustram como a classificação por bolha itera pelos 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 ocupa a posição ocupada por 6 enquanto 6 ocupa 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

Passo 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 acima

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

Python Exemplos

O código a seguir mostra como implementar o Bubble Algoritmo de classificação em Python.

def bubbleSort( theSeq ):
    n = len( theSeq )

    for i in range( n - 1 ) :
        flag = 0

        for j in range(n - 1) :
            
            if theSeq[j] > theSeq[j + 1] : 
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21,6,9,33,3] 

result = bubbleSort(el)

print (result)

Executando 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 Python Bubble Classificar o código do programa é o seguinte

AQUI,

Define uma função bubbleSort que aceita um parâmetro theSeq. O código não produz nada.
Obtém o comprimento do array 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 por bolha (n – 1) vezes. Este é o loop externo. O código não produz nada
Define uma variável de flag que será usada para determinar se ocorreu uma troca 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 da 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 que aquele 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 de theSeq[j + 1] é atribuído à posição de theSeq[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 uma troca ocorreu. 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 gera nada
Se o valor for 0, chamamos a instrução break que sai do loop interno.
Retorna o valor de theSeq depois de 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 uma variável result.
Imprime o valor da variável resultado.

Bubble classificar vantagens

A seguir estão algumas das vantagens do algoritmo de classificação por bolha

É fácil de entender
Funciona muito bem quando a lista já está ou quase classificada
Não requer memória extensa.
É fácil escrever o código do algoritmo
Os requisitos de espaço são mínimos em comparação com outros algoritmos de classificação.

Bubble classificar Desvantagens

A seguir estão algumas das desvantagens do algoritmo de classificação por bolha

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 passos necessários para ordenar a lista é da ordem n²

Análise de complexidade de Bubble Classificar

Existem três tipos de complexidade:

1) Classificar complexidade

A complexidade de classificação é usada para expressar a quantidade de tempo de execução e espaço necessário 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 da classificação por bolha é O(n²)

As complexidades de tempo podem ser categorizadas como:

Pior caso – é aqui que a lista fornecida está em ordem decrescente. O algoritmo executa o número máximo de execuções que é expresso como [Big-O] O(n²)
Melhor caso – isso ocorre quando a lista fornecida já está ordenada. O algoritmo executa 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²)

3) Complexidade espacial

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 troca de 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.
A implementação de um algoritmo de classificação por 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 por bolha 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.
A classificação por bolha tem uma complexidade de tempo de O (n²) e uma complexidade espacial de O (1)
O algoritmo de classificação por bolha é mais adequado para fins acadêmicos e não para aplicações do mundo real.
A classificação por bolha otimizada torna o algoritmo mais eficiente, ignorando iterações desnecessárias ao verificar valores que já foram classificados.

Você pode gostar: