Abstrato

MELHORANDO O DESEMPENHO DA CLASSIFICAÇÃO DE ASSINATURA RANDOMIZADA UTILIZANDO OPERADORES DE HASHING E BITWISE

Tamana Pathak e Dr.

Pesquisas feitas na área de classificação de inteiros melhoraram consideravelmente o limite inferior e alcançado com a classificação por comparação, ou seja, para [1] para algoritmos determinísticos ou para um algoritmo de classificação de base no espaço que depende apenas do número de inteiros de entrada . Andersson et al. [2] apresentou uma classificação de assinatura no tempo e espaço linear esperado, o que oferece um desempenho muito fraco do que a classificação rápida tradicional. É bem conhecido que os inteiros no intervalo [1, c] podem ser ordenados no tempo usando a ordenação radix. Os números inteiros em qualquer intervalo [1,] podem ser classificados no tempo [1]. No entanto, estes algoritmos utilizam palavras de memória extra. Apresentamos uma variante simples e estável de ordenação por subscrição para a ordenação de números inteiros, que funciona no tempo e utiliza apenas palavras de memória extra. Com isto, estamos a tentar melhorar o desempenho da classificação de assinaturas implementando de forma diferente e comparando o seu desempenho com os algoritmos de classificação tradicionais e para ver o efeito do tamanho do registo no algoritmo.