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

Índice

1–Objetivo do Trabalho.......................................................................................3

2–Introdução.......................................................................................................4

3–Referencial Teórico.........................................................................................5

3.1–Blubble Sort..................................................................................................5

3.2–Merge Sort....................................................................................................5

3.3–Quick Sort…….............................................................................................6

4–Resultados e Discussão..................................................................................7

4.5–Vantagens e Desvantagens........................................................................11

5–Considerações Finais....................................................................................12

6–ReferênciasBibliográficas..............................................................................13

7–Código Fonte.................................................................................................14

1 - Objetivo do Trabalho

O objetivo desse trabalho é analisar a performance de algoritmos de ordenação de dados, tais como:

* BubleSort

* SelectSort

* InsertSort

* QuickSort

* MargeSort

2 – Introdução

A ordenação é um dos aspectos fundamentais das ciências computacionais. Torna-se, então, importante reduzir ao máximo a complexidade temporal dos algoritmos que lidam com este problema. As melhores ordenações em série normalmente demoram O(n log n), tempo que tende a agravar com o aumento do número de elementos. Deste modo, foram desenvolvidas versões para funcionamento em paralelo destes algoritmos, cujo objetivo é diminuir consideravelmente o tempo deexecução dos mesmos.

Neste trabalho irei abordar alguns algoritmos de ordenação. Relativamente aos que realizam operações de comparação e troca, existem o bubble sort, quick sort, merge sort, insert sort e select sort.

O algoritmo de ordenação bubble sort usa uma estratégia de comparação e troca, mas é o menos efeciente. Os elementos vão borbulhando a cada iteração do método até a posição correta e cada passada do algoritmo é garantante-se q o maior elemento fique na ultima posição do vetor. (Quinn, 2003)

O algoritomo de ordenação quick sort foi inventado por C.A.R. Hoare, é um algoritmo recursivo que tem como base a comparação de valores para ordenar uma lista desordenada. Mais especificamente, quando é passada uma lista de números, o algoritmo seleciona um número dessa lista, tornando-o pivô. Após isso, a lista é partida em duas sub-listas: uma contendo números inferiores ao pivot, e outra com os números superiores. Chama-se depois a si mesma recursivamente para ordenar as duas sub-listas. A função retorna a concatenação da primeira lista, pivot e segunda lista. (Tsigas e Zhang, 2003)

O merge sort, diferente dos outros algoritmos, procede à sua junção (merge), retornando no final uma única lista com todos os elementos ordenados. Consiste em ir separando em metades uma lista de elementos, até ficar com todos os elementos separados. Esta técnica tem o objetivo de dividir para conquistar após estes elementos estarem separados. (Wilkison e Allen, 2005)

No algoritmo de insert sort o vetor é dividido em dois segmentos, um com os elementos já ordenados e o outro com os elementos a ordenar. No início só o primeiro elemento está no segmento já ordenado, então é verificado qual a posição do primeiro elemento do segmento a ordenar no segmento já ordenado, então oelemento é retirado do segmento a ordenar e inserido no já ordenado. Esse processo se repete até que não exista segmento a ordenar o que coincide com a ordenação do vetor. (Cormen op. Cit.)

E o algoritmo select sort é feita a procura do menor elemento de todo e então este elemento é trocado de lugar o primeiro elemento do vetor. Então a procura pelo menor número é feita a partir do segundo elemento e é trocado de lugar com o segundo elemento do vetor, e assim sucessivamente até o penúltimo elemento e então o vetor estará ordenado. (Ziviani, 2004)

3 – Referencial Teórico

3.1 – Bubble Sort

O algoritmo de ordenação Bubble Sort é bem simples de ser implementado, mas é o menos eficiente. A idéia desse algoritmo é percorrer o vetor n – 1 vezes, a cada passagem fazendo ir para inicio o menor elemento da sequência. Esse algoritmo lembra muito de uma forma de bolhas que procuram seu próprio nível e não é recomendado para vetores com vários elementos. (Quinn, 2003)

O bubble sort usa a compração e troca como estratégia, isso é aplicada em várias iterações sobre os dados as serem ordenados. Irei falar um pouco do algoritmo seqüencial. (Quinn, 2003)

Começando do inicio onde se deseja ordenar, isso de forma crescente, um vetor de números nas seguintes posições: x0, x1, …, xn-1, xn. Esse algoritmo inicia comparando o número que se encontra na posição x0 com o da posição x1, e troca quando necessário os números de maneira a ficar o maior da posição x1. Em seguida, repete o mesmo procedimento para as posições x1 e x2, onde na posição