Tarefa 01 Algoritmos de Ordenação

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

UFAM - UNIVERSIDADE FEDERAL DO AMAZONAS 
FT - FACULDADE DE TECNOLOGIA 
ENGENHARIA DA COMPUTAÇÃO 
 
 
 
 
 
 
 
MÁRIO HIROTOSHI SUGAI JÚNIOR 
 
 
 
 
 
TRABALHO 1: ALGORITMOS DE ORDENAÇÃO 
 
 
 
 
 
 
 
 
 
MANAUS,AM 
2016 
MÁRIO HIROTOSHI SUGAI JÚNIOR 
 
 
 
 
 
 
 
 
 
 
TRABALHO 1: ALGORITMOS DE ORDENAÇÃO 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
MANAUS, AM 
2016 
Trabalho de aproveitamento para a 
disciplina de Algoritmos e Estruturas de 
Dados I, ministrado pelo Professor Edson 
Nascimento, para o curso de Engenharia 
da Computação, na Universidade Federal 
do Amazonas. 
1. IMPLEMENTAÇÃO 
 
 ORDENAÇÃO LINEAR 
 
 O Programa, ao ser executado, está encarregado de imprimir na tela 
o vetor original. Este, por sua vez, contém 100.000 (cem mil) posições, 
que serão preenchidas com valores aleatórios que irão variar entre 0 
e 999. 
 Após isso, será iniciado na tela o processo de ordenação linear deste 
vetor. 
 A função responsável por ordenar o vetor é do tipo void e chama-se 
ordena, esta, por sua vez, recebe como argumentos o vetor original e 
o tamanho do mesmo. 
 Com o auxílio de duas variáveis contadoras (contadora1 e 
contadora2) do tipo int, uma varíavel chamada proximo, uma função 
envolvendo ponteiros chamada troca e de dois ciclos de repetição do 
tipo while, a função seguirá para o processo de ordenação que será 
melhor descrito no segundo tópico. 
 Após ordenar todos os valores, a função principal irá imprimir o mesmo 
vetor só que agora com a sua nova faceta, ordenada. 
 Ao fim da ordenação, será impresso a frequência com que cada 
número apareceu aleatoriamente no vetor original (e 
consequentemente, no mesmo quando este foi ordenado), tudo isto 
feito com uma função do tipo int chamada de frequencia. 
 Após todos estes processos, o programa estará finalizado. 
 
o FUNÇÕES UTILIZADAS 
 
 void troca (int *x, int *y) 
Função encarregada do processo de permutação entre os valores contidos no 
vetor com o auxílio de uma variável temporária chamada temp, é chamada e utilizada 
dentro de um laço de repetição na subseguinte função: 
 
 void ordena (int vetor[], int tam) 
Recebendo um vetor e o tamanho do mesmo como argumento e utilizando-se 
de três variáveis e um função de auxílio, esta função está encarregada de ordenar o 
vetor original gerado a partir de números aleatórios. O Ciclo de repetição externo, utiliza 
como condição a variável contadora2 ser menor do que o valor de tam que é a variável 
responsável por guardar o valor do tamanho do vetor original. Dentro deste laço, a 
variável contadora1 tem o seu valor setado para 0 (zero) e há o incremento da variável 
contadora2, porém este só se dá após a saída do segundo ciclo de repetição, o mais 
interno, que possui como condição que a contadora1 seja menor do que tam. O 
Restante do processo será melhor abordado no tópico 2. Esta função tem a sua 
chamada ocorrendo dentro da função principal, a função main. 
 
 int frequencia (int x,int vetor [],int tam) 
Esta função cujo a tarefa principal é retornar uma variável que armazene a 
quantidade de vezes que um número aparece em um dado vetor, a mesma recebe três 
argumentos do tipo int, sendo estes o número a ser encontrado, expresso pela 
variável x, o vetor no qual deseja-se realizar a busca e também a variável que armazena 
o valor deste do tamanho deste mesmo vetor. Esta função é chamada na função 
principal logo após o uso da função ordena. 
 
 rand e srand 
