DESENVOLVIMENTO DE UM SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS
Por: Lucas Vacilloto • 19/5/2021 • Trabalho acadêmico • 11.651 Palavras (47 Páginas) • 138 Visualizações
UNIP – UNIVERSIDADE PAULISTA[pic 1]
CIÊNCIA DA COMPUTAÇÃO (CC)
DESENVOLVIMENTO DE UM SISTEMA PARA ANÁLISE DE PERFORMANCE
DE ALGORITMOS DE ORDENAÇÃO DE DADOS
SUMÁRIO
SUMÁRIO 2
OBJETIVO 3
INTRODUÇÃO 4
REFERENCIAL TEORICO 6
DESENVOLVIMENTO 11
RESULTADO E DISCUSSÃO 23
CONSIDERAÇÕES FINAIS 29
CÓDIGO FONTE 31
OBJETIVO
Esse trabalho tem como objetivo apresentar o que são métodos de ordenação, quais são os mais conhecidos, demonstrar como funcionam, aplicá-los em um programa, utiliza-los como exemplo em uma situação hipotética que necessite de uma solução computacional e obter os resultados de desempenho e discutir sobre eles.
INTRODUÇÃO
Em diversas aplicações, sejam elas de uso comercial, acadêmico ou cientifico, vemos um grande problema na ordenação de dados, como por exemplo, ordenar números ou nomes em ordens crescentes ou decrescentes. Para tal, faz-se uso dos algoritmos de ordenação, em ciência da Computação, o algoritmo de ordenação é o responsável por rearranjar elementos de uma dada sequência em uma certa ordem, ou seja, efetua a sua ordenação total ou parcial.
Quando se pensa em ordenação de dados, há vários motivos benéficos para realizar tal ordenação, uma delas é a possibilidade de acessar informações e obter resultados de maneira mais rápida e eficiente.
Sabemos que as principais linguagens de programação nos dias atuais suportam algum tipo de chamada de função que realiza a ordenação dos dados e apesar de existirem inúmeros algoritmos de ordenações, deve-se escolher aquele que proporciona o melhor resultado de acordo com o desejado pela aplicação, ou seja, não existe um algoritmo superior a outro, mas sim aquele que se adequa da melhor maneira na solução do problema proposto.
Neste vasto número de algoritmos que ordenam dados temos os principais que são o Selection Sort, Merge Sort, Bubble Sort, Quick Sort, Insertion Sort entre outros.
Explicando de forma resumida, o Selection Sort sempre irá passar o menor valor do vetor para a primeira posição, posteriormente, o segundo menor valor para a segunda posição do vetor e assim suscetivelmente até que todo o vetor esteja ordenado
Merge Sort é um algoritmo que segue uma técnica de ordenação bem interessante, diferente das demais, ele consiste em subdividir os vetores em subgrupos (pares) e ordená-los em ordem crescente ou decrescente, feito isso ele irá realizar o merge (juntar) os vetores em novos subgrupos e então ordená-los novamente e assim será feito até todo o vetor estar ordenado. Para entender melhor o conceito do Merge sort temos um exemplo:
Ordenar 6, 3, 4, 8, 1, 2, 3, 5... O algoritmo irá dividir em pares ordenados: {3, 6}, {4, 8}, {1, 2}, {3, 5}, depois irá realizar o merge desses dados, ou seja, juntá-los em dois pares ordenados {3, 4, 6, 8} e {1, 2, 3, 5}, e depois juntar novamente até que fique ordenado: {1, 2, 3, 3, 4, 5, 6, 8}.
O Bubble Sort é um dos algoritmos mais simples que existem, porém ineficiente para a ordenação de grandes volumes de dados. Nele é possível comparar os valores a serem ordenados em pares (dois a dois). Por exemplo: Compara-se o primeiro valor do vetor, com o segundo, verificando se em cada posição o valor é menor que seu vizinho à direita, e caso não seja, troca os respectivos números de posição e assim reinicia a verificação até que todo o vetor tenha sido percorrido e consequentemente tenha seus valores ordenados de maneira crescente ou decrescente.
O Quick Sort desenvolvido por C.A.R Hoare nos anos 60, é um método de ordenação muito rápido e eficiente, ele adota a estratégia de rearranjar as chaves de modo que as chaves de menor valor, precedam as chaves de maiores valores. Nele, é escolhido um elemento chamado de pivô, a partir disto, é organizada a lista de tal modo que elementos anteriores a ele sejam de menor valor que o mesmo e elementos posteriores a ele, sejam de maior valor.
No Insertion Sort, o algoritmo ordena seus dados partindo do pressuposto de que o valor da primeira posição já está ordenado, selecionando o valor da segunda posição e comparando com o da primeira, caso o valor seja inferior ao primeiro, trocam-se as posições no vetor, na sequência o algoritmo compara as demais posições percorrendo o vetor todo até que todos os dados estejam ordenados entre si.
REFERENCIAL TEORICO
Para este projeto, o grupo utilizou-se das seguintes técnicas de ordenação de dados, tais como o Quick Sort, Selection Sort, Insertion Sort e Bubble Sort.
Quick Sort
Como já dito antes no Quick Sort é o método mais rápido e eficiente na ordenação de dados, nele é escolhido um número como pivô e a partir disso uma lista é organizada de modo que todos os números menores que o pivô fiquem a esquerda e os maiores a direita dele. Vejamos no exemplo a seguir.[pic 2][pic 3]
Neste exemplo o número 3 foi escolhido como o pivô do vetor, sendo assim o algoritmo compara o pivô com o menor valor do vetor que ainda não tenha sido ordenado à sua direita, que no caso é o número 1. Se 3>1 for verdadeiro, então a troca é realizada.
No segundo passo o pivô procura a sua esquerda um número que seja maior que ele, o número encontrado foi o 5, se 5>3 for verdadeiro, a troca é realizada então.
Terceiro passo o pivô novamente procura um número menor que ele a direita que no caso é o valor 2, então realiza a troca.
No quarto passo, procura um valor a esquerda maior que ele, vemos que há o valor 4, então o algoritmo realiza a troca, ficando assim com todos os valores do vetor ordenados em ordem crescente.
Selection Sort
No Selection Sort, a ordenação de dados consiste em pegar a primeira posição do vetor e compará-la com as demais posições para encontrar o menor valor e substitui-lo na primeira posição do vetor, em seguida o mesmo processo é efetuado novamente, porém a partir da segunda posição, comparasse todos os valores com a segunda posição do vetor, encontrando o menor valor, substitui-se o mesmo para a segunda posição e assim sucessivamente até que todos os valores tenham sido selecionados e colocados em suas posições definitivas.
...