O Desenvolvimento de sistema para análise de performance de algoritmos de ordenação de dados

Universidade Paulista UNIP

Curso de Graduação em Ciência da Computação

Desenvolvimento de sistema para análise de performance de algoritmos de ordenação de dados

Leonardo Luiz Nogueira D06HBE-6

Michel Alison Silva de Oliveira D027IJ-2

Wesley da Silva Santana D04ACH-2

Índice:

Objetivo do trabalho....................................................................................................3

Introdução....................................................................................................................3

Referencial Teórico.....................................................................................................4

Desenvolvimento........................................................................................................9

Resultados e Discussão.............................................................................................19

Considerações Finais.................................................................................................25

Referencias Bibliograficas..........................................................................................26

Introdução

Como tema proposto " Desenvolvimento de sistema para análise de performance de algoritmos de ordenação de dados", pesquisamos amplos algoritmos de ordenação que atenda de uma forma mais pratica e complexa as necessidades do desenvolvimento do programa proposto para o projeto. Uma simples descrição de um dos algoritmos mais comum, que também implementamos no projeto é o BubbleSort um dos mais simples, que tem como ordem percorrer um vetor, passando para o topo sempre o maior número do vetor, essa movimentação do BubbleSort, faz com que se lembre e compare a bolas em um balde de agua, procurando seu nível, ou seja sua posição. O Bubble tem ordem quadrática, por ter esse princípio ele não é recomendado para sistemas que necessitam de velocidade de processamento de dados e assim como quantidades.

O MergeSort é um tipo de algoritmo de ordenação que usa comparações para se efetuar operações, ela tem mais atenção ser de o tipo Dividir para Conquistar, ou seja, consiste em dividir os elementos em vários sub-elementos e resolver esses sub-elementos através de recursividade e depois conquistar é a união dos sub-elementos resolvidos. Como o Merge usa recursividade, tem um grande consumo de memória e tempo de execução, há tornando com pouca eficiente diante de vários casos de programas.

O QuickSort é um algoritmo de ordenação muito rápido e eficiente, assim como o Merge ele adota a "divisão e conquista", através de arranjar elementos pivôs menores que precedam pivôs maiores, em seguida ordena as sub-elementos dos pivôs menores e maiores recursivamente até que todos os elementos estejam em ordem.

O SelectionSort é um algoritmo baseado em passar sempre o menor valor do vetor para a primeira posição, ou maior dependendo da ordem, depois o segundo elemento, até o final, assim sucessivamente n-1 elementos restantes. Ele é composto por dois laços de repetição, um externo e interno, o laço externo 'for' tem como objetivo controlar o índice inicial e o interno tem como objetivo percorrer o vetor. Na primeira iteração do laço externo o índice começa de 0 e cada iteração ele soma uma unidade até o final do vetor e o laço mais interno percorre o vetor começando desse índice externo + 1 até o final do vetor. Uma das vantagens do SelectionSort é que ele é um algoritmo dos mais lentos para vetores com grandes tamanhos, e ele faz n² comparações, independente do vetor estar ordenado ou não.

Referencial Teórico

Como entre tantos algoritmos de diferentes e amplos de complexidade, vantagens e desvantagens criadas, para um melhor empenho, e de fácil desenvolvimento foram escolhidos 3 tipos de algoritmos de ordenação: BubbleSort, MergeSort e SelectionSort. No desenvolvimento e elaboração do projeto, começamos com o BubbleSort, como explicação para termos implementado esse algoritmo foi sua manipulação diante de linguagem escolhida nesse projeto, o Java. Sua compreensão manual é muito complexo e seria necessário muita pesquisa para ser feita a mão, após muita pesquisa de implementação e como o Buuble Sort funciona, tivemos muita dificuldade em implementa-la na linguagem Java, pois a preenchemos com dados de um banco de dados, através de um vetor. Para uma visão mais ampla desse algoritmo de ordenação, está seguinte forma em linguagem:

public Vector<Vector> bubbleSort(Vector<Vector> Orde) {

(Aqui é o nome e o parametro do método, como observação passamos como parametro um Vector, aonde estão os dados a serem passados, assim também como seu retorno)

for (int i = Orde.size(); i >= 1; i--) {

( Aqui começa o primeiro laço para dar apoio ao decorrer do vetor, Controlando o índice)

for (int j = 1; j < i; j++) {

if (Integer.parseInt(Orde.get(j - 1).get(0).toString()) > Integer.parseInt(Orde.get(j).get(0).toString())) {

(Nesse 'If' ele faz a comparação do elemento maior para o menor para a ordenação necessária, alterando e mudando valores de respectivas posições)

Vector aux = Orde.get(j);

(Nessa linha ele criar uma variável auxiliar para guardar o elemento proposto no índice do 'If')

Orde.set(j,Orde.get(j-1));

Orde.set(j-1,aux);

( E aqui ele termina a ordenação e pula para o próximo elemento do 'for')

...