A função rand se faz nativa da biblioteca stdlib.h da linguagem C, e possui 
como objetivo a geração de uma sequência de números aleatórios, porém, esta 
apresenta um pequeno problema para desenvolvedores, e este problema está 
relacionado ao fato de que para esta função funcionar ela necessita de um valor inicial 
chamado de “semente”. Se nenhum valor for passado, esta assume um valor constante, 
com este valor assumido no programa, a sequência gerada sempre será a mesma para 
todas as execuções do programa. Aí que entra a função srand que faz com que, ao 
inicializarmos a função rand com um valor semente, produza-se um valor realmente 
aleatório dentro do intervalo solicitado a cada execução do programa. Esta função se 
baseia no número de segundos passados desde 00:00:00 UTC de 1 de Janeiro de 1970, 
por isso apresentam-se valores tão difíceis de se repetirem a cada execução do 
programa (já que não se consegue executar o mesmo programa duas vezes no mesmo 
segundo). A função srand se faz presente na biblioteca time.h e foi chamada durante 
a geração do vetor de números aleatórios ainda na função principal. 
 
 
 
 
 
 
 
 
 
 
 ORDENAÇÃO LOGARÍTIMICA 
 
 O Programa ao ser executado acaba por retornar exatamente o primeiro, 
utilizando-se, inclusive, das funções montadas da mesma forma, com 
excessão da função principal main que realiza a maior das tarefas, a função 
ordena. 
 A Grande – e gritante – diferença entre estas duas é claramente o tempo de 
execução. Com o método de ordenação em tempo linear, temos que esperar 
um determinado tempo para haver o retorno do vetor totalmente ordenado, o 
que torna-se bem perceptível para o nosso caso em particular, aonde 
estamos buscando e ordenando (e ainda declarando a frequência das 
ocorrências) de 100.000 (cem mil) números. Em contrapartida, a ordenação 
logarítimica é surpreendentemente quase que instantânea, mesmo 
trantando-se de cem mil números, apresentando resultados surpreendentes 
em um deveras curto tempo de execução. 
 O Algoritmo e o código foram baseados no método de ordenação conhecido 
mundialmente como Quick Sort. Este foi desenvolvido por C.A.R. Hoare em 
1960 quando ainda estudando, em uma visita a Universidade de Moscou. 
 Assim como nosso algoritmo para o método de ordenação em tempo linear, 
este trata-se de um algoritmo de ordenação por comparação. 
 Este algoritmo baseia-se no método de divisão e conquista recursiva. 
 
o FUNÇÕES UTILIZADAS 
Este algoritmo de ordenação, em sua implementação, valeu-se praticamente das 
mesmas funções utilizadas e já explanadas na descrição da implementação do 
algoritmo de ordenação linear, sendo estas rand, srand, troca, ordena e 
frequencia. Porém, as maiores diferenças estão na descrição da função main e 
principlamente da função ordena. 
 void ordena (int *vetor, int ladoEsquerdo, int ladoDireito) 
A tarefa principal desta função continua a ser mesma, mas como bem pode-se 
perceber, agora a mesma está a receber três argumentos, sendo estes conteúdo do 
endereço de memória contido em vetor e como melhor será descrito no tópico 2, o 
algoritmo de Divisão e Conquista, por recursão, acaba divindo o problema em menores 
problemas até conseguir resolver em escala do micro para o macro, e é nisto que as 
váriaveis do tipo int ladoEsquerdo e ladoDireito acabam por trabalhar. Mesmo 
sendo recursiva o código desta função acabou ficando um pouco maior que o em tempo 
linear porém isso a execução do código é visivelmente mais fluída e rápida. 
 
 
 
 
 
 
2. LÓGICA DE PROGRAMAÇÃO 
 
 ORDENAÇÃO LINEAR 
