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

UNIP – UNIVERSIDADE PAULISTA

CIÊNCIA DA COMPUTAÇÃO

DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE

DE PERFOMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS

GLEYDSON SILVESTRE DE OLIVEIRA

C20DAB-1

RAFAEL BOEACHT ALMEIDA

C2149D-8

WALLISON JUNIOR CARDOSO SOARES SILVA

C1254G-3

Goiânia-GO.

2015.

Sumário

1. Objetivo do Trabalho........................................................4 2. Introdução........................................................................5 3. Referencial Teórico..........................................................8 3.1 Bubble Sort.....................................................................8 3.2 Insertion Sort..................................................................8 3.3 Selection Sort.................................................................8 3.4 Quick Sort.....................................................................10 4. Desenvolvimento Sistema……………............................12 4.1 Selection Sort...............................................................12 4.2 Bubble Sort...................................................................15 4.3 Insertion Sort................................................................17 4.4 Quick Sort.....................................................................20 5. Resultados e Discussão.................................................24 5.1 Teste com vetores gerados aleatoriamente..................24 5.1.1 Quick Sort..................................................................25 5.1.2 Bubble Sort................................................................25 5.1.3 Selection Sort............................................................25 5.1.4 Insertion Sort.............................................................25 5.2 Teste com vetores pré definidos..................................25 5.2.1 Vetor aleatório...........................................................25 5.2.2 Vetor semi-ordenado.................................................28 5.2.3 Vetor ordenado..........................................................29 5.3 Análise Geral................................................................29 6. Conclusão......................................................................31 7. Referencias....................................................................32 8. Código Fonte..................................................................34 9. Anexos...........................................................................38 10. Ficha de Atividades Práticas Supervisionas.................41

1. Objetivo do Trabalho

Esse trabalho tem como base demonstrar quatros tipos de algoritmos de ordenação diferente, bubble sort, selection sort, insertion sort e quick sort. Apresentando de forma clara e objetiva, suas vantagens e desvantagens, bem como seu funcionamento na prática em alguns casos específicos, além da definição teórica de cada um.

Com isso, queremos relatar o melhor algoritmo para ordenação de vetores com grandes variedades de dados, além de tamanhos diversos. Como proposto pelo tema da Atividade Prática Supervisionada.

2. Introdução

Algoritmos existem desde a remota antiguidade. A execução de uma soma armada de 2 números com vários algarismos, e um exemplo o famoso “algoritmo de Euclides” para cálculo de máximo divisor comum, se o autor assumido foi seu inventor, data do 3º século a.C. No decorrer do dia a dia, o ser humano sente a necessidade de consultar dados ordenados. Este fato se dá em virtude da agilidade em ganhar tempo em tarefas rotineiras. Imagine como seria consultar o telefone de uma pessoa se os nomes não estivessem classificados em ordem alfabética. Por isso uma das atividades mais utilizada na computação é a ordenação. As ordens mais utilizadas são as numéricas e as lexicográficas. Existem diversos algoritmos para ordenação interna.

Hoje em dia, a noção e domínio dos algoritmos tornou-se absolutamente essencial, pois qualquer programa de computador que “funciona”, isto é, dá os resultados esperados, deve ser provavelmente uma descrição de um algoritmo, ou seja, se desejar elaborar um programa para um computador, a maneira correta de fazê-lo seria inicialmente procurar os métodos mais adequados à solução do problema em questão, especificar essa solução como um algoritmo e, depois disso, formulá-lo em alguma linguagem de programação para poder introduzi-lo no computador.

Neste trabalho se aplicam as noções para que exista a ordenação de elementos Através das atividades aqui descritas, dá-se introdução a uma ampla gama de conceitos fundamentais da Teoria da Computação. A ordenação é uma atividade importante na organização de classes de objetos, visando à sua rápida localização. Assim, ordenação corresponde ao método de rearranjar um conjunto de objetos em uma ordem crescente ou decrescente, com o objetivo de facilitar a recuperação dos itens desse conjunto, tornando-se assim fundamental em processamento de dados. Existem muitos algoritmos de ordenação, a escolha mais eficiente vai depender de vários fatores, tais como: número de itens a ser classificado; se os valores já estão agrupados em subconjuntos ordenados, desordenados, aleatórios e parcialmente ordenados. A seguir são apresentados os métodos de ordenação analisados na pesquisa proposta: Quick Sort, Bubble Sort, Isertion Sort, Select Sort.

O Quicksort foi inventado em 1962 por Hoare e é um algoritmo bom por ser relativamente fácil de ser implementado e realiza ordenação in-place, ou seja, não precisa de um vetor auxiliar para realizar a ordenação. O tempo médio de execução é ótimo (n log n), porém sua implementação é frágil e deve ser realizada com cuidado para evitar a ocorrência do pior caso que é n 2. Desde sua invenção, o QuickSort é provavelmente um dos mais utilizados algoritmos de ordenação até hoje e muitos pesquisadores tentam ainda melhorar a implementação do QuickSort propondo diferentes versões otimizadas desse algoritmo. Cada otimização leva em consideração um critério, uma ideia de melhoria, mas o princípio básico do QuickSort é sempre o mesmo, dividir para conquistar. É um método de ordenação muito rápido e eficiente que foi criado com o objetivo de tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rapidamente.