Implementação de Algoritmo Híbrido AOH a partir de Algoritmos Conhecidos

Implementação de Algoritmo Híbrido AOH a partir de Algoritmos Conhecidos

Leandro Soares Neves

Curso de Bacharelado em Ciência da Computação–Universidade Federal do Piauí(UFPI) – Campus Universitário Ministro Petrônio Portella
64049-550 – Teresina– PI– Brasil

[e-mail]

Resumo.Este artigo destina-se a analisar e avaliar o desempenho de alguns algoritmos de ordenação de vetores através de testes em uma interface de desenvolvimento e gráficos comparativos. Ainda no artigo, será mostrado um algoritmo” híbrido” (AOH) e seus respectivos resultados nos testes.

1. Introdução

Este trabalho é composto de duas etapas, onde na primeira o objetivo é avaliar o desempenho de alguns dos principais algoritmos de ordenação de vetores conhecidos (Insertion Sort, Selection Sort, Bubble Sort, Merge Sort).

A partir de resultados colhidos, a segunda e mais importante etapa é desenvolver um terceiro algoritmo híbrido (composto pelo Algoritmo MergeSort com um dos outros algoritmos) representando a melhor combinação (o algoritmo AOH mais rápido e eficiente). Essa análise se baseia na implementação e execução dos mesmos em iguais condições de tamanho da entrada, recursos de memória e processamento.

2. Especificações

Os algoritmos foram implementados na IDE Falcon C++ V3.3.0.0 em um notebook com processador core i3-2328M e memória RAM DDR3 de 2GB com o Windows 10 como Sistema Operacional.

Os algoritmos de ordenação foram organizados em funções dentro de um único código (funcoes.cpp) referenciados por um arquivo de cabeçalho (funcoes.h). Há também o código principal (main.cpp) contendo as referências das funções dos algoritmos e uma função (void menu()) para uma melhor interação e disposição das informações da aplicação. Os testes serão avaliados com vetores de entrada de tamanhos predefinidos: 100, 500, 1.000, 5.000, 30.000, 80.000, 100.000, 150.000 e 200.000. A coleta de resultados é feita executando o algoritmo três vezes para cada entrada, tendo como resultado a média das três execuções conforme especificado pelo professor.

3.  Desenvolvimento

A ordenação é uma operação imprescindível em ciência da computação, já que é utilizada em muitos programas como etapa intermediária. Tendo em vista tal importância, foram então desenvolvidos muitos algoritmos com essa finalidade, cada um com sua forma de rearranjar os dados, com eficiência e complexidades diferentes.

É importante perceber que nem sempre um determinado algoritmo pode ser o melhor de todos nas mais variadas situações, existem pontos importantes a serem levados em consideração, tais como tamanho da entrada, a extensão em que certos itens já estão ordenados de alguma forma, restrições sobre os valores e o dispositivo onde esses itens serão armazenados.

Aqui veremos alguns dos algoritmos mais populares esuas respectivas análises.

3.1. InsertionSort

O algoritmo InsertionSorté um algoritmo de ordenação simples, de complexidade no melhor caso Ω(n) e no pior caso e no caso médio ϴ(n²). Ele consiste em ordenar por comparação na qual uma nova lista é construída em um valor por vez, sendo eficiente em vetores com tamanho reduzido. Já quando se trata de grandes vetores / listas ele se torna bem menos eficiente que algoritmos como MergeSort, HeapSort e QuickSort.

A seguir o gráfico com os resultados dos testes de cada entrada:

[pic 1]

3.2. SelectionSort

O algoritmo selection sort consiste em ordenar elementos deslocando o menor ou maior valor (dependendo da ordem requerida – se não-decrescente ou decrescente) para a primeira posição, depois o segundo maior/menor para a segunda posição e assim sucessivamente com os elementos restantes até os dois últimos elementos.

Segue o gráfico:

[pic 2]

3.3.BubbleSort

O bubblesort, ou ordenação por flutuação, é um algoritmo de ordenação também bem simples a exemplo dos dois anteriores. A ideia é percorrer o vetor diversas vezes, a cada passagem fazendo “flutuar” para o topo o maior elemento da sequência. Essa movimentação lembra a forma como bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

No melhor caso, o algoritmo executa n operações, onde n representa a quantidade de elementos do vetor. Já no pior caso, são feitas O(n²) operações (complexidade de ordem quadrática). Contudo, tal algoritmo não é recomendado no uso de programas que exigem agilidade e manipulação de grande quantidade de dados.

A seguir o gráfico com os resultados:

[pic 3]

3.4.MergeSort

O merge sort, ou ordenação por intercalação, é um exemplo de algoritmo de ordenação que usa o princípio de divisão e conquista.

Sua ideia básica é muito intuitiva: criar uma sequência ordenada a partir de duas outras também ordenadas. Para tal, ele divide o algoritmo em duas subsequências (passo da divisão) até que se tenha sequencias de um único elemento (passo da conquista - ponto de parada da recursão, que por conter apenas um elemento logicamente já estará ordenado) e agrupa esses elementos novamente de maneira ordenada (passo da combinação).