A maior rede de estudos do Brasil

Grátis
42 pág.
APS UNIP 3º E 4º SEMESTRE - COMPUTAÇÃO

Pré-visualização | Página 1 de 4

INSTITUTO DE CIÊNCIAS EXATAS E TECNOLOGIA – ICET
CURSO DE CIÊNCIA DA COMPUTAÇÃO
CHRYSTIAN ARTUR RODRIGUES DE ALMEIDA - F246HD7 
FRANCSICO ÁLISSON COSTA LOPES - T05AIE0
“DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS
APS – ESTRUTURA DE DADOS
DIEGO RODRIGUES
BRASÍLIA/DF
2021/01
Índice
Índice	2
Objetivo	2
Introdução	2
Algoritmo:	2
Algoritmo de Ordenação:	2
Bubble Sort :	2
Selection Sort:	2
Quick Sort:	2
Insertion sort:	2
Referencial Teórico	2
Desenvolvimento	2
Resultados e Discussão	2
Considerações Finais	2
Referencias Bibliográficas	2
Objetivo
O objetivo do trabalho é desenvolver um sistema computacional utilizando algoritmos que irão ordenar 100 mil imagens de satélites de toda região a cada 24 horas utilizando a linguagem de programação PHP da forma mais eficiente possível levando em consideração a utilização de mais de um método de ordenação. O objetivo é usar e comparar os métodos escolhidos para uma análise mais ampla sobre eles.
Os métodos irão catalogar os dados das imagens capturados pelos satélites, em seguida irá ordenar e comparar os desempenhos de cada um
Introdução
Algoritmo:
O algoritmo é uma forma de pensar em uma resolução de problema. Pode ser feito com qualquer sequência de valores ou objetos que tenham uma lógica infinita como por exemplo: língua portuguesa, linguagem C, linguagem Pascal, uma sequência de números, um conjunto de objetos tais como caneta, lápis, borracha. Ou seja, qualquer sequência que possa fornecer uma sequência lógica.
 Um algoritmo pode ser visto como uma receita culinária, ou seja, algo que pode ser seguido como uma passo-a-passo e com os procedimentos necessários para a resolução de um problema, apesar de alguns algoritmos serem bem mais complexos.
Algoritmo de Ordenação:
	Algoritmo de ordenação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem. Em outras palavras faz uma ordenação completa ou parcial. O objetivo de uma ordenação é facilitar a recuperação dos dados de uma lista.
