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

O que é uma Bubble Classificar?

Bubble Classificar é um algoritmo de ordenação usado para ordenar itens de uma lista em ordem crescente, comparando dois valores adjacentes. Se o primeiro valor for maior que o segundo, o primeiro valor ocupa a posição do segundo, e vice-versa. Se o primeiro valor for menor que o segundo, não há troca de posição.ping é feito.

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ê aprenderá qual o problema que ele resolve, sua forma otimizada, um passo a passo visual e um exemplo prático. Python programa e suas características de desempenho.

Implementando o Bubble Algoritmo de classificação

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

Considere a seguinte lista:

[21, 6, 9, 33, 3]

A solução

Percorra a lista, comparando dois elementos adjacentes e trocando-os.ping eles 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 ordenaçã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 é list menos um.

Passo 3) Para cada passagem externa 1, realize (n – 1) passagens internas. Obtenha o valor do primeiro elemento e compare-o com o valor do segundo. Se o segundo valor for menor que o primeiro, troque as posições.

Passo 4) Repita o passo 3 até chegar à passagem externa (n – 1). Obtenha o próximo elemento da lista e repita o processo realizado no passo 3 até que todos os valores estejam em ordem crescente correta.

Passo 5) Retorne o resultado quando todas as iterações forem concluídas. Retorne os resultados da lista ordenada.

Passo 6) Otimizar 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 antecipadamente.

Estratégias 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 seguindo os seguintes passos:

Passo 1) Crie uma variável de sinalização que monitore se houve alguma troca.ping ocorreu no circuito interno.

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

Passo 3) Se os valores não tiverem trocado de posição, encerre o laço interno e continue com o laço 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 o algoritmo de ordenação por bolha itera pelos valores ao ordená-los.

A imagem a seguir mostra a lista não ordenada:

Primeira iteração

Passo 1)

Os valores 21 e 6 são comparados para verificar qual é maior que o outro.

21 é maior que 6, portanto 21 ocupa a posição que era ocupada por 6, enquanto 6 ocupa a posição que era 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 a acima.

Passo 3)

Os valores 21 e 33 são comparados para encontrar o maior.

O valor 33 é maior que 21, portanto não há troca.ping 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 ao final da primeira iteração é semelhante à mostrada 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:

[3, 6, 9, 21, 33]

Code Explicação

A explicação para o Python BubblO código do programa de classificação é o seguinte:

AQUI,

1. Define uma função bubbleSort que aceita um parâmetro theSeq. O código não produz nada.
2. Obtém o comprimento do array e atribui o valor a uma variável n. O código não produz nenhuma saída.
3. Inicia um laço `for` que executa o algoritmo de ordenação por bolha (n – 1) vezes. Este é o laço externo. O código não gera nenhuma saída.
4. Define uma variável de sinalização que será usada para determinar se uma troca ocorreu ou não. Isso serve para fins de otimização. O código não gera nenhuma saída.
5. Inicia o loop interno que compara todos os valores da lista, do primeiro ao último. O código não produz nada.
6. 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.
7. 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 nenhuma saída.
8. O valor de theSeq[j + 1] é atribuído à posição de theSeq[j]. O código não produz nenhuma saída.
9. O valor da variável tmp é atribuído à posição theSeq[j + 1]. O código não produz nenhuma saída.
10. A variável de sinalização recebe o valor 1 para indicar que ocorreu uma troca. O código não gera nenhuma saída.
11. Utiliza uma instrução if para verificar se o valor da variável flag é 0. O código não produz nenhuma saída.
12. Se o valor for 0, chamamos a instrução break que sai do loop interno.
13. Retorna o valor de theSeq depois de classificado. O código gera a lista classificada.
14. Define uma variável el que contém uma lista de números aleatórios. O código não produz nada.
15. Atribui o valor da função bubbleSort a uma variável result.
16. Imprime o valor da variável resultado.

Bubble classificar vantagens

A seguir, apresentamos algumas das vantagens do algoritmo de ordenação por bolha:

• É fácil de entender.
• Funciona muito bem quando a lista já está ordenada ou quase ordenada.
• Não requer memória extensa.
• É 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.

Bubble classificar Desvantagens

A seguir, apresentamos algumas das desvantagens do algoritmo de ordenaçã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 ordenação é usada para expressar a quantidade de tempo de execução e espaço necessários para ordenar a lista. O algoritmo de ordenação por bolha realiza (n – 1) iterações para ordenar 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 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²).

3) Complexidade espacial

A complexidade espacial mede a quantidade de espaço extra necessária para ordenar a lista. O algoritmo de ordenação por bolha requer apenas um (1) espaço extra para a variável temporal usada na operação de troca.ping valores. Portanto, tem uma complexidade de espaço de O(1).

Perguntas Frequentes