DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS.

...

O QuickSort ainda tem como estratégia a divisão e a conquista, ou seja a estratégia consiste em rearranjar as chaves menores para que elas precedam as chaves maiores, ainda esse método ordena as duas sublistas de chaves menores e maiores para que lista seja ordenada adequadamente conforme necessário.

Em algumas raras instâncias, o Quicksort pode ser tão lento quanto os algoritmos elementares; mas em geral é muito mais rápido. Mais precisamente, o algoritmo consome tempo proporcional a n log n em média e proporcional a n2 no pior caso.

Usaremos duas abreviaturas ao discutir o algoritmo. A expressão v[i..k] ≤ x será usada como abreviatura de v[j] ≤ x para todo j no conjunto de índices i..k. Analogamente, a expressão v[i..k] ≤ v[p..r] será interpretada como v[j] ≤ v[q] para todo j no conjunto i..k e todo q no conjunto p..r.

No método algoritmo BubbleSort podemos verificar que também é um método de ordenação porém mais simples que o QuickSort, esse algoritmo tem como objetivo comparar os itens a serem ordenados de maneiro sucessiva ou seja o mesmo faz comparações de acordo com as posições dos dados a serem ordenados, porém esse algoritmo não é indicado para casos de ordenações que requem velocidade e que possuem grande quantidade de dados a serem ordenados pois ele percorre os dados por diversas vezes.

Técnica básica Comparam-se dois elementos e trocam-se suas posições se o segundo elemento é menor do que o primeiro São feitas várias passagens pela tabela Em cada passagem, comparam-se dois elementos adjacentes Se estes elementos estiverem fora de ordem, eles são trocados.

Vantagens Simplicidade do algoritmo, Estável. Desvantagens Lentidão Indicações Tabelas muito pequenas. Quando se sabe que a tabela está quase ordenada, Demonstrações didáticas. Origem da denominação, Os elementos menores (mais “leves”) vão aos poucos “subindo” para o início da tabela, como se fossem bolhas.

Por fim temos o algoritmo InsertionSort, é o algoritmo de ordenação que, dado uma estrutura (array, lista) constrói uma matriz final com um elemento de cada vez, uma inserção por vez. Assim como algoritmos de ordenação quadrática, é bastante eficiente para problemas com pequenas entradas, sendo o mais eficiente entre os algoritmos desta ordem de classificação. Esse algoritmo tem fácil utilização em comparação aos demais porém muitas vezes ele pode não ser eficiente para grandes quantidades de dados e também é um algoritmo instável em sua utilização.

InsertionSort: Podemos fazer uma comparação do Insertion Sort com o modo de como algumas pessoas organizam um baralho num jogo de cartas. Imagine que você está jogando cartas. Você está com as cartas na mão e elas estão ordenadas. Você recebe uma nova carta e deve colocá-la na posição correta da sua mão de cartas, de forma que as cartas obedeçam a ordenação.

A cada nova carta adicionada a sua mão de cartas, a nova carta pode ser menor que algumas das cartas que você já tem na mão ou maior, e assim, você começa a comparar a nova carta com todas as cartas na sua mão até encontrar sua posição correta. Você insere a nova carta na posição correta, e, novamente, sua mão é composta de cartas totalmente ordenadas. Então, você recebe outra carta e repete o mesmo procedimento. Então outra carta, e outra, e assim por diante, até você não receber mais cartas.

4. Resultados e Discussão

Os resultados que irão ser apresentados a seguir foram adquiridos por meio de um computador com processador Intel i5 e memória RAM DDR2 de 4GB.

4.1 Dados Aleatórios

[pic 1]

(Valores na escala de milisegundos (ms))

[pic 2]

Na situação de dados em ordem aleatória, o BubbleSort resultou notoriamente o pior desempenho, 8 vezes mais delongado para ordenar mil números, 3 vezes para ordenar dez mil e aproximadamente duas vezes mais para ordenar cem mil em comparação com o segundo da lista, o InsertionSort. E com o melhor desempenho bem acima dos outros se encontra o QuickSort.

4.2 Dados pré-ordenados em ordem decrescente

[pic 3]

(Valores na escala de milisegundos (ms))

[pic 4]

Na situação de dados pré-ordenados em ordem decrescente, o BubbleSort resultou o pior resultado, porém desta vez não tão lenta como a primeira, ficando somente um pouco atrás do segundo da lista, o InsertionSort. E com o melhor desempenho bem acima dos demais novamente, encontra-se o QuickSort.

4.3 Dados já ordenados (ordem crescente)

[pic 5]

(Valores na escala de milisegundos (ms))

[pic 6]

Na situação de dados já ordenados, o BubbleSort conseguiu o pior resultado, mas como no último caso, ficou apenas bem pouco atrás do segundo da lista, resultou em um tempo muito próximo do InsertionSort. E com o melhor desempenho muito além dos outros mais uma vez, o QuickSort fica em primeiro lugar.

Sobre os testes:

O Quick Sort sem dúvida alguma é o mais veloz para todos os tamanhos e tipos de dados usados em comparação aos demais. Em dados do mesmo tamanho, o Quick Sort processa mais rapidamente para dados ordenados, o Insertion só supera ou empata com o Quick Sort em todos os casos em que o dado foi de tamanho 100. O Bubble Sort possui o pior dos casos em ordem aleatória e decrescente, tornando-se análogo ao Insertion apenas nos dados já ordenados.

5. Considerações Finais

No trabalho foram apresentados três métodos de ordenação, alguns dos mais conhecidos, foi explicado como funcionam, seus desempenhos e foram também aplicados na prática em um software. Em analogia aos desempenhos dos métodos, o QuickSort é o algoritmo mais poderoso que existe para uma grande variedade de situações, é recursivo, o que demanda uma pequena quantidade de memória adicional ganhando mais desempenho.

6. Desenvolvimento

Nosso programa não possui nenhuma interação com o usuário, os resultados serão exibidos no console da IDE do Eclipse Oxygen.

[pic