QUESTIONÁRIO 06 - ED II

INSERÇÃO E MÉTODO SHELL

1)      Por que o método shell têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?

Resposta:

Leva o nome de seu inventor, Ronald L. Shell; consiste na aplicação do método da Inserção, em vários passos, a elementos não consecutivos (separados por determinados intervalos). A cada passo, esse intervalo decresce: primeiro, são ordenados entre si todos os elementos separados de quatro posições. Em seguida, são ordenados os elementos a duas posições de distância. Finalmente, são ordenados os elementos adjacentes. Há também a versão Shell-Metzner, antecessor a ele.Também conhecido por método concha.

2)      A ordenação pelo método shell é um dos mais simples. Qual a principal característica do método ou como ele funciona?

Resposta:

Shell algoritmo de ordenação melhora a ordenação por inserção, comparando os elementos separados por um espaço de várias posições. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Isso permite que um elemento para fazer "passos maiores" em direção a sua posição esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. A várias passagens sobre os tamanhos de dados são feitos espaço cada vez menores. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados. A última etapa da espécie Shell é uma espécie de inserção simples, mas aí já é garantido que os dados são quase ordenada do vetor.

3)      Qual é a classificação do método shell? Qual o seu grau de complexidade?

Resposta:

Shell sort é o mais eficiente algoritmo de classificação dentre os de complexidade quadrática. É um refinamento do método de inserção direta.

4)      Dê exemplo de aplicação do método shell, com as comparações, trocas e iterações.

Resposta:

Execução:

Dado o vetor de entrada: 12, 43, 1, 6, 56, 23, 52, 9

12, 43, 1, 6, 56, 23, 52, 9
12, 43, 1, 6, 56, 23, 52, 9
1, 43, 12, 6, 56, 23, 52, 9
1, 6, 12, 23, 56, 43, 52, 9
1, 6, 12, 23, 52, 43, 56, 9
1, 6, 12, 23, 52, 9, 56, 43
1, 6, 12, 9, 52, 23, 56, 43
1, 6, 9, 12, 52, 23, 56, 43
1, 6, 9, 12, 23, 52, 56, 43
1, 6, 9, 12, 23, 52, 43, 56
1, 6, 9, 12, 23, 43, 52, 56

Em negrito estão os números trocados na atual iteração.
Após as seguintes trocas acima, obtemos o vetor ordenado: 1, 6, 9, 12, 23, 43, 52, 56.

5)      Demonstre o código-fonte do método shell e comente o mesmo.

Resposta:

//***************************************************************************
// Função shell_sorte – Recebe uma matriz desordenada e a ordena com
// algoritmo shell sort
//
// Entradas – matriz a ser ordenada e tamanho da matriz a ordenar
// Saídas - nenhuma
//***************************************************************************
void shell_sort(unsigned char matriz[], unsigned int tamanho){

    unsigned int i, gap;
    unsigned char temp, ret;

    gap = tamanho / 2;
    do {
       do{
          ret=0;
             for (i=0; i< tamanho – gap; i++)
                if (matriz[i] >matriz[i+gap]){
                   temp=array[i];
                      array[i]=array[i+gap];
                      array[i+gap]=temp;
                      ret=1;
                }
       } while(ret);
    } while (gap = gap / 2);
}