Os algoritmos desenvolvidos (EP1.py) e (EP1_timeit.py) tem por objetivo calcular o tempo que as funções de ordenação levam para ordenar listas de 5000, 10000 e 15000 elementos ou mais (dentro do tempo de 60 segundos de execução), e também calcular quantas buscas são realizadas durante a ordenação dos dados.
Obs: A versão do Python utilizada neste programa é
3.6
Biblioteca que auxilia no manuseio do tempo do sistema, neste programa foi utilizado o método time.time(), ele retorna o tempo em segundos e o método process_time() que retorna a soma do tempo de execução com o tempo de processamento,e os dois foram utilizados para marcar o tempo de execução de cada função de ordenação e de busca.
Biblioteca que permite fazer calculos matematicos e funções de calculo de média por exemplo, neste programa ela foi utilizada para identificar o valor minimo dentro da lista, na função Seleção m = min(v)
Biblioteca que permite a criação de numeros e listas compostas por numeros aleatórios, neste programa ele foi utilizado para gerar numeros aleatórios com o metodo randint e embaralhar a lista com o método shuffle.
Realiza a ordenação de uma lista olhando apenas para a Direita, fazendo comparações de elemento por elemento.
Simulação da ordenação da função Seleção
Realiza a ordenação de uma lista da Esquerda para a Direita, ou seja, pego o elemento da posição atual B e comparo com o elemento seguinte A, caso:
B < A (B for menor que A) -> B continua na mesma posição e eu comparo o próximo da lista com o elemento A
A < B (A for menor que B) -> A troca de posição com B e eu pego o próximo da lista e comparo com o B
Simulação da ordenação da função Inserção
Realiza a ordenação de uma lista A utilizando um vetor auxiliar B, divide a lista em dois e ordena cada pedaço de forma individual, no final reune os dados, formando uma lista novamente tudo isso dentro do vetor B auxiliar, depois é enviado para o vetor original A.
Simulação da ordenação da função MergeSort
Realiza a ordenação de uma lista com a ajuda de um pivô ou numero de referência para auxiliar na ordenação.
Simulação da ordenação da função QuickSort
Função embutida da linguagem Python, realiza a ordenação de uma lista comparando os elementos de maior valor com os elementos seguintes.
Simulação da ordenação do método Sort
No programa também foram utilizados dois algoritmos de busca, para calcular quantas buscas são realizadas durante a ordenação das listas.
Realiza a busca de um elemento dividindo a lista ao meio tendo o ponto maximo, o ponto minimo e o ponto médio (ou ponto central) que é o responsável por buscar o elemento procurado.
Simulação de buscas da função Busca Binária - Buscando pelo numero 714 na demonstração
Realiza a busca de elemento em elemento dentro da lista, até encontrar o valor procurado.
Simulação de buscas da função Busca Sequencial - Buscando pelo numero 714 na demonstração
A função Seleção na teoria é a pior de todas, pois ela demanda muito processamento e tem um tempo de ordenação muito lento, porém no algoritmo, podemos visualizar que a Seleção esta tendo um tempo de execução e quantidade de buscas menores do que a Inserção.
Isto aconteceu porque no código a função Seleção utiliza uma estrutura auxiliar para procura do menor numero, no método min m = min(v), e a estrutura auxiliar utilizada é chamada de HEAP.
Simulação do heap máximo
O Heap Binário é um tipo de estrutura de dados utilizado para ordenar os elementos a medida que são inseridos na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada.
-
Um
heap binárioé uma árvore binária mantida na forma de um vetor. -
O
heapé gerado e mantido no próprio vetor a ser ordenado.
Para uma ordenação crescente, deve ser construído um heap máximo (o maior elemento fica na raiz). Para uma ordenação decrescente, deve ser construído um heap mínimo (o menor elemento fica na raiz).
- Auxilio do Professor Fernando Masanori
 |
Bruna Larissa Clemente Gomes
3º Semestre - Análise e Desenvolvimento de Sistemas-FATEC São José dos Campos 2020
 |