Classificação de bolhas em Python - Explicação da classificação por bolhas com código de exemplo

Introdução ao Bubble Sort em Python

A classificação por bolha é um algoritmo de classificação simples e lógico. Seu princípio de funcionamento é baseado na troca recursiva de elementos adjacentes, se a ordem estiver incorreta. Neste tópico, vamos aprender sobre o Bubble Sort no Python.

A classificação por bolha às vezes também é conhecida como classificação por afundamento, classificação por ondulação.

Vamos ver através de um exemplo:

Primeira corrida

( 6 1 4 3) -> ( 1 6 4 2): Aqui os dois elementos são trocados se a ordem não estiver correta.

(1 6 4 2) -> (1 4 6 2): Aqui os próximos dois elementos são trocados se a ordem não estiver correta.

(1 4 6 2 ) -> (1 4 2 6 ): Aqui os próximos dois elementos são trocados se a ordem não estiver correta.

Segunda execução

( 1 4 2 6) -> ( 1 4 2 6): Aqui são comparados dois elementos, mas não os trocamos, pois a ordem está correta.

(1 4 2 6) -> (1 2 4 6): Aqui os próximos dois elementos são trocados, pois a ordem não está correta.

(1 2 4 6 ) -> (1 2 4 6 ): Aqui os dois últimos elementos são comparados, mas não são trocados, pois a ordem é

Agora sabemos que a matriz parece classificada, no entanto, uma execução é necessária sem nenhuma troca, para o algoritmo para saber se a classificação é feita.

Terceira execução

( 1 2 4 6) -> ( 1 2 4 6): Nenhuma troca nos dois primeiros elementos.

(1 2 4 6) -> (1 2 4 6): Nenhuma troca nos próximos dois elementos.

(1 2 4 6 ) -> (1 2 4 6 ): Nenhuma troca nos últimos dois elementos.

Como não houve troca em nenhum estágio, agora o algoritmo entende que a classificação é perfeita.

O tipo de bolha ganhou esse nome porque os elementos se movem para a ordem correta, que é como bolhas subindo à superfície.

Classificação de bolhas na linguagem Python

Agora vamos ver a implementação lógica da classificação de bolhas por meio de python. Atualmente, o Python é uma linguagem muito usada. Compreendê-lo através do python certamente lhe dará a confiança para poder escrevê-lo em qualquer outro idioma também.

Código Python

def bubble_Sort(arr): m = len(arr) # Traverse through all the array elements for u in range(m): for v in range(0, mu-1): # traverse the array from 0 to mu-1 # Swap if the element is greater than adjacent next one if arr(v) > arr(v+1) : arr(v), arr(v+1) = arr(v+1), arr(v)

Para imprimir a matriz após a classificação de bolhas, você precisa seguir o código:

for i in range(len(arr)): print("%d" %arr(i)), Here arr will be your array.

Explicação do código Python

Aqui "m" é o comprimento da matriz. Dois loops for mantêm a lógica real do solo, onde "u" representa o primeiro elemento, enquanto "v" representa o segundo com o qual o primeiro elemento deve ser comparado para troca, se a ordem de classificação entre os dois não estiver correta.

"Arr (v)> arr (v + 1)" representa a comparação de elementos consecutivos; se o primeiro elemento for maior que o segundo elemento, a operação de troca será realizada pela seguinte expressão:

Ou seja, "arr (v), arr (v + 1) = arr (v + 1), arr (v)".

Essa operação de troca é chamada de swap. A parte boa é que não é necessária memória temporária para esse tipo de operação de troca.

"U" representa o loop de cada execução, enquanto "v" representa estágios de cada estágio. Um exemplo na seção acima pode ser referido.

Depois de realizar a classificação por bolhas, é possível ver a matriz classificada, com o código mencionado abaixo:

for i in range(len(arr)): print ("%d" %arr(i)),

Vamos ver como isso se comporta no Python IDE, para uma compreensão mais profunda:

Resultado:

Existem alguns fatos sobre o Bubble Sort, que todos devem saber antes de implementá-lo:

Uma classificação de bolha geralmente é considerada um método de classificação não muito eficiente. Como ele tem que trocar os itens até que sua localização final seja conhecida. Isso tudo leva ao desperdício de operações e, portanto, muito caro. Esse algoritmo passa por todos os elementos, onde a classificação é necessária ou não. Depois que a execução passa sem nenhuma troca, a classificação de bolha é considerada concluída.
Essa é a mais simples de todas as estruturas de dados, para qualquer iniciante isso dá uma boa confiança. É fácil de construir e entender.
Ele usa muito tempo e memória.
Este é considerado um algoritmo estável, pois preserva a ordem relativa dos elementos.
Considerado bom para pequeno array / lista. No entanto, é uma má idéia usá-lo por muito tempo.

Conclusão

Percorrendo o conteúdo acima do tipo de bolha, é possível ter uma compreensão clara desse algoritmo de classificação, especializado em python. Uma vez que se sinta confortável com a lógica de classificação de bolhas, será mais fácil entender o outro conjunto de estruturas de dados. Uma abordagem lógica é a única maneira de se destacar no campo da estrutura de dados. Entender primeiro a lógica do algoritmo da estrutura de dados em todos os estágios e depois direcionar seu código através do Python ou em qualquer outra linguagem deve ser o caminho.

Artigos recomendados

Este é um guia para o Bubble Sort em Python. Aqui discutimos a implementação lógica da classificação de bolhas através do código python com a explicação. Você também pode consultar o seguinte artigo para saber mais -