Estrutura De Dados - Metodos De Ordenação

Universidade Estácio de Sá

Aluno:

Matricula:

Disciplina: Estrutura de dados

Professor:

Trabalho Av2

1. Sobre técnicas de ordenação, dado a seguinte sequencia S:

S = {“maça”, “banana”, “pera”, “goiaba”, “mamão”, “açaí”}

Realize, passo-a-passo e por escrito, a ordenação para cada um dos métodos abaixo:

a) BubbleSort:

houveTroca <- verdade

enquanto houveTroca for verdade faça:

houveTroca <- falso

para i de 1 até 5 faça:

se palavra[i] é maior que palavra[i + 1]

então aux <- palavra[i]

palavra[1] <- palavra[i + 1]

palavra[i + 1] <-aux

houveTroca <- verdade

fimse

fimpara

fimenquanto

Conclusão:

Enquanto 1x = maça, pêra, banana, mamão, açaí, goiaba

Enquanto 2x = maça pêra mamão açaí banana goiaba

Enquanto 3x = maça pêra açaí mamão banana goiaba

Enquanto 4x = maça pêra açaí mamão banana goiaba (não houve troca)

Fim execução

5(para) * 4(enquanto) = 20 comparações

b) SelectionSort:

para i de 1 até 5 faça:

menor <- i

Para j de i+1 até 6 faça:

Se palavra[menor] > palavra[j] então

menor <- j

Fimse

Se menor != i então

aux <- palavra[menor]

palavra[menor] <- palavra[i]

palavra[i] <- aux

Fimse

Fimpara

Conclusão:

Para (I) = executa o código 5x

Para (J) = em qual posição se encontra o menor elemento - 5 comparações

Se posição menor for diferente da posição encontrada em para(J), trocar de posição – 1 comparação

5(execuções) * 6 (comparações) = 30 comparações

c) InsertionSort:

para j de 1 até 5 faça:

elemento <- palavra[j];

i <- j – 1;

ENQUANTO ((i >= 0) E (palavra[i] > elemento)) faça:

//(i>=0) = tratamento de erro, se o elemento for o primeiro não há como testar com o anterior.

palavra[i+1] <- palavra[i]

palavra[i] <- elemento

i <- i–1

fimenquanto

fimpara

maça, banana, pera, goiaba, mamão, açaí

Conclusão:

Para (J) = executa o código 5x

Enquanto = compara se (i >= 0) e (palavra[i] > elemento) – 2 comparações

Enquanto 1x= 2 comparações

maça, banana, pera, goiaba, mamão, açaí

Enquanto 2x = 4 comparações

maça, pera, banana, goiaba, mamão, açaí

Enquanto 3x = 2comparações

maça, pera, banana, goiaba, mamão, açaí

Enquanto 4x = 6 comparações

maça, pera, mamão, banana, goiaba, açaí

Enquanto 5x = 8 comparações

maça, pera, açaí, banana, goiaba, mamão

2+4+2+6+8 = 22 comparações

2. Responda:

a) O que é um ponteiro ?

É um tipo de dado cujo o valor se refere diretamente a um outro valor alocado em outra área da memória, através de seu endereço.

b) como se declara um ponteiro ?

Com um asterisco seguido de um nome qualquer

c) o que são os operadores “*” e “&” para ponteiros?

O “*” retorna o valor da variável que está localizada no ponteiro e “&” retorna o endereço de memória que está localizado o valor da variável contida no ponteiro.

d) quando usar cada um desses operadores ?

Usar “*” para declarar ou operar um ponteiro e “&” para fazer o ponteiro apontar para o endereço de memória da variável.

e) Cite um exemplo envolvendo a declaração e o uso dos operadores de ponteiros.

#include <iostream>

using namespace std;

int main(){

int a, b;

int