Buscar

APS Ordenacao

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 29 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 29 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 29 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

22
26
Universidade Paulista
Ciência da computação
Atividade Prática Supervisionada
ALGORÍTMOS DE ORDENAÇÃO DE DADOS
Caio Roberto Tenório da Silva R.A.- F1001E-0
Gabriel Garcia dos Santos R.A.- N44924-1
Geovane Martins de Moraes R.A.- D89594-0
 
Bauru
2020-2
Sumário
1. Introdução e Objetivo do trabalho						3
2. Referencial Teórico									5
2.1	Conceitos sobre Algoritmos de Ordenação					5
2.2 	Algoritmos de Ordenação por Troca (Bubble Sort)				5
2.2.1		Análise de Complexidade 							8
2.2.2 	Bubble Sort Melhorado							9
2.2.2.1	Análise de Complexidade							11
2.3	Algoritmos de Ordenação por inserção (Insertion Sort)			12
2.3.1		Análise de Complexidade 							14
2.4	Algoritmos de Ordenação rápida (Quick Sort)					15
2.4.1		Análise de Complexidade 							16
2.5	Algoritmos de Ordenação por intercalação 					19
3. Desenvolvimento									22
4. Resultados e discussão								26
5. Considerações finais								..
Referências bibliográficas								..
ANEXOS - Código fonte										..
	
1 Introdução e Objetivo do Trabalho
	Ordenação é o processo de arranjar um conjunto de informações semelhantes em uma ordem crescente ou decrescente. Tal processo, está presente na maioria das aplicações em que objetos e informações armazenados precisam ser pesquisados e recuperados. 
	Sua principal função é facilitar a recuperação posterior de itens do conjunto ordenado. Um exemplo, seria um catálogo telefônico. Sem a ordenação dos nomes das pessoas em ordem alfabética, seria muito difícil utilizá-lo. Assim, evidencia-se que a utilização de dados ordenados é inquestionável. 
	Alguns algoritmos podem explorar a ordenação dos dados para operar de maneira mais eficiente, do ponto de vista de desempenho computacional. Para obtermos os dados ordenados, temos basicamente duas alternativas: ou inserimos os elementos na estrutura de dados respeitando a ordenação (dizemos que a ordenação é garantida por construção), ou, a partir de um conjunto de dados já criado, aplicamos um algoritmo para ordenar seus elementos (CELES & RANGEL, 2002). 
	Existem vários algoritmos que fazem a ordenação de maneiras diferentes, possuindo vantagens e desvantagens as quais devem ser consideradas conforme a aplicação que se destinam. Para decidir qual método é o melhor, certos critérios de eficiência precisam ser estabelecidos, e um método para comparar diferentes algoritmos precisa ser selecionado. 
	Os métodos de ordenação são classificados através de sua complexidade (O) e são em geral, classificados em dois grandes grupos: métodos de ordenação interna (vetores) e métodos de ordenação externa (arquivos). Se o arquivo a ser ordenado é pequeno, ou seja, cabe todo na memória principal então o método ordenador é chamado de ordenação interna. Em um método de ordenação interna, qualquer registro pode ser imediatamente acessado. Se o arquivo a ser ordenado não cabe na memória principal e por isso tem de ser armazenado em fita ou disco, então o método de ordenação é chamado de ordenação externa. Em um método de ordenação externa, os registros são acessados sequencialmente ou em grandes blocos. Existem os métodos simples, que são ideais para conjuntos pequenos, requerem O(n2) comparações, produzem programas pequenos e fáceis de entender; e existem métodos eficientes que são adequados para conjuntos maiores, requerem O (n log n) comparações, usam 4 menos comparações e essas comparações são mais complexas nos detalhes (VIANA,2016). 
	O objetivo desse trabalho consiste em estudar os algoritmos de ordenação de dados e toda teoria computacional envolvida. A unidade de medida para efeito de comparação do desempenho dos algoritmos escolhidos e implementados deverá ser o tempo total de ordenação, não contabilizando o tempo de aquisição dos dados, mas somente a ordenação em si. Os algoritmos escolhidos para implementação e comparação neste trabalho trata-se do BubbleSort (método da bolha), do InsertionSort (Inserção) os quais, Bubble Sort e Quick Sort serão implementados na linguagem de programação JAVA. 
