A Ordenação Linear e Logarítmica

[pic 1]

Universidade Federal do Amazonas

Faculdade de Tecnologia

Engenharia da Computação

Brendon Lopes

Guilherme Souza

Raphael Velloso

Trabalho 1 – Ordenação Linear e Logarítmica

Manaus – AM

2016

Valney Marinho do Nascimento Júnior

Brendon Lopes

Trabalho 1 – Ordenação Linear e Logarítmica

Trabalho de aproveitamento para a disciplina

Algoritmo e Estruturas de Dados I, ministrado

                     pelo Professor Edson Nascimento, para o Curso

de Engenharia da Computação, na

Universidade Federal do Amazonas

ORIENTADOR: EDSON NASCIMENTO

Manaus – AM

2016

1. Implementação.

* Em ambos os programas exibirá um vetor com números aleatórios de 0 a 999, sendo que o vetor terá o tamanho de 100000.

* Os dois programas farão a ordenação desse vetor pelos métodos de ordenação Bubble Sort (ordenação linear) e Quick Sort (ordenação logarítmica), além disso apresentarão a frequência dos números, caso haja repetição dos mesmos. Por exemplo, logo no inicio da imagem abaixo tem 10 10, o primeiro 10 é o elemento e o segundo é a sua frequência.

        

1.1 Quick Sort (ordenação logarítmica).

•  Método rápido e eficiente de ordenação.
•  É baseado na ideia de dividir e conquistar.
•  Esta ordenação tem como no início de seu processo pegar um elemento do vetor, chamado pivô, e fazer dele como referência para ordenação de uma parte do vetor.
•  O elemento pivô poderá ser qualquer um, no caso o programa pegará o pivô através de uma operação que é a média das variáveis “incio” e “fim”, que no caso será o meio do vetor. O pivô nem sempre será o mesmo número, pois ele estará dentro de um laço de repetição.
•  A ideia é que todos os elementos menores que o pivô fiquem na sua esquerda e que os maiores elementos fiquem na sua direita.
•  Será feito uma troca quando o lado esquerdo que corresponde o inicio for menor ou igual   ao lado direito que corresponde o fim.
•  Caso não haja mais trocas, as etapas acima ocorrerão novamente em uma chamada recursiva, tendo como alteração o pivô.
•  Será repetido até que ocorra a ordenação.

Funções utilizadas no programa.

- void geravetor(int *vetor);

        Gera uma série de números aleatórios.

- void imprimevetor(int *vetor, int tamanho);

        O vetor será exibido.

- int freq(int *vetor, int num);

        Frequência que um elemento terá.

- void ordenacao(int *vetor, int inicio, int fim);

        Essa será a função do quick sort.

- int main();

        Essa é a função principal na linguagem C.

Bibliotecas utilizadas.

- <stdio.h>

-

-

1.2 Bubble Sort (ordenação linear).

• O algoritmo e implementação irão gerar valores aleatórios entre 0 e 999 para preencher um vetor de 100 mil posições. E exibirá como resultado, ordenado por valor e frequência , um vetor contendo o valor e a frequência com que cada valor aparece no vetor de entrada.
• O programa escrito é lido sequencialmente, então foi escrito primeiro as funções que irei precisar para gerar cada elemento que o programa necessita.
• Primeiro o código vai gerar um vetor que será utilizado em toda o programa, depois vem uma função que verifica a frequencia que um numero ocorre dentro de um vetor, porém ela esta associada a função que imprime o vetor que foi escrita logo em seguida; daí teho uma função que troca os valores de duas posições dentro de um vetor; e por seguinte, uma função que faz uma ordenação inicial, função bola, que utiliza a função troca, e troca os valores de dois elementos do vetor caso o elemento da esquerda seja maior que o elemento da direita ao qual foi comparado; e como a função bola só percorre uma vez o vetor e sempre deixa o elemento de maior valor do vetor na ultima posição do vetor, foi criada uma função, bolinha, que chama a função bola, sempre utilizado o vetor original menos o ultimo elemento, assim ordenando o vetoraté que o ultimo elemento a ser analisado  for igual ao elemento inicial do vetor, assim ordenando ele.
• E todas essas funções são chamadas dentro de main, o programa final. Todas as funções são depedentes entre si para que todo o algoritmo do programa funcione corretamente.

Funções e suas respectivas descrições:

void geraVetor – nessa função que é gerado um vetor de cem mil posições, com elementos aleatórios e dentro de um intervalo aberto de zero a mil.

void freq - função que vai verificar dentro do vetor a frequencia que cada elemento ocorre no vetor.

void imprimeVetor – dentro desta função o vetor gerado no início, em geraVetor, é impresso elemento a elemento e ao lado de cada elemento dele é gerado a sua respectiva frequência.

void troca – função que compara dois valores, e caso o primeiro valor analisado seja maior que o segundo, eles trocam de posição.

...