1- Por que o método shell têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?
R: O método de comparações e movimentações do ShellSort lembra o formato de uma 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?
R: Sua principal característica é utilizar a quebra sucessiva de seqüência a ser ordenada e implementa a ordenação na seqüência obtida
3- Qual é a classificação do método shell? Qual o seu grau de complexidade?
R: É classificado dentre os de complexidade quadrática, seu grau de complexidade é O(n^2 )
4-Dê exemplo de aplicação do método shell, com as comparações, trocas e iterações.
R: - Temos o seguinte vetor de números inteiros :
V = (36 , 24 , 17 , 14 , 39 , 27)
- A cada passagem do método de inserção ShellSort , o Vetor vai sendo alterado da seguinte forma :
- Inicial: V=(36,24,17,14,39,47)
-Apos i=2 V=(24,36,17,14,39,27)
-Apos i=3 V=(17,24,36,14,39,27)
-Apos i=4 V=(14,17,24,36,39,27)
-Apos i=5 V=(14,17,24,36.39,27)
-Apos i=6 V=(14,17,24,27,36,39)
5- Demonstre o código-fonte do método shell e comente o mesmo.
void shell (int *v,int i) {
int x , j , valor;
int h = 1;
do{
h=3*h+1
}while(h< i);
do{
h/=3;
for(x = h; x < i; x++) {
valor = v [x]
j = x - h;
while (j>=0 && valor < v[j]) {
v [j + h] = v [j]
j = h
}
v [j + h] = valor
}
}while (h >1)
}
O algoritmo usa variável auxiliar denominada a distancia de comparação (h) , o valor de h e inicializado com um valor próximo de n/2.
Nenhum comentário:
Postar um comentário