É muito importante ao iniciar o código, fazer o algoritmo já tendo em mente todas 
as variáveis e funções auxiliares que virão a ser utilizadas. Ao declarar o vetor original, 
determinar o tamanho dele como uma variável é fundamental para o funcionamento do 
nosso algoritmo quando este for ser implementado, uma vez que, dentro dos laços de 
repetição, faz-se necessário que as variáveis auxiliares caminhem até chegarem 
próximas deste tamanho. 
Para criar o vetor
original e preencher o mesmo com os valores aleatórios, foi 
necessário utilizar um ciclo de repetição do tipo while. Destro deste ciclo, o vetor começa 
a ser preenchido a cada posição através da função responsável por gerar números 
randômicos, quando estivermos com o nosso vetor aleatório totalmente preenchido, sai-
se do ciclo. 
E assim, chamamos a função responsável pela ordenação e o que esta fará? 
Bem, utilizando um ciclo dentro de outro ciclo, a variável “contadora” irá ter o seu valor 
setado para 0 (zero), e uma outra variável chamada “próxima” será sempre igual ao 
valor da “contadora” acrescido de 1 (um). Dentro do ciclo mais interno, que possui como 
condição o valor da variável “contadora” fosse menor do que o número de posições do 
vetor – o que mais tarde pôde ser alterado, de forma a ser explicado mais posteriormente 
-, tínhamos uma condição que diz que: Se o valor de “contadora” for maior do que o 
valor do próximo, faz-se uma permutação – uma troca, realizada através de uma função 
auxiliar que pode ser criada através do uso e manuseio de ponteiros – entre os valores 
presentes nos vetores de índice “contadora” e “próximo”, respectivamente. Ao fim do 
ciclo, ocorre o incremento da variável contadora (e por consequência, de “próximo” 
também). E assim, “contadora” passaria para a segunda posição do vetor, ou ao vetor 
de índice 1 (um), e “próximo” iria passar a ser a terceira posição do vetor. 
Ao chegar na última posição do vetor, o que ocorre: a nossa contadora irá ter 
percorrido todo o vetor uma vez e assim, provavelmente (dependendo dos valores 
gerados) esta não estará ordenada. O que deve ser feito então, é a condição do ciclo 
externo, que com uma segunda contadora, irá fazer com que este vetor seja percorrido 
até estar totalmente ordenado. Sempre que o primeiro ciclo for concluído, o valor de 
“contadora” será setado novamente a zero, dando início mais uma vez ao ciclo e 
acrescendo o valor de contadora. Ao se ordenar, o primeiro ciclo não terá sido acessado 
e assim, saindo também do segundo ciclo e retornando o vetor ordenado. 
Após pequenos testes, pode ser percebido que este método encontra o n-ésimo 
maior número do seu vetor, isolando-o a direita (demonstrado no algoritmo no próximo 
tópico) e assim, para polpar esforço da memória e ter aproveitamento de tempo, pode-
se setar o valor do índice até aonde o vetor será percorrido, subtraindo um do mesmo a 
cada “percorrida”. Por exemplo: Dado um vetor com dez posições, ao percorrermos este 
uma vez, iremos encontrar o valor mais alto de todo o vetor, e assim, este será isolado 
na última posição do vetor após todas as permutações dentro do ciclo. Ao iniciar o ciclo 
novamente, a “contadora” não precisa fazer comparações até a última posição do vetor, 
ou seja, ao percorrer pela segunda vez, a contadora pode ir até a penúltimo posição do 
vetor (no caso, a nona), na terceira vez, até a antepenúltima (oitava) e assim por diante, 
até que dadas as corretas permutações e também número de vezes que esta percorreu 
o vetor, este estará ordenado em até menos passos do que se esperava inicialmente. 
Este processo provou-se análogo tanto para dez quanto para n números, aonde 
n Є Z*. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 MÉTODO LOGARÍTIMICO 
Utilizando-se do método conhecido como Quicksort, foi possível resolver de 
forma mais dinâmica os problemas de ordenação de vetores. 
O Quicksort baseia-se no método de divisão e conquista, aonde a partir da 
divisão do vetor através em duas partes, adotando um elemento central, aonde, antes 
dele teremos 50% dos elementos e após ele, 50% de todos os elementos do vetor – 
funcionando de maneira similar a uma mediana. A este elemento central damos o nome 
de pivô e utilizar os elementos ao lado esquerdo e ao lado direito do pivô de forma a 
ordenar da forma mais ótima estes números, utilizando-se da recursão da mesma 
função várias vezes. 
De forma a encontra este pivô, pegamos o número total de elementos do vetor, 
somamos a 1 e dividimos por 2, como pode ser visto na equação abaixo: 
𝑣𝑒𝑡𝑜𝑟[𝑝𝑖𝑣ô] =
1 + 𝑛
2
 
