Uma Nova Proposta para a Obtenção da Complexidade de Pior Caso do ShellSort - Souza, Raquel M.; Oliveira, Fabiano S.; Pinto, Paulo E. D. (Trends in Computational and Applied Mathematics, 2019)
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 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.