Abstrato

Solução de hardware para algoritmos de classificação: uma revisão

Rouf Ali

Os algoritmos de ordenação reorganizam os itens/elementos de dados de uma matriz/lista de dados numa determinada ordem, seja por ordem crescente ou decrescente com dados numéricos, por ordem alfabética com dados de caracteres e cronologicamente com o tipo de dados de data. Existem várias aplicações de programação utilizadas em ciência da computação que aplicam técnicas de classificação. Existem dois tipos de algoritmos de classificação. Algoritmos baseados em comparação e algoritmos não baseados em comparação. Num algoritmo de classificação baseado em comparação, os elementos de uma matriz são comparados entre si para determinar qual dos dois elementos deve ocorrer primeiro na lista classificada final. Os melhores algoritmos de classificação baseados na comparação têm um limite inferior de complexidade de n log n. Os algoritmos de classificação baseados em comparação não fazem suposições sobre a entrada e podem abordar qualquer caso de entrada. Os algoritmos não baseados em comparação utilizam a natureza dos itens de dados na lista para realizar a classificação. Os seus algoritmos de classificação utilizam informações especiais sobre as chaves (valores/itens/elementos) e outras operações para além da comparação para determinar a ordem de classificação dos elementos. Consequentemente, o limite inferior n log n não se aplica a estes algoritmos de classificação. Os algoritmos não baseados em comparação são executados em tempo linear e requerem suposições especiais sobre a sequência de entrada a classificar.