Relatório Do Projeto Prático

Resumo

Projeto consistem em analisar o tempo que um algoritmo de ordenação leva para ordenar um

conjunto de xentradas.-Implemente do zero todos algoritmos de ordenação (Bubble,

Selection, Insertion, Merge, QuickeHeap)-Utilize uma função para analisar o tempo exato de

cada execução/ordenação.-Realize todos os experimentosde acordo com a planilha exemplo,

variando a quantidade de entradas.-Crie umgráfico a partir da tabela, demonstrando a

quantidade de entradas em relação a cada execução.-Analise os resultados obtidos de cada

conjunto de experimentos e dê o seu parecer porque os tempos de ordenação variaram

seguindo algum padrão (complexidade).

Introdução a Ordenação

A classificação é o processo de colocar elementos de uma coleção em algum tipo de ordem.

Por exemplo, uma lista de palavras pode ser classificada em ordem alfabética ou por

tamanho.

Existem muitos, muitos algoritmos de ordenação que foram desenvolvidos e analisados. Isso

sugere que a classificação é uma área importante de estudo em ciência da computação. A

classificação de um grande número de itens pode exigir uma quantidade substancial de

recursos de computação. Como a pesquisa, a eficiência de um algoritmo de classificação está

relacionada ao número de itens sendo processados.

Para pequenas coleções, um método de classificação complexo pode ser mais problemático

do que vale a pena. A sobrecarga pode estar muito alta. Por outro lado, para coleções

maiores, queremos aproveitar o maior número possível de melhorias.

Pratica

Para a realização da pratica dos algoritmos de ordenação ,utilizei os algoritmos em anexo .

Utilizei um notebook com as seguintes especificações:

Processador Intel® Core™ i3-2375 CPU @1.50 GHz

Memoria (Ram) 4 GB

Sistema Operacional de 64 bits, processador com base em x64 , Windows 10

A linguagem de programação utilizada e C.

O compilador utilizado foi Code::Blocks 17.12

Foi preciso utilizar a biblioteca time.h a qual se encontra o tipo de variável clock_t ,utilizada

para receber o tempo de inicio e final .

Como os algoritmos de bubblesort , seletionsort e insertionsort ,são algoritmos mais lentos

utilizei o array variando de 1000 a 10000 , sendo que foi variando de mil a mil ate chegar a

dez mil .

Pela rapidez dos algoritmos Merge, Quick e Heap ,o computador não conseguiu contabilizar

o tempo ,por ser muito rápido ,sendo assim utilizei o array de 10000 a 100000 ,sendo que foi

variado de dez mil a dez mil ate chegar a cem mil .

Os tempo se encontram em uma planilha em anexo, assim como os gráficos .

Bubble Sort

O algoritmo Bubble Sort anda pelo vetor inteiro ,comparando itens adjacentes e trocando

aqueles que estão fora de ordem .

Vantagens: •A principal vantagem desse algoritmo é que sua implementação é fácil e

conhecida.

•Além disso, no Bubble Sort, os elementos são trocados de lugar sem utilizar armazenamento

temporário, o que faz o requerimento de espaço ser mínimo.

Desvantagens: •Esse algoritmo não é adequado para grandes conjuntos de dados, pois sua

média e a pior das complexidades são de Ο (n2), em que né o número de itens.

Comsiderado o método de classificação mais ineficiente ,por ter que comparar item a item

antes que chegue ao final. Essas comparações desperdiça muito tempo .

Em particular, se durante um passe não houver trocas, então sabemos que a lista deve ser

classificada. O Bubble Sort pode ser modificado para parar mais cedo se descobrir que a lista

foi classificada. Isso significa que, para listas que exigem apenas alguns passos, uma

classificação de bolha pode ter uma vantagem, pois ela reconhecerá a lista classificada e será

interrompida.

No BubbleSort, as comparações n-1 serão feitas na primeira passagem, n-2 na segunda

passagem, n-3 na terceira passagem e assim por diante. Então o número total de comparações

será: Saída: (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1

Soma = n(n-1)/2O(n2)

A principal vantagem do BubbleSorté a simplicidade do algoritmo. A complexidade de

espaço é O(1), porque apenas um espaço de memória adicional é necessário, isto é, para a

variável temp. Além disso, a melhor complexidade de tempo do caso será O(n), é quando a

lista já está ordenada. A seguir estão as complexidades de Tempo e Espaço do algoritmo

Bubble Sort:

•Pior caso do tempo O(n2)

•Melhor complexidade de tempo O(n)

•Complexidade média de tempo O(n2)

•Complexidade de espaço O(1)

Selection