Voltar
Artigo Acesso aberto Produção Nacional Revisado por pares
BIBTEX RIS

Uma Nova Proposta para a Obtenção da Complexidade de Pior Caso do ShellSort

2019; Sociedade Brasileira de Matemática Aplicada e Computacional; Volume: 20; Issue: 3 Linguagem: Português

10.5540/tema.2019.020.03.457

ISSN

2179-8451

Autores

Raquel M. Souza, Fabiano S. Oliveira, Paulo E. D. Pinto,

Tópico(s)

Algorithms and Data Compression

Resumo

A complexidade de pior caso do ShellSort, um algoritmo de ordenação por comparação, depende de uma sequência de passos dada de entrada. Cada passo consiste de um inteiro representando a diferença de índices dos pares de elementos que devem ser comparados durante a ordenação de um vetor de entrada. Tal complexidade é conhecida somente para algumas sequências específicas. Neste trabalho, usamos uma relação entre ShellSort e o número de Frobenius para apresentar um novo algoritmo que provê um limite superior no número de comparações que o \mbox{ShellSort} perfaz, para dados vetor e sequência de passos. Aplicamos este algoritmo, em conjunto com uma análise de complexidade empírica, para estudar sequências cujas complexidades de pior caso são conhecidas através do método analítico. Mostramos que a abordagem empírica foi bem sucedida em determinar tais complexidades. Baseado nestes resultados positivos, estendemos o estudo para sequências para as quais as complexidades de pior caso estão em aberto.

Referência(s)