O capítulo 2 consiste no referencial teórico. Após o referencial teórico, o capítulo 3 apresenta o desenvolvimento dos algoritmos escolhidos pelo grupo, depois no capítulo 4 os resultados e discussões, isto é, como foram aplicados os testes e sobre o desempenho obtido pelos algoritmos etc. No capítulo 5 o grupo apresentará as considerações finais e o seu entendimento sobre tudo que foi feito. E finalmente as referências para esta pesquisa e o código dos algoritmos desenvolvidos como anexo.
	
	
2 Referencial Teórico	
	
	Este capítulo aborda a teoria envolvida na proposta deste trabalho.
2.1 Conceitos sobre Algoritmos de Ordenação
Algoritmo de ordenação em ciência da computação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem - em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são as numéricas e as lexicográficas (ordem alfabética).
Existem várias razões para se ordenar uma sequência, uma delas é a possibilidade se acessar seus dados de modo mais eficiente. (MARCOS LAUREANO,2012).
Há vários algoritmos de ordenação, mas para este trabalho foram escolhidos para o estudo os algoritmos de ordenação: Bubble Sort, Quick Sort, Insertion Sort, Merge Sort. (DEVMEDIA,2012).
2.2 Algoritmo de ordenação por troca (BUBBLE SORT)
Neste algoritmo de ordenação serão efetuadas comparações entre os dados armazenados em um vetor de tamanho n. Cada elemento de posição “i” será comparado com o elemento de posição i+1, e quando a ordenação procurada (crescente ou decrescente) é encontrada uma troca de posições entre os elementos é feita. Assim, um laço com a quantidade de elementos do vetor será executado (for(j=1; j<=n; j++)), e dentro deste, um outro laço que percorre da primeira a penúltima posição do vetor (for(i=0; i<n-1; i++)). Na próxima página, o algoritmo de BUBBLE SORT será ilustrado, implementando e analisando com o objetivo de ordenar os dados de forma crescente.
A ilustração a seguir mostra a execução do algoritmo BUBBLE SORT na ordenação crescente de um vetor com 5 elementos.
Fonte: GOMES & ARAUJO, 2010
21
Fonte: GOMES & ARAUJO, 2010
2.2.1 Análise de complexidade
O principal trecho de código do algoritmo BUBBLE SORT é aquele que a ordenação realmente é realizada. O trecho é mostrado a seguir.
Fonte: GOMES & ARAUJO, 2010
Em alguns algoritmos de ordenação o fator relevante que determina seu tempo de execução é o número de comparações realizadas. Considerando que o algoritmo foi complementado para um vetor de 5 posições, verifica-se que o número de iterações do primeiro laço é 5. O segundo laço possui 4 iterações, mas como está interno ao primeiro, este será executado 20 vezes (5x4). Logo, o número de comparações (condição SE) realizadas será 20.
Aplicando a mesma ideia sobre um algoritmo com vetor de tamanho n, ele realizara n(n-1) = n^2-n comparações (linha 5). Utilizando uma das notações vistas anteriormente, pode-se dizer que o tempo de execução do algoritmo BUBBLE SORT é “O ou 0” (n^2), pois N^2-N<=C.N^2, C=1, N>=1.
Neste algoritmo não há situações melhores ou piores. Qualquer que seja o vetor de entrada, o algoritmo se comportará da mesma maneira, realizando todas as comparações, mesmo que desnecessárias.
2.2.2 BUBBLE SORT melhorado (1ª Versão)
Neste algoritmo de ordenação serão efetuadas comparações entre os dados armazenados em um vetor de tamanho n. Cada elemento de posição terá comparado com o de posição “i” - 1, e quando a ordenação procurada (crescente ou decrescente) é encontrada, uma troca de posições entre os elementos é feita. Assim, um laço com a quantidade de elementos do vetor menos um será executado (for (j=1;j<n;j++)) e, dentro dele, um outro laço que percorre da última posição à posição j, fazendo com que a posições já ordenadas não sejam mais percorridas (for(i=n-1;1>=j;i--)). Abaixo, a 1° versão melhorada do algoritmode ordenação por troca BUBBLE SORT será ilustrada implementada com o objetivo de ordenar os dados de forma crescente de um vetor com 5 elementos.
Fonte: GOMES & ARAUJO, 2010
2.2.2.1 Análise de complexidade
O trecho desta versão do algoritmo BUBBLE SORT em que ocorre a ordenação é mostrado a seguir.
Fonte: GOMES & ARAUJO, 2010
	Nessa versão, o para da linha 1 será executado n-1 vezes (4). O segundo para, da linha 3, será executado de acordo com o valor de j do primeiro para. Logo, o para da linha 3 será executado 4 vezes para j=i, 3 vezes para j=2, 2 vezes para j=3 e uma vez para j=4. Ou seja, para o vetor de tamanho 5, o número de comparações realizadas (linha 5), que é interna ao para da linha 3, será (4+3+2+1)=10. Considerando um vetor de tamanho n, sendo realizadas ((n-1)+	+3+2+1) comparações . Portanto, o tempo de execução do algoritmo é:
