Desenvolvimento de Sistema para Análise de Performance de Algoritmos de Ordenação de Dados

...

- C++

- PHP

- JAVA

Onde ao desenvolver o trabalho, foi focado nos algoritmos de ordenação utilizando a linguagem Orientada a Objeto Java.

- Introdução

Nos textos a seguir veremos pesquisas sobre os principais métodos de ordenação em geral, e os escolhidos na realização do trabalho, que são os métodos, Bubble Sort, Selection Sort e Insertion Sort.

Esses métodos de ordenação, como dito anteriormente, têm como sua principal funcionalidade ordenar os dados de forma pratica e funcional em um algoritmo, assim, facilita-se o acesso aos dados ordenados, deixando este processo mais rápido.

Partindo da ideia de ordenação de dados para melhorar sua busca, foram criados diversos algoritmos de ordenação, tais como:

- InsertionSort

- SelectionSort

- BubbleSort

- CombSort

- Merge Sort

- Heapsort

- Shell Sort

- Radixsort

- GnomeSort

- CountSort

- BucketSort

- CocktailSort

- Timsort

- QuickSort

Em cada um dos métodos listados acima, encontramos formas diferentes de lógica e de implementação em algoritmos para ordenar os dados, uns de formas mais fáceis e simples, outros com lógicas mais complexas, e cada um com seu nível diferenciado de funcionalidade dentro do algoritmo.

Entre eles, irei descrever os que foram usados na realização do trabalho, e os principais métodos mais utilizados.

- BubbleSort

O método de ordenação BubbleSort (Método Bolha) é considerado entre os métodos de ordenação, um dos mais fáceis por sua lógica e aplicação no algoritmo não serem complexas.

Neste método utilizamos de ordenação por comparação, para isso, ele percorre o vetor completo, comparando os elementos adjacentes, indo de dois em dois, e no momento da comparação, ele “empurra” o maior valor para trás caso esteja desordenado, se não estiver ele mantém a posição e realiza a próxima comparação, indo desta forma de dois em dois até o final do vetor e retorna ao inicio do vetor para novamente realizar todas as trocas de posição, ordenando-os até que o vetor por completo esteja ordenado.

Como dito antes, o maior ponto positivo do algoritmo BubbleSort é a sua lógica fácil de ser compreendida e implementada nos algoritmos, porém, este tipo de ordenação não é recomendado para números de registros muito grandes, pois como a ordenação é feita comparando os elementos de dois em dois, para uma quantidade muito grande de dados a serem ordenados, prejudicaria o programa causando lentidão ou até mesmo má funcionalidade do mesmo.

- InsertionSort

Com o algoritmo InsertionSort, utilizamos ordenação por inserção. Desta forma ao percorrermos o vetor, inserimos os valores menores e maiores em seus lugares devidos ordenando o vetor.

No momento em que percorrermos o vetor, ele inicia da direita para a esquerda, onde o primeiro elemento do vetor é separado em um subconjunto, neste subconjunto, independente do valor do primeiro elemento, ele consta como o menor valor do subconjunto. Ao continuarmos percorrendo o vetor, localizamos o elemento menor do que o elemento separado no subconjunto, desta forma, o elemento menor do que o do subconjunto é colocado na posição da esquerda, levando o antigo primeiro valor do subconjunto para a direita. E continua percorrendo o vetor e efetuando a troca de forma que todos os elementos do vetor sejam ordenados.

A principal vantagem deste método em questão, é a sua facilidade de implementação em um algoritmo, além de ter um bom desempenho em listas pequenas de dados e não consumir muita memória no momento da ordenação. Porém, como outros métodos, ele não é muito funcional quando se trata de uma base de dados grandiosa a ser ordenada, sua funcionalidade se limita também devido a como sua estrutura se dá a lógica para efetuar a ordenação.

- SelectionSort

No algoritmo SelectionSort, utilizamos o método de seleção, de tal forma que é selecionado o maior elemento e o menor e é efetuado as trocas para obter a ordenação.

Neste algoritmo, percorremos todos os valores do vetor para acharmos o maior elemento, após localizado o maior elemento, percorremos novamente o vetor afim de achar o menor elemento de todo o vetor. Localizado o menor elemento, é efetuado a troca entre o maior elemento do vetor e o menor, desta forma, ele retorna a percorrer o vetor, porém pegando o índice do 2º menor elemento do vetor e comparando com os demais elementos afim de obter assim a ordenação completa do vetor.

Assim como o método Bubblesort, utilizando o SelectionSort em listas muito extensas de dados, não poderemos obter bons resultados, por seu algoritmo como o do Bubblesort é de ordem quadrática, ou seja, ele utiliza-se de dois elementos do vetor duas vezes para obter a ordenação completa.

- QuickSort

O algoritmo QuickSort utiliza-se de ordenação por divisão e conquista, partindo disto, dividimos os elemento de forma que eles se arranjem em duas partes para que assim sejam ordenados separadamente antes de retornarmos a uni-los.

Melhor dizendo, num conjunto de elementos onde necessitam ser ordenados, a ordenação por divisão e conquista utiliza-se primeiramente de um pivô, que seria definido como o elemento central do grupo, e os grupos seriam definidos de tal forma que os elementos anteriores ao pivô sejam menores do que ele e os elementos posteriores ao pivô sejam maiores do que ele. Após esta separação entre os valores maiores e menores do conjunto, definimos um novo pivô entre os conjuntos criado, novamente ordenando eles de forma em que os maiores estejam à direita do novo pivô e os menores a esquerda do novo pivô. Assim, continuamos criando subgrupos e escolhendo novos pivôs dentro dos subgrupos até que todos estejam devidamente ordenados e volte à junção do grupo num total.

Diferentemente