Estrutura de dados - Algoritmo de classificação de bolhas
A classificação por bolha é um algoritmo de classificação simples. Esse algoritmo de classificação é um algoritmo baseado em comparação em que cada par de elementos adjacentes é comparado e os elementos são trocados se não estiverem em ordem. Este algoritmo não é adequado para grandes conjuntos de dados, pois sua complexidade média e de pior caso são de Ο (n 2 ) onden é o número de itens.
Como funciona a classificação por bolha?
Pegamos um array não classificado para nosso exemplo. A classificação por bolha leva Ο (n 2 ) tempo, então estamos mantendo-a curta e precisa.
A classificação por bolha começa com os dois primeiros elementos, comparando-os para verificar qual é o maior.
Nesse caso, o valor 33 é maior que 14, portanto, já está nos locais classificados. Em seguida, comparamos 33 com 27.
Descobrimos que 27 é menor que 33 e esses dois valores devem ser trocados.
A nova matriz deve ser semelhante a esta -
Em seguida, comparamos 33 e 35. Descobrimos que ambos já estão em posições ordenadas.
Em seguida, passamos para os próximos dois valores, 35 e 10.
Sabemos então que 10 é menor que 35. Portanto, eles não são classificados.
Trocamos esses valores. Descobrimos que atingimos o final da matriz. Após uma iteração, o array deve ficar assim -
Para ser mais preciso, agora estamos mostrando como um array deve ficar após cada iteração. Após a segunda iteração, deve ser assim -
Observe que após cada iteração, pelo menos um valor se move no final.
E quando não há necessidade de troca, o bubble sorts aprende que um array está completamente classificado.
Agora devemos examinar alguns aspectos práticos do tipo de bolha.
Algoritmo
Nós presumimos list é uma matriz de nelementos Além disso, assumimos queswap a função troca os valores dos elementos da matriz fornecidos.
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
Pseudo-código
Observamos no algoritmo que o Bubble Sort compara cada par de elementos do array, a menos que todo o array esteja completamente classificado em ordem crescente. Isso pode causar alguns problemas de complexidade, como o que aconteceria se a matriz não precisasse mais de troca, pois todos os elementos já estão em ascensão.
Para amenizar o problema, usamos uma variável de sinalização swappedo que nos ajudará a ver se alguma troca aconteceu ou não. Se nenhuma troca ocorreu, ou seja, o array não requer mais processamento para ser classificado, ele sairá do loop.
O pseudocódigo do algoritmo BubbleSort pode ser escrito da seguinte forma -
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
Implementação
Mais um problema que não abordamos em nosso algoritmo original e seu pseudocódigo improvisado, é que, após cada iteração, os valores mais altos se estabelecem no final do array. Portanto, a próxima iteração não precisa incluir elementos já classificados. Para esse propósito, em nossa implementação, restringimos o loop interno para evitar valores já classificados.
Para saber sobre a implementação de classificação por bolha na linguagem de programação C, clique aqui .