Os programadores que mudam do desenvolvimento de PC e web para a codificação de 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 de dados limitado, não há espaço para bibliotecas ou estruturas pré-criadas. Portanto, para aqueles que precisam escrever suas próprias rotinas de classificação, aqui estão algumas considerações sobre como escolher o tipo de bolha humilde.
Plano de fundo
O bubble sort é um algoritmo simples que ordena uma lista de itens na memória. Dada uma matriz, o código compara repetidamente cada par de itens adjacentes e os troca se não estiverem em ordem. O processo se repete até que não ocorram mais trocas. Se fosse possível visualizar a matriz enquanto a classificação estiver em andamento, os valores baixos "bolhariam" para o topo, enquanto os valores grandes afundariam para baixo. Aqui está o código relevante no Visual Basic 2010:
Enquanto swap =True swap =False Para i =0 Para tbl.length - 2 Se tbl(i)> tbl(i + 1) Então tmp =tbl(i) tbl(i) =tbl(i + 1) tbl(i) + 1) =tmp swap =True End If Next End While
Quando escolher a classificação por bolha
Este algoritmo tem várias vantagens. É simples de escrever, fácil de entender e leva apenas algumas linhas de código. Os dados são classificados no local para que haja pouca sobrecarga de memória e, uma vez classificados, os dados estão na memória, prontos para processamento. A principal desvantagem é a quantidade de tempo que leva para classificar. O tempo médio aumenta quase exponencialmente à medida que o número de elementos da tabela aumenta. Dez vezes o número de itens leva quase cem vezes mais tempo para classificar.
Outras classificações de matrizes
Os algoritmos de classificação variam em complexidade, velocidade e sobrecarga. A ordenação por bolhas é a menos complexa, mas também uma das mais lentas. Outras classificações baseadas em array, como a classificação por inserção e a classificação por troca, são um pouco mais rápidas, mas exigem mais código (veja as referências abaixo). A principal vantagem das ordenações baseadas em array é que eles usam o mínimo de código e ocupam a menor quantidade de memória de trabalho. Considere esses tipos de arrays simples com menos de algumas centenas de itens.
Algoritmos de classificação complexa
Conjuntos de dados maiores exigem código mais complexo e mais memória. A classificação rápida e a classificação por heap dividem e copiam os conjuntos de dados para otimizar o número de comparações. A classificação rápida divide continuamente a lista e a remonta em ordem ordenada. A classificação heap copia os dados em uma estrutura de árvore e, em seguida, percorre a árvore para copiar os dados de volta à ordem. Ambos são rápidos e eficientes, mas exigem mais código e muito mais armazenamento de trabalho. Escolha esses algoritmos para grandes conjuntos de dados.