Aonde n é o número total de elementos a serem analisados naquele vetor. 
Existem duas váriaveis contadoras, uma para a esquerda e outra para a direita 
(a primeira começa a percorrer o vetor do primeiro elemento até o anterior ao pivô de 
forma crescente, e a segunda começa a percorrer do último até o primeiro elemento 
após o pivô de forma decrescente), e assim, iniciam-se as comparações diretamente 
com o vetor. 
Seleciona-se o primeiro elemento do lado esquerdo ao pivô e pergunta-se se 
este é menor do que o pivô, em caso de resposta afirmativa, seleciona-se o segundo 
elemento do lado esquerdo ao pivô e faz-se a comparação novamente, em caso de 
resposta negativa, seleciona-se o último elemento do lado direito ao pivô e pergunta-se 
se este é maior do que o pivô, em caso de resposta afirmativa, seleciona-se o penúltmo 
elemento do lado direito ao pivô e faz-se novamente esta comparação, em caso de 
resposta negativa, ocorre a permutação entre este elemento e aquele que estava 
selecionado ao lado esquerdo do pivô. 
Generalizando-se, a troca ocorre sempre que tivermos um “não” para as duas 
comparações (se o elemento a esquerda é menor e se o elemento a direita é maior), 
mas, em caso de haver um não e um sim, ou vice-versa, o que ocorre: o pivô será 
permutado com o elemento que recebeu um “não” como resposta. Portanto, a partir 
disto, somos capazes de deduzir que o melhor dos casos para a ordenação através do 
quicksort é quando o pivô já é o elemento central do vetor ordenado, o que diminui muito 
mais a quantidade de comparações a serem feitas, poupando-se tempo e memória. 
Quando temos a situação de todos os elementos do lado esquerdo serem 
menores do que o pivô e todos os elementos do lado direito serem maiores do que o 
pivô, chegamos ao ponto em que o pivô original é “deixado de lado” e surge aqui, o “pulo 
do gato”. 
A recursão. Chama-se novamente a função para o lado esquerdo ao pivô e para 
o lado direito ao pivô, gerando um pivô para cada uma e assim havendo todas as 
comparações novamente. Este processo deve ser repetido até o momento em que 
tenhamos apenas três elementos a serem analisados e após as – se necessárias – 
permutações, acabamos com o vetor todo ordenado, porém “fragmentado”, ou seja, 
divido. 
 Então, vem a parte da “conquista” que será o momento de unir todos os 
elementos novamente ao vetor original, e quando o fizermos, teremos o vetor totalmente 
ordenado. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3. DESENVOLVIMENTO TEÓRICO 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Na página seguinte pode ser visto o algoritmo utilizado na construação 
da função FREQUÊNCIA. Esta, por sua vez, é responsável por informar o 
número de ocorrências de determinado número em um vetor. Solicitado em 
sala de aula no dia 21 de Outubro de 2016.