RELATORIO TRABALHO PRATRICO

Prévia do material em texto

FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
INTRUDUÇÃO 
Em nosso dia a dia nos deparamos com a necessidade de consultar dadosordenados. Como por 
exemplo, uma lista telefônica, um dicionário. Por isso uma das atividades mais utilizada na 
computação é a ordenação. 
Ordenar corresponde ao processo de rearranjar um conjunto de objetosem ordem ascendente ou 
descendente. O objetivo principal da ordenaçãoé facilitar a recuperação posterior de itens do 
conjunto ordenado. Aatividade de colocar as coisas em ordem está presente na maioria 
dasaplicações em que os objetos armazenados têm de ser pesquisados e recuperados. [1] 
Existem diversos algoritmos para ordenação interna: BubbleSort, InsertSort, SelectSort 
,ShellSort, QuickSort, HeapSort, MergeSort. 
No presente trabalho seráapresentado a implementação e os testes do método QuickSort. 
 
DESENVOLVIMENTO 
O trabalho consiste em criar um programa para ordenar por idade uma lista contendo o nome, a 
idade e o salário de 1000 funcionários, exibindo também a media dos salários de acordo com a 
faixa etária dos funcionários. Obrigatoriamente o método utilizado foi o QuickSort. 
 Abaixo segue o enunciado do Trabalho. 
 
 
 
 
 
 
 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
Considerações sobre o QuickSort. 
 Adequado para coleções médias e grandes 
 O desempenho do método é o melhor na maioria das vezes (caso médio) 
 Adota a estratégia de divisão e conquista 
 Existem variações para o funcionamento do método 
 Entendimento e desenvolvimento não são triviais 
É o algoritmo mais rápido que se conhece entre os de ordenação interna parauma ampla variedade 
de situações. Foi escrito em 1960 e publicado em 1962 por C.A. R.Hoare após vários refinamentos 
[2]. Porém em raras instâncias especiais ele é lento [3]. Adotando a estratégia Dividir para 
conquistar o funcionamento resume-se a dividir o problema de ordenar um vetor de n posições em 
dois outros menores [2]. 
Funcionamento 1° Caso: 
1 – Escolha um elemento da lista, denominado PIVÔ (Normalmente o pivô fica no meio da 
coleção ou sub coleção). 
2 – Comparem todos os elementos da coleção colocando os menores valores à esquerda e os 
maiores à direita (No fim deste processo o pivô estará em sua posição final e haverá duas sub 
coleções não ordenadas). Essa operação é chamada de partição. 
3 - Com as sub coleções refazer os passos. 
Funcionamento 2° Caso: 
1° O Pivô será o elemento à esquerda da coleção ou sub coleção 
2° coloque um índice no inicio da lista e o outro no final do vetor 
3° O índice final movimentará para o sentido inicial da lista (←)quando a comparação “valor 
MENOR que o pivô” for FALSA, o índice inicial movimentará para o sentido final da lista (→) 
quando a comparação “valor MAIOR que o pivô também for FALSA”. Quando a resposta da 
comparação é VERDADEIRA, troca de posição e muda o índice que está movimentado. 
4° Repita a operação para as suas coleções. 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
Explicação do Código 
Estrutura 
Foi criada uma estrutura chamada de RH para que se pudesse ter dentro de 
um único tipo (Trh) todas as variáveis relacionadas com os funcionários: as 
variáveis nome, idade e sal (salário). E variáveis globais que serão usadas e 
partes diferentes do código. 
Programa Principal 
No programa principal é 
incluído um cabeçalho que 
contem as bibliotecas e as 
funções. Os ponteiros ARQ e r 
irão receber o endereço dos 
arquivos, o primeiro (*ARQ) é 
para leitura da lista de 
funcionários, contendo nome, 
idade e salario. O segundo (*r) 
abre para escrita o arquivo que 
deverá ficar a lista ordenada. 
As variáveis ini, fim e tmili são 
para calcular o tempo de 
execução da função quickSort 
A função imprime_arq() irá 
imprimir o arquivo 
desordenado. 
 
 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
 