Os algoritmos de ordenação mais utilizados são: Bubble Sort, Selection Sort, Quick Sort e Insertion Sort.
Bubble Sort :
Bubble sort é o algoritmo mais simples, porém o menos eficientes. No algoritmo bubble sort, cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Se o elemento da posição 2 for maior que o da posição 3, eles são trocados de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo pouco eficiente para listas muito grandes. Seguindo um exemplo teórico a seguir:
Selection Sort:
A selection sort funciona de um dos dois jeitos: ou passa o menor valor do vetor para a primeira posição ou o maior valor do vetor para a última posição, e depois o segundo menor valor para a segunda posição e assim sucessivamente, até os últimos dois elementos ou dois primeiros.
Neste tipo de ordenação é selecionado um número a partir do primeiro, este número que foi selecionado é comparado com os números a partir da sua direita, quando encontra um número menor, o número selecionado passa a ocupar a posição do menor número encontrado. Este número encontrado será o próximo número selecionado para continuar, caso não for encontrado nenhum número menor que este selecionado, ele é colocado na posição do primeiro número selecionado, e o próximo número à sua direita será o escolhido para fazer as comparações. Este processo é repetido até a lista estar ordenada.
De qualquer maneira, essa ordenação é excepcionalmente fácil de implementar e garante que itens imediatamente apareçam na localização final uma vez movidos. Algumas pessoas chamam esse tipo de algoritmo de ordenação de comparação local. Segue o exemplo teórico do algoritmo:
Quick Sort:
Quicksort é o algoritmo mais eficiente na ordenação por comparação. Neste algoritmo é selecionado um elemento chamado de pivô, a partir dele a lista é organizada de forma que todos os números a sua esquerda sejam menores e todos os elementos a sua direita sejam maiores. Ao final desse processo o número pivô já está em sua posição final (neste caso se a ordem for do menor para o maior). 
O tempo médio de ordenação de Quicksort é O(n log n), mas o pior caso de tempo de ordenação é O(n2). Segue o exemplo teórico do algoritmo:
Insertion sort:
O Insertion sort é um algoritmo simples e eficiente quando aplicado em pequenas listas. Neste algoritmo a lista é percorrida da esquerda para a direita, à medida que avança vai deixando os elementos mais à esquerda ordenados.
O algoritmo funciona da mesma forma que as pessoas usam para ordenar cartas em um jogo de baralho como o pôquer.
Uma insertion sort funciona usando um único item como ponto de partida e adicionando itens à sua esquerda ou direita baseada em se esses itens são menores ou maiores que o selecionado. Conforme o número de itens ordenados cresce, o algoritmo verifica novos itens em relação aos ordenados e insere o novo elemento na posição correta na lista. Uma insertion sort tem uma velocidade de melhor caso de ordenação de O(n) e de pior caso de ordenação de O(n2). 
A insertion sort ainda é um método de força bruta para ordenar itens, mas pode exigir menos comparações que uma selection sort. Segue o exemplo teórico do algoritmo:
Referencial Teórico
Quick Sort
Neste primeiro método utilizamos o algoritmo de ordenação Quick Sort, e no código a seguir temos as variáveis para ordenar da esquerda para direita e utilizamos um número como pivô. Que vai ser o elemento chave para a ordenação, ele irá jogar todos os números menores que ele para a esquerda e todos os menos para a direita.
Para definir algumas funções no código usamos as functions quicksort, partition e PrintArray. A função quicksort foi utilizada para definir as variáveis de “direita”, “esquerda“ e a nossa array que é a lista a ser ordenada. A função partition foi utilizada para definir nossa variável pivô e como ela irá ordenar os demais elementos da nossa lista, nesta parte do código foi feita um “FOR” para quando o index dos elementos deve ir para esquerda, ser for menor e quando deve ir para direta, se for maior. A função PrintArray foi criada apenas para mostrar na tela a lista e dentro dela temos um loop para que isso se repita.
Logo no final do código mostramos uma lista com alguns números quaisquer apenas para demonstração.
Bubble Sort
Neste segundo método utilizamos o algoritmo de ordenação Bubble Sort, e no código a seguir temos as variáveis para ordenar comparando um número da primeira posição com o da segunda posição. Utilizando o elemento i + 1 no código e a variável auxiliar para fazer a troca e colocar em ordem. 
Estamos utilizando uma função criada no PHP chamada “bubbleSort” que auxilia na hora de fazer a ordenação dos valores. Dentro da função fizemos um FOR para o algoritmo realizar a repetição assim que acabar de ordenar a cada dois elementos, e só termina quando os elementos do vetor estão totalmente ordenados. Esse método de ordenação não é tão eficaz quando está sendo utilizado uma lista de elementos muito extensa, por isso para fazer os testes usamos uma lista de elementos curta.
Ao final do algoritmo usamos chamamos o vetor para mostrar na tela de forma ordenada.
Heap Sort
Neste terceiro método utilizamos o algoritmo de ordenação Heap Sort, e no código a seguir temos as variáveis para ordenar trocando um elemento da última posição ou na primeira posição dependendo da forma de ordenação. Utilizando o princípio da ordenação por seleção.
Utilizamos a função heapsort que facilita no andamento do algoritmo pois é uma função do próprio PHP. Dentro da função nós chamamos um método que faz a troca de um elemento para última posição e depois outro elemento para a penúltima posição. E isso se repete no loop criado dentro da mesma função até que a ordenação de todos os elementos esteja completa.
Usamos também uma função

Crie agora seu perfil grátis para visualizar sem restrições.