APS- ORDENAÇÃO DE DADOS

Prévia do material em texto

�
Sumário
Introdução e Objetivo do Trabalho	 3
2.	Referencial Teórico								 5
3.	Desenvolvimento								 12
Resultados e discussão							 21
Considerações finais							 22
Referências bibliográficas							 24
Anexos - Código fonte							 26 
	
�
1 Introdução e Objetivo
Ordenar indica o processo de rearranjar um conjunto de objetos ou informações em uma ordem ascendente ou descendente. A atividade de colocar as coisas em ordem está presente na maioria das aplicações em que os objetos e informações armazenados precisam ser pesquisados e recuperados.
O objetivo principal da ordenação é facilitar a recuperação posterior de itens do conjunto ordenado. Imagine como seria difícil utilizar um catálogo telefônico se os nomes das pessoas não estivessem listados em ordem alfabética. O mesmo pode ser dito com relação a dicionários, índices de livros, folhas de pagamento, contas bancárias, tabelas, arquivos e outros materiais organizados alfabeticamente, portanto, evidencia-se que a conveniência de usar dados ordenados é inquestionável. Os tipos de ordenação mais usados conhecidos são: Ordenação por troca, Ordenação por inserção, Ordenação por seleção, entre outros.
	Em ordenação por troca existem os algoritmos: BubbleSort (método da bolha) e QuickSort (método da troca e partição); Na ordenação por inserção, existem os algoritmos: InsertionSort (método da inserção direta) e BinaryInsertionSort (método da inserção direta binária); Na ordenação por seleção, os algoritmos são: SelectionSort (método da seleção direta) e HeapSort (método da seleção em árvore). Existem ouros métodos como o: MergeSort (método da intercalação) e o BucketSort (método da distribuição de chave) (DEVMEDIA, 2012).
