Bubble sort é um dos algoritmos de classificação mais simples que itera através de um determinado array e compara elementos adjacentes. Se os elementos estiverem na ordem errada, eles serão trocados para colocá-los na ordem correta. Este processo continua até que todo o array seja classificado.
Algoritmo:
Etapa 1:Iterar o array diversas vezes Em cada iteração, compare os elementos adjacentes (i e i + 1)
Etapa 2:Se o elemento atual (i) for maior que o próximo elemento (i + 1), troque-os Repita este processo até que todo o array esteja classificado
Complexidade de tempo:
O(n^2), pois itera pelo array várias vezes e realiza comparações e trocas em cada iteração.
Exemplo de código em Python:
def bubble_sort(arr):
para i no intervalo(len(arr) - 1):
# Iterar pelo array para comparar elementos adjacentes
para j no intervalo(len(arr) - 1 - i):
#Compara o elemento atual com o próximo elemento
se arr[j]> arr[j + 1]:
# Troque os elementos se eles estiverem na ordem errada
arr[j], arr[j + 1] =arr[j + 1], arr[j]
# Retorna o array ordenado
retorno
Exemplo:
Entrada:
[5, 3, 1, 2, 4]
Saída:
[1, 2, 3, 4, 5]
O algoritmo de classificação por bolha itera pela matriz e compara os elementos adjacentes. Se estiverem na ordem errada, eles serão trocados. Este processo é repetido até que todo o array seja classificado.
Veja como o algoritmo funciona neste exemplo:
Iteração 1:
- Compare 5 e 3:Troque-os, pois 5 é maior que 3.
- Compare 3 e 1:Troque-os, pois 3 é maior que 1.
- Compare 2 e 4:Não é necessária troca, pois estão na ordem correta.
- A matriz se torna:[3, 1, 2, 4, 5].
Iteração 2:
- Compare 3 e 1:Troque-os, pois 3 é maior que 1.
- Compare 1 e 2:Não é necessária troca, pois estão na ordem correta.
- Compare 2 e 4:Não é necessária troca, pois estão na ordem correta.
- A matriz se torna:[1, 2, 3, 4, 5].
Iteração 3:
- Compare 1 e 2:Não é necessária troca, pois estão na ordem correta.
- Compare 2 e 3:Não é necessária troca, pois estão na ordem correta.
- Compare 3 e 4:Não é necessária troca, pois estão na ordem correta.
- A matriz se torna:[1, 2, 3, 4, 5].
Iteração 4:
- Compare 1 e 2:Não é necessária troca, pois estão na ordem correta.
- Compare 2 e 3:Não é necessária troca, pois estão na ordem correta.
- Compare 3 e 4:Não é necessária troca, pois estão na ordem correta.
- A matriz permanece inalterada.
Após a quarta iteração, o array é classificado em ordem crescente:[1, 2, 3, 4, 5].
