Utilizamos a abordagem empírica para o estudo de pior caso do algoritmo de ordenação ShellSort. A complexidade de tempo de pior caso deste algoritmo é conhecida apenas para algumas sequências específicas (uma sequência é um parâmetro do algoritmo). Desenvolvemos um método para determinar um limite superior para o pior caso, baseado em Frobenius, e utilizamos dois métodos previamente existentes, de Pratt e de Erkiö, na a determinação de limites inferiores para o número de comparações durante a ordenação. Através da análise empírica da complexidade de algoritmos, confirmamos as complexidades de pior caso para várias das sequências de passos presentes na literatura, de maneira mais simples que o estudo analítico e, usando a mesma metodologia, apresentamos conjecturas para as complexidades de pior caso desconhecidas.
We use the empirical approach to study the worst case of the ShellSort sorting algorithm. The worst case time complexity of this algorithm is known only for some specific sequences (a sequence is a parameter of this algorithm). We developed a method to determine an upper bound on the worst case, based on Frobenius, and used two previously existing methods, Pratt s and Erkiö s methods, in the determination of lower bounds for the number of comparisons during the sorting. Through the complexity empirical analysis of algorithms, we confirmed the worst case complexities for several step sequences studied in the literature in a simpler way than the analytical studies and, using the same methodology, we present conjectures to the unknown worst case complexities.
