ShellSort

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO PARANÁ
ENGENHARIA DE COMPUTAÇÃO

RaFAEL RIBEIRO FERREIRA

shell sort

CURITIBA

2014
SUMÁRIO

1. INTRODUÇÃO 4
2. MÉTODO DE ORDENAÇÃO SHELL SORT 4
3. MAIN 5
4. DEBUG 6
5. CONCLUSÃO 6
6. REFERÊNCIAS 7

ÍNDICE DE ILUSTRAÇÕES

Figura 1 - Método ShellSort 4
Figura 2 - Função principal 5
Figura 3 – Debug 6

1. INTRODUÇÃO
O desenvolvimento deste programa teve como objetivo ordenar um vetor de caracteres usando um método de ordenação chamado ShellSort. No programa será implementado uma função de ordenação do tipo ShellSort, e também um vetor de inteiros do tipo Int. Para o vetor, são atribuídos números randômicos, para isso foi usado a função rand(). E após isso é usado a função ShellSort para ordenar os números do vetor.

2. MÉTODO DE ORDENAÇÃO SHELL SORT

Figura 1 - Método ShellSort
O método de ordenação ShellSort é uma extensão do método InsertionSort. Este algoritmo de inserção troca itens adjacentes quando está procurando o ponto de inserção na sequencia destino. Se o menor valor estiver na posição mais a direita no vetor, então o número de comparações é igual a n-1 para encontrar o seu ponto de inserção. O shellSort contorna este problema, permitindo trocas de registros distantes um do outro. Em geral, ele passa várias vezes no vetor dividindo-o em vetores menores e nestes são aplicados o algoritmo de ordenação por inserção tradicional.
O shellSort faz divisão em h intervalos, esse é seu diferencial. Após essa aplicação, ele executa o método de inserção.

Equações: h(s > 1) = 3h(s − 1) + 1 h(s = 1) = 1

A complexidade desse algoritmo contém alguns problemas matemáticos muito difíceis, por exemplo a própria sequência de incrementos para h. De acordo com teste empíricos nas duas formulas para o cálculo dos incrementos, a ordem de complexidade do