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 .