QUESTIONÁRIO 06 - 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?

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.

QUESTIONÁRIO 05 - ORDENAÇÃO E MÉTODO BOLHA

1) Ordenar é um processo de rearranjar um conjunto de objetos em uma ordem ascendente/crescente ou descendente/decrescente. Qual a importância da ordenação para qualquer processo e para informática? Dê exemplos práticos de utilização. Defina a complexidade dos métodos de ordenação e a sua classificação.

O objetivo principal da ordenação é facilitar a organização e a localização posterior de dados do conjunto ordenado. Pode-se citar uma lista telefônica. Imagine como seria consultar o telefone de uma pessoa se os nomes não estivessem classificados em ordem alfabética. Para algoritmos de ordenação interna, as medidas de complexidade relevantes contam o número de comparações entre chaves e o número de movimentações de itens do arquivo, os métodos de ordenação são classificados em dois grandes grupos: ordenação interna e externa.

2) Qual é a classificação dos métodos de ordenação? Qual a diferença entre eles? Quais são os métodos de ordenação mais utilizados ou principais?

1-ordenação interna: São os métodos que não necessitam de uma memória

2-Ordenação externa : Quando o arquivo a ser ordenado não cabe na memória principal e , por isso , tem de ser armazenado em fita ou disco .

ShellSort , QuickSort , HeapSort e MergeSort são considerados mais eficientes .

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

O algortimo de “ordenação bolha”, ou “bubble sort”, recebeu este nome pela imagem pitoresca usada para descrevê-lo: os elementos maiores são mais leves, e sobem como bolhas até suas posições corretas.

A idéia fundamental é fazer uma série de comparações entre os elementos do vetor.

Quando dois elementos estão fora de ordem, há uma inversão e esses dois elementos são trocados de posição.

Assim, o primeiro elemento é comparado com o segundo. Se uma inversão for encontrada, a troca é feita.

. O processo continua até que o penúltimo elemento seja comparado com o último.

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

O BubbleSort é um método de simples implementação e de ordem de complexidade quadrática.

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

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

/* Ordenação bolha */

void bolha (int n, int* v)

{

int i,j,temp;

for (i=n-1; i>=1; i--)

for (j=0; j

if (v[j]>v[j+1]) { /* troca */

temp = v[j];

v[j] = v[j+1];

v[j+1] = temp;

}

}

Na quinta linha do código verifica-se os dois elementos se estão desordenados. Se os elementos não estiverem ordenados a troca exige uma variável de armazenamento temporário (temp = v[j+1];) do mesmo tipo que a dos elementos do array que está sendo ordenado.