Cada um desses algoritmos faz a ordenação de maneiras diferentes, possuindo suas 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. 
	Para tornar a comparação independente da máquina, certas propriedades críticas dos algoritmos de ordenação precisam ser definidas quando comparados, como o número de comparações e o número de movimentos de dados. Para ordenar um conjunto de dados, eles têm que ser comparados e movidos conforme necessário; a eficiência dessas duas operações depende do tamanho do conjunto de dados. 
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 seqüencialmente 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 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 tratam-se do GnomeSort e do BubbleSort, os quais serão implementados na linguagem de programação C/C++.
O capítulo 2 consiste do 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 Algoritmo de Ordenação
Em ciência da computação algoritmo de ordenação, é um algoritmo que coloca os elementos de um vetor, isto é, uma lista por exemplo, de uma dada sequência em uma certa ordem. E pode ocorrer a sua ordenação completa ou parcial. O objetivo da ordenação é facilitar a recuperação dos dados de uma lista.
Um algoritmo de busca eficiente sem dúvidas é de grande valia em inúmeras aplicações pois são muito comuns os casos em que para termos acesso aos dados de maneira eficiente precisamos organizá-los. Corroborando com essa ideia Adam Drozdek (2002, p.404) escreve: [...] A conveniência de usar dados ordenados é inquestionável e precisa ser aplicada também a ciência da computação. Embora um computador possa manipular um caderno de telefones não-ordenado mais fácil e rapidamente do que o ser humano, é extremamente ineficiente ter o computador processando um conjunto desordenado de dados. Frequentemente é necessário ordenar os dados antes do processamento. [...]
Na computação existe uma série de algoritmos que utilizam diferentes técnicas de ordenação para organizar um conjunto de dados, eles são conhecidos como Métodos de Ordenação ou Algoritmos de Ordenação. (TREINAWEB BLOG, 2016)
Os métodos de ordenação se classificam em:
Ordenação Interna: onde todos os elementos a serem ordenados cabem na memória principal e qualquer registro pode ser imediatamente acessado.
Ordenação Externa: onde os elementos a serem ordenados não cabem na memória principal e os registros são acessados sequencialmente ou em grandes blocos.
Dentro da ordenação interna temos os Métodos Simples e os Métodos Eficientes:
Métodos Simples:
Os métodos simples são adequados para pequenos vetores, são programas pequenos e fáceis de entender. Possuem complexidade C(n) = O(n²), ou seja, requerem O(n²) comparações. Exemplos: InsertionSort, SelectionSort, BubbleSort, CombSort. Nos algoritmos de ordenação as medidas de complexidade relevantes são:
Número de comparações C(n) entre chaves.
Número de movimentações M(n) dos registros dos vetores.
Onde n é o número de registros.
Métodos Eficientes:
Os métodos eficientes são mais complexos nos detalhes, requerem um número menor de comparações. São projetados para trabalhar com uma quantidade maior de dados e possuem complexidade C(n) = O(n log n). Exemplos: QuickSort, MergeSort, ShellSort, HeaSort, RadixSort, GnomeSort, CountingSort, BucketSort, CocktailSort, TimSort.
Existem vários algoritmos de ordenação, mas para este trabalho foram escolhidos para estudo os algoritmos de ordenação: CountingSort, GnomeSort, TreeSort e BubbleSort. E desses serão implementados os algoritmos BubbleSort e GnomeSort. (DEVMEDIA, 2012).
2.2 Algoritmo CountingSort
O CountingSort é um tipo de algoritmo utilizado para ordenar vetores de tipos inteiros onde os valores estão entre 0 e M-1. A ideia é utilizar recipientes para organizar e classificar os dados e então retorna-los. Este tipo de algoritmo faz uso de um vetor auxiliar, onde é feito a separação e numeração das ocorrências dos dados de entrada, a qual os valores do vetor são usados como índices em um outro vetor.
A ideia básica do CountingSort é determinar, para cada entrada x, o número de elementos menor que x. Essa informação pode ser usadapara colocar o elemento x diretamente em sua posição no array de saída. Por exemplo, se há 17 elementos menor que x, então x pertence a posição 18. Esse esquema deve ser ligeiramente modificado quando houver vários elementos com o mesmo valor, uma vez que nós não queremos colocar eles na mesma posição.
A implementação de um algoritmo de CountingSort requer várias operações, em geral são usadas as seguintes etapas:
Cria cnt[M+1] e b[max N]
Inicializa todas as posições de cnt a 0.
Percorre o vector a e, para cada posição i de a faz cnt[a[i]-1]++ o que faz com que, no final, cada posição i de cnt contem o nº de vezes que a chave i-1 aparece em a.
Acumula em cada elemento de cnt o elemento somado ao elemento anterior: cnt[i] indica a posição ordenada do primeiro elemento de chave i.
Guarda em b os valores de a ordenados de acordo com b[cnt[a[i]++]=a[i]
Copia b para a.
Counting-Sort trabalha como uma contadora de ocorrências dentro de um programa, especificamente dentro de um vetor. Quando determinado vetor tem números repetidos, números únicos e números que não existem um outro vetor indica a quantidade de ocorrências.
2.2.1 Complexidade 
	A complexidade do algoritmo CountingSort é de que ele não faz as comparações entre elementos de A. Sua complexidade deve ser medida em função do número das outras operações, aritméticas, atribuições, etc. A complexidade do CountingSort é O(n + k). Quando k pertencente à O(n), ele tem complexidade O(n).
2.2.2 Desvantagem	
	
	Esta implementação tem a desvantagem de precisar de vetores auxiliares. O CountingSort ordena exclusivamente números inteiros pelo fato de seus valores servirem como índices no vetor de contagem.
2.3 Algoritmo BubbleSort
Bubble Sort, ou ordenação por flutuação, é um algoritmo de ordenação que pode ser aplicado em Arrays e Listas dinâmicas. Se o objetivo é ordenar os valores em forma decrescente, então, a posição atual é comparada com a próxima posição e, se a posição atual for maior que a posição posterior, é realizada a troca dos valores nessa posição. Caso contrário, não é realizada a troca, apenas passa-se para o próximo par de comparações. 
Se o objetivo é ordenar os valores em forma crescente, então, a posição atual é comparada com a próxima posição e, se a posição atual for menor que a posição posterior, é realizada a troca. Caso contrário, a troca não é feita e passa-se para o próximo par de comparação.
Um array ou lista pode estar já ordenado no momento em que se solicita a ordenação, dessa forma, esta situação tem de ser considerada na implementação do algoritmo. 
Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.
Devido essa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.
2.3.1 Complexidade
 	
	A complexidade desse algoritmo é de ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.
Para um vetor de n elementos, n – 1 varreduras são feitas para acertar todos os elementos
Definida pelo número de comparações envolvendo a quantidade de dados do vetor 
Número de comparações: (n - 1) + (n – 2) + ... + 2 + 1 
Complexidade (para qualquer caso): å i = 1 n - 1 i (n - 1) n = 2 Þ O(n2 )
2.3.2 Desvantagem
No melhor cenário, o algoritmo retorna n de operações, n é igual ao tamanho do vetor, porém no pior cenário ele pode retornar n2, ou seja, para uma lista pequena não seria um problema para o processamento, mas vamos imaginar uma lista com mil, dez mil, milhões, realmente o tempo de processamento seria absurdo. Além disso, o método tem custo elevado, mesmo sendo muito simples. 
Por este motivo existem diversos algoritmos para ordenação complexos, porém performáticos. (COISA DE PROGRAMADOR, 2017).
2.4 Algoritmo GnomeSort
Algoritmo similar ao InsertionSort com a diferença que o GnomeSort leva um elemento para sua posição correta, com uma sequencia grande de trocas assim como o BubbleSort.
O algoritmo percorre o vetor comparando seus elementos dois a dois, assim que ele encontra um elemento que está na posição incorreta, ou seja, um número maior antes de um menor, ele troca a posição dos elementos, e volta com este elemento até que encontre o seu respectivo lugar.
2.4.1 Complexidade
	
	O método GnomeSort tem sua complexidade muito simples. Por mais que pareça ter seu algoritmo em O(n), na verdade o tem em O(n²). Esse método não tem aninhamento de loops, ele é todo feito dentro de apenas um ‘while’, não sendo recursivo, (SARBAZI-AZAD, 2000)
2.4.2 Desvantagem
 	É um método também conhecido por “Ordenação estúpida”, por ser lenta para retornar os valores. 
2.5 Algoritmo TreeSort
	TreeSort é um algoritmo de classificação que cria uma árvore de pesquisa binária a partir dos elementos a serem classificados e, em seguida, percorre a árvore (em ordem) para que os elementos saiam na ordem de classificação. Seu uso típico é classificar elementos na ordem em que a entrada é alimentada ao algoritmo: após cada inserção, o conjunto de elementos vistos está disponível em ordem de classificação (GEEKS FOR GEEKS, 2018).
Passos para o algoritmo Tree Sort:
Etapa 1: pegar os elementos inseridos em uma matriz.
Etapa 2: criar uma árvore de pesquisa binária inserindo itens de dados da matriz na árvore de pesquisa binária.
Passo 3: realizar o percurso em ordem na árvore para obter os elementos na ordem de classificação.
2.5.1 Complexidade
	Tem sua complexidade O(n log n) adicionando um item à busca de árvore binária que leva geralmente O(log n) de tempo. No entanto, adicionando n itens irá demorar O(n log n) de tempo.
2.5.2 Desvantagem
	O pior caso de tempo da complexidade do método Tree Sort pode ser aplicado usando uma busca binária auto balanceada. Usando essa busca, a ordenação Tree Sort irá demorar O(n log n) de tempo para organizar os arrays.
	Com a utilização da busca binária não-balanceada, a complexidade é O(N^2).
�
3 Desenvolvimento
Após estudo bibliográfico programei e comparei os algoritmos GnomeSort e BubbleSort. Abaixo podemos ver as telas do programa Dev C++, software no qual os códigos dos métodos de ordenação foram implementados. 
 	Na sequência, temos as telas do programa em execução. Na primeira imagem, podemos ver o menu inicial (onde podemos selecionar a quantidade de dados que desejamos gerar para posteriormente ter sua ordenação feita):
Após a seleção de 5 mil dados, utilizando a opção 2, na próxima tela observamos a etapa da geração de dados:
Temos na sequência, a apresentação dos dados gerados:
Etapa de ordenação dos dados:
Tempo das ordenações Gnome e Bubble, respectivamente:
�
Apresentação dos dados ordenados:
�
4 Resultados e Discussão
Após implementarmos os códigos de ordenação de dados, utilizando os métodos GNOME SORT e BUBBLE SORT, iniciamos as etapas de testes de tempo de execução, a fim de verificarmos a eficácia de cada um dos métodos implementados. 
Os dados foram gerados de forma aleatória no programa, e o tempo de execução só foi contado a partir do momento do inicio da ordenação (o tempo de geração randômica dos dados não foi levado em conta).
Abaixo, segue a tabela com os tempos de execução (em milissegundos) e o tempo médio da ordenação por GNOME SORT, nos testes efetuados por todos os quatro integrantes do grupo, em suas respectivas máquinas, e com todas as quantidades de dados pré-dispostas no programa desenvolvido.
	 	Na tabela abaixo, temos os dados da execução do método Bubble Sort.
�
 	Como podemos observar, após análise das tabelas, o método BUBBLE SORT se provou mais eficaz que o método GNOME SORT, apresentando um tempo menor na execução da ordenação dos dados gerados, diferença essa que pode ser bem observada principalmentequando a ordenação é de uma grande quantidade de dados, como acima de 50.000, por exemplo. 
	Cada integrante do grupo que realizou os testes teve um desempenho único em comparação com os outros integrantes. Podemos observar que o desempenho do programa depende de fatores extras à unicamente programação do código. 
	Mesmo com o mesmo programa sendo executado, podemos observar que o Indivíduo 4 levou mais tempo para a conclusão da ordenação de dados em sua máquina, enquanto os outros integrantes tiveram poucas variações de tempo em cada teste, alternando um melhor desempenho de cada um em cada tipo de teste, dependendo da quantidade de dados gerados para ordenar, o que nos leva novamente à conclusão de que existem outros fatores que causam impacto no desempenho, como por exemplo, o hardware da máquina utilizada e a execução em segundo plano de outros programas em cada computador.
	Encontramos dificuldades na forma de implementar a medição do tempo de ordenação dos dados, e tivemos que retomar as pesquisas na programação em linguagem C para encontrarmos a melhor maneira para conseguirmos o desejado.�
5 Considerações Finais
Com o estudo dos diferentes tipos de algoritmos de ordenação descritos nesse trabalho e com os resultados obtidos nos testes realizados com os métodos de ordenação, o grupo pode concluir que as operações de ordenação de dados são de suma importância para sistemas computacionais e a escolha do método mais eficiente tem grande impacto no desempenho de uma determinada aplicação. A distribuição dos dados de maneira organizada facilita o acesso e a recuperação de dados armazenados anteriormente em uma aplicação. Durante os estudos fomos capazes de apontar qual entre os métodos de ordenação escolhidos apresentou melhor desempenho na ordenação dos elementos de um vetor utilizando como parâmetro o número de iterações realizadas, considerando a quantidade de dados e o tempo de execução. 
Com isso, finalizamos, dizendo que os resultados dos testes refletem com precisão o que já fora escrito anteriormente por outros autores sobre o desempenho dos métodos estudados neste trabalho.
�
Referências Bibliográficas
AZEREDO, Paulo A.. Métodos de Classificação de Dados e Análise de suas Complexidades. Rio de Janeiro: Campus, 1996
BAASE, Sara. Computer Algorithms: Introduction to Design and Analysis (em inglês). 2ª ed. Reading, Massachusetts: Addison-Wesley, 1988. 53 p
CARDOSO, Rafael. Algoritmos de ordenação em CSharp. Disponível em: <https://raphaelcardoso.com.br/algoritmos-de-ordenacao-em-csharp/#more-4898> Acesso em Outubro de 2018.
CARVALHO, Cid. Ordenação Linear, 2011. Disponível em: <http://www.ic.unicamp.br/~zanoni/mo417/2011/aulas/handout/05-ordenacao-linear.pdf> Acesso em: Outubro de 2018.
COISA DE PROGRAMADOR. Algoritmo de Ordenação BubbleSort. Disponível em: <https://www.coisadeprogramador.com.br/algoritmos-ordenacao-bubble-sort/>. Acesso em: Outubro de 2018.
CORMEMN, T.H.;Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos. Tradução da 2ª edição americana Teoria e Prática. 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 2018.
DROZDEK, A. Estruturas de dados e algoritmos em C++. 1a ed.São Paulo-SP: Cenage Learnig, 2009.
EMBARCADOS. Algoritmo de Ordenação BubbleSort. Disponível em: <https://www.embarcados.com.br/algoritmos-de-ordenacao-bubble-sort/>. Acesso em: Outubro de 2018.
GEEKS FOR GEEKS. TreeSort. Disponível em: <https://www.geeksforgeeks.org/tree-sort/> Acesso em: Outubro de 2018.
GEEKS FOR GEEKS. Cartesian Tree Sorting. Disponível em: <https://www.geeksforgeeks.org/cartesian-tree-sorting/>. Acesso em: Outubro de 2018.
MELLO, R.S. Ordenação de Dados, 2002. Disponível em: <http://www.inf.uri.com.br/neilor/apostila-ED2.pdf> Acesso em: Outubro de 2018.
MELLO, Ronaldo. Ordenação de Dados, 2002. Disponível em: <http://www.inf.ufsc.br/~r.mello/ine5384/15-OrdenacaoDados.pdf> Acesso em: Outubro de 2018.
TREINAWEB. Conheça os principais algoritmos de ordenação. Disponível em: <https://www.treinaweb.com.br/blog/conheca-os-principais-algoritmos-de-ordenacao/> Acesso em: Outubro de 2018.
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 2018.
SARBAZI-AZAD, Hamid. Stupid Sort: A new sorting algorithm. Department of Computing Science Newsletter, University of Glasgow, 599:4, 2 October 2000.
WIKIPEDIA. BubbleSort. Disponível em: <https://pt.wikipedia.org/wiki/Bubble_sort> Acesso em: Outubro de 2018.
WIKIPEDIA. GnomeSort. Disponível em: <https://pt.wikipedia.org/wiki/Gnome_sort> Acesso em: Outubro de 2018.
�
Anexos - Código Fonte
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <string.h>
clock_t tInicio, tFim;
int *dadosGerados;
int horas, minutos, segundos, milisegundos;
void geraTempo(int timeMS){
	milisegundos = (int) ((timeMS % 1000) / 100);
	segundos = (int) ((timeMS / 1000) % 60);
	minutos = (int) ((timeMS / (1000 * 60)) % 60);
	horas = (int) ((timeMS / (1000 * 60 * 60)) % 24);
}
void iniciaTempo(){
 tInicio = clock();
}
void finalizaTempo(){
 tFim = clock();
}
int calculaTempo(){
 return (int) ((tFim - tInicio) / (CLOCKS_PER_SEC / 1000));
}
void swap(int *xp, int *yp) {
 int temp = *xp;
 *xp = *yp;
 *yp = temp;
}
void geraDados(int qtde){
 if(qtde <= 0) {
 	memset(dadosGerados, 0, qtde);
	}
 int i = 0;
	memset(dadosGerados, 0, qtde);
 for (i = 0; i < qtde; i++) {
 dadosGerados[i] = rand() % qtde;
 }
}
void imprimeArray(int arr[], int tamanho) {
 int i;
 for (i = 0; i < tamanho; i++) {
 	if(i > 0 && i < tamanho) printf(", ");
 printf("%d", arr[i]);
 }
 printf("\n");
}
int bubbleSort(int arr[], int n) {
	iniciaTempo();
 int i, j;
 for (i = 0; i < (n - 1); i++) {
 for (j = 0; j < (n - i - 1); j++) {
 if (arr[j] > arr[j + 1]) {
 swap(&arr[j], &arr[(j + 1)]);
 }
 }
 }
 finalizaTempo();
 
 return calculaTempo();
}
int gnomeSort(int arr[], int n) {
	iniciaTempo();
 int index = 0;
 while (index < n) {
 if (index == 0) {
 index++;
 }
 if (arr[index] >= arr[(index - 1)]) {
 index++;
 } else {
 swap(&arr[index], &arr[(index - 1)]);
 index--;
 }
 }
 finalizaTempo();
 
 return calculaTempo();
}
int main() {
 char escolha = '0'; 
	int numeroDados = 0, tDuracaoOrdBubble, tDuracaoOrdGnome, *dadosGnome, *dadosBubble;
 while (1 == 1) {
 system("cls");
 
 printf(" -----------------------------------\n");
 printf(" | Escolha uma das opcoes a baixo! |\n");
 printf(" -----------------------------------\n\n");
 printf(" ================= \n");
 printf(" || 1 - 1.000 || \n");
 printf(" || 2 - 5.000 || \n");
 printf(" || 3 - 10.000 || \n");
 printf(" || 4 - 15.000 || \n");
 printf(" || 5 - 20.000 || \n");
 printf(" || 6 - 25.000 || \n");
 printf(" || 7 - 50.000 || \n");printf(" || 8 - 80.000 || \n");
 printf(" || 9 - 100.000 || \n");
 printf(" || 0 - Sair || \n");
 printf(" ================= \n\n");
 scanf("%c", &escolha, 1);
 setbuf(stdin, NULL);
 switch(escolha){
 case '1':
 numeroDados = 1000;
 break;
 case '2':
 numeroDados = 5000;
 break;
 case '3':
 numeroDados = 10000;
 break;
 case '4':
 numeroDados = 15000;
 break;
 case '5':
 numeroDados = 20000;
 break;
 case '6':
 numeroDados = 25000;
 break;
 case '7':
 numeroDados = 50000;
 break;
 case '8':
 numeroDados = 80000;
 break;
 case '9':
 numeroDados = 1000000;
 break;
 default:
 escolha = '0';
 numeroDados = 0;
 break;
 }
 if(numeroDados <= 0) break;
 
 dadosGerados = (int*) malloc(sizeof(int) * numeroDados);
 dadosGnome = (int*) malloc(sizeof(int) * numeroDados);
 dadosBubble = (int*) malloc(sizeof(int) * numeroDados);
 
 system("cls");
 printf("Gerando Array de dados... \n\n");
 geraDados(numeroDados);
 dadosGnome = dadosGerados;
 dadosBubble = dadosGerados;
 printf("Dados gerados... Pressione qualquer tecla para visualizar os dados...\n\n");
 system("pause");
 system("cls");
 printf("Imprimindo Array gerado... \n\n");
 imprimeArray(dadosGerados, numeroDados);
 printf("\n\nPressione qualquer tecla para iniciar as ordenacoes GNOME e BUBBLE...\n\n");
 system("pause");
 
 system("cls");
 printf("Iniciando ordenacoes... \n\n");
 tDuracaoOrdGnome = gnomeSort(dadosGnome, numeroDados);
 tDuracaoOrdBubble = bubbleSort(dadosBubble, numeroDados);
 printf("Ordenacoes concluidas... Pressione qualquer tecla para mostrar o tempo de ordenacao de GNOME e BUBBLE...\n\n");
 system("pause"); 
 
 system("cls");
 geraTempo(tDuracaoOrdGnome);
 printf("Tempo de Ordenacao GNOME: %d:%d:%d.%d (%d MS)", horas, minutos, segundos, milisegundos, tDuracaoOrdGnome);
 geraTempo(tDuracaoOrdBubble);
 printf("\nTempo de Ordenacao BUBBLE: %d:%d:%d.%d (%d MS)", horas, minutos, segundos, milisegundos, tDuracaoOrdBubble);
 printf("\n\nPressione qualquer tecla para mostrar o array ordenado por GNOME...\n\n");
 system("pause"); 
 system("cls");
 printf("Imprimindo Array ordenado por GNOME... \n\n");
 imprimeArray(dadosGnome, numeroDados);
 printf("\n\nPressione qualquer tecla para mostrar o array ordenado por BUBBLE...\n\n");
 system("pause");
 system("cls");
 printf("Imprimindo Array ordenado por BUBBLE... \n\n");
 imprimeArray(dadosBubble, numeroDados);
 printf("\n\nPressione qualquer tecla para continuar o programa...\n\n");
 system("pause");
 }
 
 return 0;
}
 
Universidade Paulista
Ciência da Computação
Atividade Prática Supervisionada
ALGORÍTMOS DE
ORDENAÇÃO DE DADOS
385X
 
Guilherme Henrique Baú �
R.A: A96EFF-8�
�
 
Bauru
2019/1