Shell Sort

Desenvolvido por: Felipe Weizenmann

Conceito

Shell Sort é um algoritmo de ordenação eficiente.

Um algoritmo simples de entender; Relativamente rápido de processar; Fácil de implementar.

HistóricoCriado em 1959;Desenvolvido por Donald Shell; Publicado pela Universidade de Cincinnati;

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).

Princípios BásicosO 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.

Vantagens

Shellsort é uma ótima opção para arquivos de tamanho moderado;

Sua implementação é simples e requer uma quantidade de código pequena.

DesvantagensO tempo de execução do algoritmo é sensível

à ordem inicial do arquivo;

O método é instável.

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.

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; } }