As funções quickSort_Cresc() e quickSort_dec() ordenam o vetor de modo crescente e decrescente 
respectivamente, e a função imprime_arq2()imprime o arquivo ordenado, exibindo a idade e o 
salario. A função Media_idade() exibe a media de acordo com a faixa etária. 
A função fclose() fecha os arquivos. O código será eexecutado ate que o usuário digite 0 para sair. 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
Funções 
QuickSort 
A função recebe como parâmetros 
um ponteiro do tipo Trh, para ter 
acesso a estrutura RH, e dois inteiros 
(esquerda e direita) que se refere as 
posições dos elementos a direita e 
esquerda do vetor. As variáveis x e y 
são para comparar os elementos do 
vetor, onde x representa o pivô e y a 
variável auxiliar. 
A variável auxiliar (x) recebe o 
elemento que será o pivô, que fica 
aproximadamente no meio do vetor. 
O vetor é percorrido tanto do lado 
direito quanto do lado esquerdo. 
A troca ocorre quando a maior idade 
é encontrada, e junto com ela o 
salario. 
Usando a ideia de recursividades, a 
função chama si mesma ate que o 
todo o vetor esteja ordenado, 
comparando quem é o maior. Isso na 
função para ordenar em ordem 
decrescente. 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
 
já a função para ordenar em 
ordem crescente. O valor 
procurado é o menor. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
Imprime 
 
 
As funções para exibir as informações na tela são: imprime_arq() e imprime_arq2(): 
imprime_arq()–recebeo endereço do arquivo e o vetor do tipo Trh para se ter acesso a estrutura. 
O arquivo é percorrido ate o final, as strings são guardadas dentro de vetor[i].nome, os inteiros 
dentro de vetor[i].idade, e os números reais dentro de vetor[i].sal. A medida que essas variáveis 
da estrutura RH são carregadas, elas também são impressas na tela. 
imprime_arq2() – o funcionamento é praticamente igual, ao da função anterior, a diferença esta no 
fato de que dessa vez o vetor esta ordenado, e só será exibido a idade e o salario. 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
Media 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A funçãoMedia_idade() recebe por parâmetro 
vetor do tipo Trh para que os valores da 
variável idade possam ser acessados e 
comparados. A medida que o vetor é 
percorrido, contadores vão sendo 
incrementados, assim como o total do salario 
para que a media dos salários possa ser 
calculadadentro de cada faixa etária. 
Calculada a media ela é exibida na tela. 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
RESULTADO 
O QuickSort é considerado o método mais eficiente e é altamente recomendável para arquivos 
grandes. Quanto mais o vetor estiver desordenado, maior será sua vantagem em relação aos outros 
métodos. Pelo tamanho do vetor usado no trabalho, ser um vetor considerado pequeno, o tempo 
de execução dele acaba por se pequeno também. 
 
CONLUSÃO 
Apesar de ser aparentemente simples, a implementação o código deste trabalho apresentou alguns 
erros, os quais não conseguimos corrigir. Primeiro, mesmo ordenando idade e salario, não 
conseguimos fazer com que o nome acompanhasse a ordenação. Por isso decidimos exibir apenas 
a idade e o salário. E segundo, não conseguimos passar o vetor ordenado para o arquivo 2.txt. O 
trecho do código abaixo deveria escrever no arquivo 2.txt o vetor ordenado, no entanto, ele só 
funciona se for colocado 
antes da função 
imprime_arq2(). Se ele for 
colocado em qualquer lugar 
depois da função imprime_arq2(). Ele não escreve nada no arquivo 2. Ate a conclusão deste 
trabalho, mesmo com as orientações que nos foram passada - ao enviarmos o código para o 
professor Wanderson – não conseguimos corrigir esses problemas. 
 
 
 
 
 
 
 
 
 
 
FIC – Faculdades Integradas de Caratinga 
Ciência da Computação, autoriz. MEC, portaria 585, de 26/06/98 
Laboratório de Ordenação e Pesquisa Prof. Wanderson Miranda 
Ordenação e Pesquisa Prof. Bruno Becattini 
Grupo: Bruna Cristine, ClaudioMonteiro, DjullyFavia, Grace Kelly 
3º Período – Ciências da Computação 
REFERENCIAS BIBLIOGRAFICAS 
 
[1] ZIVIANI, Nivio. Projeto de Algoritmos com implementação em C++ e Java. 
Disponível em:<http://www2.dcc.ufmg.br/livros/algoritmos-java/transparencias.php> 
Acessado em: 26 Mar 2015 
 
[2] QUICKSORT 
Disponível em:<http://pt.wikipedia.org/wiki/Quicksort> 
Acessado em: 26 Mar 2015 
 
[3] FEOFILOFF ,PauloProjeto de algoritmos: Quicksort, 1998. 
Disponível em:<http://www.ime.usp.br/~pf/algoritmos/aulas/quick.html> 
Acessado em: 26 Mar 2015