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

...

Complexidade para qualquer caso é .[pic 4]

- SELECTION SORT

O método de seleção (Selection Sort) busca o menor valor do vetor a ser ordenado e o coloca na primeira posição, fixando essa posição para que não faça mais parte da próxima busca. Este processo se repete até que o vetor seja completamente ordenado.

Ilustração do método:

[pic 5]

Analisando a figura acima, podemos ver que há uma troca entre o primeiro elemento de cada busca como o menor elemento da parte desordenada do vetor.

Complexidade:

- Pior caso: ;[pic 6]

- Melhor caso: [pic 7]

- INSERTION SORT

Este método de ordenação por inserção é eficiente em pequenos vetores. Consiste em varrer o vetor da esquerda para a direita, e conforme avança ele vai mantendo o lado esquerdo do vetor organizado.

Ilustração do método:

[pic 8]

A figura acima mostra o processo feito por este método para ordenar os elementos. Conforme o sistema anda de casa em casa do vetor, ele vai organizando o elemento selecionado na parte esquerda do vetor, ou seja, a cada elemento que ele seleciona ele procura sua posição na parte esquerda do vetor, mantendo esta sempre organizada.

Complexidade para qualquer caso .[pic 9]

- QUICK SORT

Um algoritmo rápido como o próprio nome diz, o Quick Sort funciona de forma recursiva. Consiste em pegar uma chave, organizar o vetor colocando de um lado os maiores que a chave e do outro os menores. Por ser recursiva, tanto a parte menor quanto a parte maior, viram vetores distintos que vão ter outra chave e organizar da mesma maneira, assim sucessivamente até chegarmos a um vetor de apenas um elemento.

Ilustração do método:

[pic 10]

Como podemos ver na ilustração, este método seleciona uma chave e separa os maiores à esquerda, e menores à direita. Assim recursivamente, e fará como que cada um dos lados se torne vetores e separarão os maiores e os menores, até chegar a um vetor de apenas um elemento. Após esse processo ele volta ordenando o vetor.

Complexidade: caso médio O(n * log n).

- Desenvolvimento

Para desenvolver o programa, utilizamos a linguagem de programação C++. Com base na análise que desenvolvemos para a construção dos sistemas, tomamos a decisão de fazer um sistema para captação de dados a ser ordenados.

- Obtenção de Dados

O sistema de ordenação obtêm os dados através de um arquivo de texto, este que será gerado também por um programa desenvolvido pelo grupo.

O programa funciona de forma simples, o usuário digita a quantidade de elementos que deseja armazenar e aleatoriamente estes elementos são criados.

[pic 11]

O arquivo de texto de forma simples armazena cada número em uma linha, o que facilita a importação desde arquivo para o sistema de ordenação.

[pic 12]

- Processos para Ordenação

O sistema desenvolvido possui quatro formas de ordenação, mas antes é preciso importar de um arquivo de texto os elementos a serem ordenados. Para isso, criamos uma função que capta uma determinada lista de números do arquivo de texto.

Feito isso, o sistema possibilita a visualização do vetor importado como a possibilidade de ordenar em qualquer um dos quatro algoritmos de ordenação.

[pic 13]

O programa ordena em qualquer um dos algoritmos e já apresenta o seu tempo de execução.

- Listagem de Valores

É possível visualizar e salvar os valores da lista antes ou depois da sua ordenação. O sistema tem uma função que armazena os elementos novamente em um arquivo de texto.

- Apresentação dos Resultados

Após a ordenação de um vetor o sistema apresenta o tempo gasto para ordenar em milissegundos. Este tempo será utilizado para a comparação com os demais algoritmos de ordenação. O tempo define o desempenho a ser avaliado neste trabalho, pois não avaliaremos o espaço gasto na memória.

- RESULTADOS E DISCURSÃO

Para avaliarmos o desempenho dos algoritmos utilizamos a função clock de C++ antes da função de ordenação e logo após a mesma. Esta função armazena em uma variável a hora exata, assim, fazendo a subtração da hora armazenada após a utilização da função de ordenação pela hora armazenada antes da chamada da função, temos o tempo gasto para executar a função.

Utilizamos vetores dos tamanhos de 5.000, 10.000 e 100.000 para fazer a avaliação do tempo gasto na ordenação de cada um dos algoritmos. Com Isso, obtivemos os seguintes resultados:

- Bubble Sort:

- Vetor de 5.000: 70 milissegundos;

- Vetor de 10.000: 265 milissegundos;

- Vetor de 100.000: 27831 milissegundos.

- Selection Sort:

- Vetor de 5.000: 44 milissegundos;

- Vetor de 10.000: 153 milissegundos;

- Vetor de 100.000: 13362 milissegundos.

- Insertion Sort:

- Vetor de 5.000: 31 milissegundos;

- Vetor de 10.000: 78 milissegundos;

- Vetor de 100.000: 6143 milissegundos.

- Quick Sort:

- Vetor de 5.000: menos de 1 milissegundos;

- Vetor de 10.000: 2 milissegundos;

- Vetor