Os programadores que mudam do desenvolvimento de PC e web para a codificação de dispositivos móveis ou sistemas incorporados 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é-construídas. Portanto, para aqueles que precisam escrever suas próprias rotinas de classificação, aqui estão algumas considerações sobre a escolha do tipo de bolha humilde.
Fundo
A classificação por bolha é um algoritmo simples que classifica 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 está em andamento, os valores baixos "borbulhariam" no topo enquanto os valores grandes iriam afundar. Aqui está o código relevante em Visual Basic 2010:
Vídeo do dia
While swap = True swap = False For i = 0 To tbl.length - 2 Se tbl (i)> tbl (i + 1) Então tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = troca tmp = 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 conforme o número de elementos da mesa aumenta. Dez vezes o número de itens leva quase cem vezes mais tempo para classificar.
Outras classificações de matriz
Os algoritmos de classificação variam em complexidade, velocidade e sobrecarga. O tipo de bolha é o menos complexo, mas também um dos mais lentos. 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 (consulte as referências abaixo). A principal vantagem das classificações baseadas em array é que elas usam menos código e ocupam a menor quantidade de memória de trabalho. Considere esses tipos para matrizes simples com menos de algumas centenas de itens.
Algoritmos de classificação complexa
Conjuntos de dados maiores requerem um código mais complexo e mais memória. A classificação rápida e a classificação de 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 na ordem de classificação. A classificação de heap copia os dados em uma estrutura de árvore e, em seguida, atravessa a árvore para copiar os dados de volta à ordem. Ambos são rápidos e eficientes, mas requerem mais código e muito mais armazenamento funcional. Escolha esses algoritmos para grandes conjuntos de dados.
