Lista de Algoritmo e Estrutura de Dados

UNIVERSIDADE FEDERAL DE OURO PRETO

GABRIEL FELIPE CORDEIRO FREIRE

JOÃO MARCOS SOARES FERREIRA REIS

LISTA DE EXERCÍCIOS PREPARATÓRIOS PARA A TERCEIRA PROVA

JOÃO MONLEVADE

2016

GABRIEL FELIPE CORDEIRO FREIRE

JOÃO MARCOS SOARES FERREIRA REIS

LISTA DE EXERCÍCIOS PREPARATÓRIOS PARA A TERCEIRA PROVA

Lista de Exercícios solicitada pelo professor Alexandre Magno de Sousa da matéria de Algoritmos e Estrutura de Dados I como requisito parcial à obtenção da nota do segundo bimestre de 2015

JOÃO MONLEVADE

2016

Exercício 1

void Ordena(TipoItem x[], int n){

    TipoItem aux;

    int i, j, tam;

    tam = n;

    for(i=2;i<=n/2;i++){

        aux = x[i];

        for(j = i+1; j

            x[j-1] = x[j];

        }

        x[tam-1] = aux;

        tam--;

    }

}

Exercício 2

int BuscaBin (Item a[], int e, int d, int chave){

    int m, e = 0;

    if (e == d)  return e;

    m = e + ((d- e) / 2);

    if (chave > a[m].chave){

                return BuscaBin (a, m + 1, d, chave);

    }    

    else if (chave < a[m].chave){

                return BuscaBin (a, e, m, chave);

    }

    return m;

}

void InsercaoBin (TipoItem x[], int n){

    int k, i, j;

    TipoItem aux;

    for (i = 1; i < n; i++) {

        k = BuscaBin (x, 0, i, x[i].chave);

        aux = x[i];

        for (j = i - 1; j >= k; j--){

                        x[j + 1].chave = x[j].chave;

        }

                x[k].chave = aux;

    }

}

Exercício 3

R: Realmente, quando h = 1, o ShellSort opera da mesma forma que o algoritmo de Inserção, que é um algoritmo estável. Porém, quando h > 1, as trocas de posição que ocorrem podem alterar a ordem dos registros de chaves iguais. Como no exemplo a seguir, onde utilizo a palavra Shell, considere os números entre colchetes como subchaves, e os valores em negrito como os que estão trocando de posição.

i	1	2	3	4	5
	S	H	E	L[1]	L[2]
h=4	L[2]	H	E	L[1]	S
h=1	H	L[2]	E	L[1]	S
	H	E	L[2]	L[1]	S
	E	H	L[2]	L[1]	S
	E	H	L[2]	L[1]	S
	E	H	L[2]	L[1]	S

Observamos que L[2], no fim da ordenação, vem primeiro que L[1], provando que o algoritmo não é estável.

Exercício 4

Obs.: Considere os valores em negritos nas tabelas como valores que irão se movimentar.

MÉTODO SHELLSORT

I	1	2	3	4	5	6	7	8	9	10
	C	O	M	P	U	T	A	C	A	O
h=4	C	O	A	P	U	T	M	C	A	O
	C	O	A	C	U	T	M	P	A	O
	A	O	A	C	C	T	M	P	U	O
	A	O	A	C	C	O	M	P	U	T
h=1	A	O	A	C	C	O	M	P	U	T
	A	A	O	C	C	O	M	P	U	T
	A	A	C	O	C	O	M	P	U	T
	A	A	C	C	O	O	M	P	U	T
	A	A	C	C	O	M	O	P	U	T
	A	A	C	C	M	O	O	P	U	T
	A	A	C	C	M	O	O	P	T	U
	11 Movimentações	20 Comparações

        

i

1

2

3

4

5

6

7

8

9

10

11

12

D

E

P

A

R

T

A

M

E

N

T

O

h=4

D

E

A

A

R

T

P

M

E

N

T

O

D

E

A

A

E

T

P

M

R

N

T

O

D

E

A

A

E

N

P

M

R

T

T

O

h=1

D

E

A

A

E

N

P

M

R

T

T

O

A

D

E

A

E

N

P

M

R

T

T

O

A

A

D

E

E

N

P

M

R

T

T

O

A

A

D

E

E

M

N

P

R

T

T

O

A

A

D

E

E

M

N

O

P

R

T

T

16 Movimentações

28 Comparações