Fonte: GOMES & ARAUJO, 2010
	Para qualquer vetor de entrada, o algoritmo se comporta da mesma maneira.
Veja o gráfico:
Fonte: GOMES & ARAUJO, 2010
2.3 Algoritmo de ordenação por inserção (INSERTION SORT)
Neste algoritmo de ordenação será eleito o segundo número do vetor para iniciar as comparações. Assim os elementos à esquerda do número eleito estão sempre ordenados de forma crescente ou decrescente. Logo um laço com as comparações será executado do segundo elemento ao último, ou seja, na quantidade de vezes igual ao número de elementos do vetor menos um (for(i=i;i<n;i++). Enquanto existirem elementos à esquerda do número eleito para comparações e a posição que atende a ordenação que se busca não for encontrada, o laço será encontrado. O número eleito está na posição i. Os números a esquerda do eleito estão nas posições de i-1 à 0, logo o laço a ser executado será(j=i-i) e (while (j>=0 && elemento [j] > eleito));
Fonte: GOMES & ARAUJO, 2010
	Abaixo, o algoritmo de ordenação por inserção, INSERTION SORT, será ilustrado, implementando e analisando com o objetivo de ordenar os dados de forma crescente.
.
Fonte: GOMES & ARAUJO, 2010
2.3.1 Análise de complexidade
O trecho do algoritmo em que ocorre a ordenação é mostrado a seguir
Fonte: GOMES & ARAUJO, 2010
No algoritmo anterior existem duas estruturas de repetição. A estrutura para executar n-1 vezes, onde n é o tamanho do vetor. A estrutura de repetição “enquanto” será executada a princípio também n-1 vezes, porem dependendo do vetor de entrada nas linhas 5, 7 e 8 podem ser executadas menos vezes.
O pior caso do algoritmo ocorre quando o vetor de entrada possui os elementos na ordem inversa, ou seja, se o vetor está em ordem decrescente e busca-se a ordem crescente. Nesse caso, cada elemento X [ j ] é comparado com cada elemento no subvetor ordenado X [0.. j-1], e então executar-se a linha das comparações (linha 5) j+2 vezes para cada valor de j=0, 1, ..., n-2. Logo o tempo de execução, que ´w o número de comparações é dado pela fórmula:
Fonte: GOMES & ARAUJO, 2010
O melhor caso do algoritmo ocorre quando o vetor de entrada fornecido possui os elementos já ordenados. Para cada j=0, 1, ..., n-2, tem-se que a condição x[j] >eleito na linha 5 é falsa. Então o custo de executar a linha 5 é 1 para cada valor de j e o tempo de execução do melhor caso é T(n)=0(n-1), já que se tem n-1 valores para j.
2.4 Algoritmo de ordenação rápida (QUICK SORT)
Neste algoritmo de ordenação o vetor é particionado em dois por meio de um procedimento recursivo. Essa divisão ocorre até que o vetor fique com apenas um elemento, enquanto os demais ficam ordenados à medida que ocorre o particionamento.
Assim, no algoritmo de ordenação rápida, QUICK SORT, tem-se a técnica da divisão e conquista da seguinte forma:
° Dividir: o vetor X[p..r] é particionado (rearranjado) em dois subvetores não vazios X[p..q] e X[q+1..r] , tais que cada elemento de X[p..q] é menor ou igual a cada elemento de x[q+1..r]. O índice q e calculado como parte do processo de particionamento. Para determinar o índice q, escolhe-se o elemento que se encontra na metade do vetor original, chamando de pivô, e rearranjam-se os elementos do vetor de forma que os que ficarem à esquerda de q são menores (ou iguais) ao pivô e os que ficarem a direita de q são maiores (ou iguais) ao pivô.
° Conquistar, os dois subvetores são ordenados X[p..q] e X[q+1..r] por chamadas recursivas ao QUICK SORT.
° Combinar durante o processo recursivo, os elementos vão sendo condenados no próprio vetor, não exigindo nenhum processamento nesta etapa.
2.4.1 Análise de complexidade
	A seguir na próxima folha a imagem do algoritmo.
Fonte: GOMES & ARAUJO, 2010
A ideia principal do algoritmo de ordenação QUICK SORT é fazer o processo de particionar o vetor em duas partes, realizado pela função partição. 
Nesse procedimento o vetor e particionado na posição j, de forma que todos os elementos do lado esquerdo de j são menores ou iguais ao elemento denominado pivô, e todos os do lado direito são maiores que o pivô. Nesse procedimento, o tempo de execução é limitado pelo tamanho de vetor, no caso n. isso acontece porque para realizar esse particionamento, ele compara os elementos de posição i (cujo valor inicia na primeira posição e vai aumentando) e só da posição j (cujo valor inicia com a última posição e decresce) com o valor pivô. Ou seja, ele compara todos os elementos do vetor com o pivô enquanto os índices atenderem a condição i<j; logo, o procedimento partição realizara O(n) comparações.
O tempo de execução do QUICK SORT depende se o particionamentos e ou não balanceado, o algoritmo executa tão rapidamente quando o MERGE SORT. Se não é balanceado, o algoritmo é tão lento quanto o INSERTION SORT.
O pior caso ocorre quando o procedimento de particionamento produz uma região com n-1 elementos e outra com somente um elemento. Considere que esse particionamento ocorra em todo passo do algoritmo. Como o custo do particionamento é O(n), a recorrência para o tempo de execução do QUICK SORT é:
Fonte: GOMES & ARAUJO, 2010
A recorrência obtida no pior caso pode ser resolvida utilizando o método da expansão telescópica, conforme mostrado a seguir:
Fonte: GOMES & ARAUJO, 2010
Deve-se agora calcular o valor de i para obter-se o tempo final. Considerando que a recursão termina quando se atinge um vetor de tamanho 1(T(1)) e o custo para se ordenar tal vetor é O(1), ocorre no algoritmo do QUICK SORT quando T(n-i)=T(1) ou seja: N – I =1; I = N-1.
Agora, substituindo o valor de i na expressão anterior, obtém-se que
Fonte: GOMES & ARAUJO, 2010
Portanto, o tempo de execução do QUICK SORT no pior caso é O(n^2) para c=2, n=>1.
O melhor caso ocorre quando o procedimento de particionamento produz duas regiões de tamanho n/2. A recorrência então é:
Fonte: GOMES & ARAUJO, 2010
2.5 Algoritmo de ordenação por intercalação (MERGE SORT)
Como o algoritmo QuickSort, o MergeSort é outro exemplo de algoritmo do
tipo divisão e conquista, sendo é um algoritmo de ordenação por intercalação ou segmentação. A ideia básica é a facilidade de criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, o algoritmo divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.
Então, os passos para o algoritmo são: Dividir uma sequência em duas novas sequências; ordenar, recursivamente, cada uma das sequencias (dividindo novamente, quando possível); combinar (merge) as subsequências para obter o resultado.
Fonte: LAUREANO, 2012
A complexidade do algoritmo é dada por n log n em todos os casos. A desvantagem deste algoritmo é precisar de uma lista (vetor) auxiliar para realizar a ordenação, ocasionando em gasto extra de memória, já que a lista auxiliar deve ter o mesmo tamanho da lista original.
Fonte: LAUREANO, 2012
3 Desenvolvimento	
Após estudo bibliográfico, o grupo implementou e comparou os algoritmos Bubble Sort e Insertion Sort
Tela 1 - Apresentação.
	A primeira tela apresenta o tema da APS e os nomes dos participantes quedesenvolveram o trabalho.
Tela 2 - Ordenação.
	A tela 2 é responsável pela criação e composição de uma Array com 100 ou 50000 números, apresentação dos dados em uma Jlist e pela escolha do algoritmo de ordenação que será utilizado.
Tela 3 – Bubble Sort
	O primeiro algoritmo implementado foi o Bubble Sort, a imagem acima, é a tela implementada em Java, responsável pela implementação do algoritmo no projeto. Ela utiliza os números da Array descrita na tela 2 para ordená-los.
Tela 4 – Insertion Sort
	O segundo algoritmo implementado foi o Insertion Sort. A imagem acima, é a tela implementada em Java, responsável pela implementação do algoritmo no projeto. Ela também utiliza os números da Array descrita na tela 2 para ordená-los.
	
 
4 Resultados e Discussão
	O projeto foi testado ................ explique como fez os testes, para demonstrar os diferentes resultados obtidos.
Os resultados foram cronometrados em Milissegundos, de acordo com o tempo da geração da quantia de dados desejada: 1.000, 10.000, 50.000 ou 100.000 dados. 
As figuras 1, 2 e 3, abaixo, representam alguns prints das execuções dos testes feitos.
COLOCAR AS TELAS MOSTRANDO A EXECUÇÃO DOS TESTES COM O TEMPO QUE GASTOU PARA ORDENAR.
6 Considerações Finais
	Concluímos que, com o desenvolvimento do projeto, adquirimos conhecimento de algoritmos de ordenação. E isso facilitou e melhorou nossos estudos referentes as matérias de Estrutura de Dados e Linguagem de Programação Orientada a Objeto, pois nosso projeto foi baseado em JAVA e nas aulas de Estrutura de Dados. 
PRECISA MELHORAR UM POUCO AS CONSIDERAÇÕES FINAIS.
Referências Bibliográficas	
CELES, W; RANGEL, J.L. Apostila de Estruturas de Dados. Rio de Janeiro: PUC, p.14, 2002
DEVMEDIA; Algoritmos de ordenação: análise e comparação, Disponível em:< http://www.devmedia.com.br/articles/viewcomp.asp?comp=28261 > Acesso em: Outubro de 2019.
GOMES, A.F; ARAÚJO, G.S. Estrutura de dados: algoritmos, análise de complexidade e implementações em JAVA E C/C++. São Paulo: Pearson Prentice Hall, p.21-74, 2010.
LAUREANO, M. Estrutura de dados com Algoritmos e C. Rio de Janeiro: Brasport, p.115-117, 2012.
VIANA DANIEL, Conheça os principais algoritmos de ordenação, 2016. Disponível em:<https://www.treinaweb.com.br/blog/conheca-os-principais-algoritmos-de- ordenacao/> Acesso em outubro de 2019.
ANEXOS - Código Fonte
#include<stdio.h>
#include<conio.h>
#
........

Outros materiais