Shell sort

Se encontrar algum contexto que discorde, entre em contato!
Obrigado!
Felipe Weizenmann

1. Shell Sort Desenvolvido por: Felipe Weizenmann

2. Conceito Shell Sort é um algoritmo de ordenação eficiente . Um algoritmo simples de entender; Relativamente rápido de processar; Fácil de implementar .

3. Histórico Criado em 1959; Desenvolvido por Donald Shell; Publicado pela Universidade de Cincinnati;

4. Funcionamento Ele divide um grande vetor de dados em vetores menores, ordenando-os e fazendo isso novamente para ter um único vetor ordenado e então trabalhar em cima dele, que seria mais prático e rápido; O  algoritmo de Shell Sort em si mesmo não ordena nada, mas aumenta a eficiência de outros algoritmos de ordenação (como o da inserção e seleção).

5. Princípios Básicos O Shell Sort se baseia em uma variável chamada de incremento de sequência , que é dado por h  e ao decorrer da execução do algoritmo, é decrementada até 1. Utilizando o incremento de sequência ,  o algoritmo compara elementos distantes em um vetor, em vez de comparar com o próximo.

6. Vantagens Shellsort é uma ótima opção para arquivos de tamanho moderado; Sua implementação é simples e requer uma quantidade de código pequena.

7. Desvantagens O tempo de execução do algoritmo é sensível à ordem inicial do arquivo; O método é instável.

8. Análise A complexidade do algoritmo ainda não é conhecida; Ninguém ainda foi capaz de encontrar uma fórmula fechada para sua função de complexidade; A sua análise contém alguns problemas matemáticos muito difíceis Exemplo : escolher a sequência de incrementos. O que se sabe é que cada incremento não deve ser múltiplo do anterior.

9. Código-fonte // ShellSort - com incrementos de Shell template < class Comparable > void ShellSort (vector< Comparable > & vec ) { int j; for ( int gap = vec.size ()/2; gap > 0; gap /= 2) for ( int i = gap; i < vec.size (); i++) { Comparable tmp = vec [i]; for (j = i; j>gap && tmp < vec [j-gap]; j -= gap) vec [j ] = vec [j-gap]; vec [j ] = tmp ; } }