Vantagens e Desvantagens do Bubble Sort

Programadores que migram de desenvolvimento para PC e web para codificação em dispositivos móveis ou sistemas embarcados descobrem que mais tempo é gasto selecionando e codificando suas próprias estruturas de dados e algoritmos. Com menos memória e armazenamento limitado, não há espaço para bibliotecas ou frameworks prontos. Para quem precisa escrever suas próprias rotinas de ordenação, aqui estão considerações sobre o humilde bubble sort.

Contexto

O bubble sort é um algoritmo simples que ordena uma lista de itens na memória. Dado um array, o código compara repetidamente cada par de itens adjacentes e os troca se não estiverem em ordem. O processo repete até que não haja mais trocas. Se fosse possível visualizar o array durante a ordenação, os valores menores "borbulhariam" para o topo enquanto os maiores afundariam para o fundo. Aqui está o código relevante em Visual Basic 2010:

While swap = True
  swap = False
  For i = 0 To tbl.length - 2
    If tbl(i) > tbl(i + 1) Then
      tmp = tbl(i)
      tbl(i) = tbl(i + 1)
      tbl(i + 1) = tmp
      swap = True
    End If
  Next
End While

Quando Escolher o Bubble Sort

Este algoritmo tem várias vantagens. É simples de escrever, fácil de entender e ocupa apenas algumas linhas de código. Os dados são ordenados no local, então há pouca sobrecarga de memória e, uma vez ordenados, os dados estão na memória, prontos para processamento. A principal desvantagem é o tempo que leva para ordenar. O tempo médio aumenta quase exponencialmente conforme o número de elementos da tabela aumenta. Dez vezes mais itens levam quase cem vezes mais tempo para ordenar.

Outros Algoritmos de Ordenação por Array

Algoritmos de ordenação variam em complexidade, velocidade e sobrecarga. O bubble sort é o menos complexo, mas também um dos mais lentos. Outros sorts baseados em array, como insertion sort e exchange sort, são um pouco mais rápidos, mas exigem mais código. A principal vantagem dos sorts baseados em array é que usam menos código e exigem menor memória de trabalho. Considere estes sorts para arrays simples com menos de algumas centenas de itens.

Algoritmos de Ordenação Complexos

Conjuntos de dados maiores exigem código mais complexo e mais memória. O quick sort e o heap sort dividem e copiam os conjuntos de dados para otimizar o número de comparações. O quick sort divide continuamente a lista e a remonta em ordem. O heap sort copia os dados em uma estrutura de árvore e depois percorre a árvore para copiar os dados de volta em ordem. Ambos são rápidos e eficientes, mas exigem mais código e muito mais armazenamento de trabalho. Escolha estes algoritmos para grandes conjuntos de dados.

• Como Desfocar Algo no Paint
• Como Alterar a Localização da Conta da App Store