Aeds

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE MINAS GERAIS

CAMPUS SÃO JOÃO EVANGELISTA

Exercícios de Algoritmos e Estrutura de Dados

Assunto: Lista de Exercícios 5

Componentes: Wárlley Júnio Andrade

Curso: Superior em Sistemas de Informação Série/Turma: BSI111A Professor: Bruno Toledo

São João Evangelista, Maio de 2012.

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE MINAS GERAIS

CAMPUS SÃO JOÃO EVANGELISTA 1. Basicamente como é o funcionamento do algoritmo Shellsort? 1. Ordenação é efetuada dividindo o conjunto em subconjuntos. 2. Os subconjuntos são constituídos por elementos separados n elementos (incrementos). 3. Os subconjuntos são ordenados utilizando o método de inserção. 4. Repetição dos pontos 1, 2 e 3, com diminuição do incremento, até o conjunto estar ordenado. 2. Qual a diferença entre a ordenação por inserção direta e a ordenação por Shellsort? A diferença com relação à inserção direta é o número de segmentos do vetor. Na inserção direta é considerado um único segmento do vetor onde os elementos são inseridos ordenadamente. No método do Shell são considerados diversos segmentos. Inserção direta movimenta elementos adjacentes, já o Shellsort permite a troca de elementos distantes. 3. Utilizando o algoritmo Shellsort faça a ordenação do seguinte arranjo: 12, 43, 1, 6, 56, 23, 52, 9. Vetor inicial: (N = 8) 12 43 1 6 56 23 52 9  Primeiro passo: H = 4 12 43 1 6
1 2 3 4

56
1

23
2

52
3

9
4 seguimento

Antes da ordenação: 12, 56 43, 23 1, 52 Após a ordenação: 12, 56 23, 43

6, 9

1, 52

6, 9

Seguimento original: H=4 12 23 1 6  Segundo passo: H= 2 12 43 1 6
1 2 1 2

56

43

52

9

56
1

23
2

52
1

9
2 seguimento

Antes da ordenação 12, 1, 56, 52 Após a ordenação 1, 12, 52, 56

23, 6, 43, 9

6, 9, 23,43

Seguimento original: H = 2 1 6 12 9

52

23

56

43

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DE MINAS GERAIS

CAMPUS SÃO JOÃO