Análise de Desempenho de Algoritmos de Ordenação de Dados

1 OBJETIVO 04

2 INTRODUÇÃO 05

2.1 FOTOS 07

3 DESENVOLVIMENTO 08

3.1 BUBBLE SORT 08

3.2 MERGE SORT 11

3.3 HEAP SORT 14

3.4 QUICK SORT 16

3.5 INSERTION SORT 20

3.6 SELECTION SORT 24

CONSIDERAÇÕES FINAIS 27

BIBLIOGRAFIA 28

O Objetivo do nosso trabalho é apresentar alguns dos principais métodos de

ordenação de dados, bem com a explicação e implementação de três desses

métodos com o objetivo de deixar mais clara a apresentação e diferença entre

esses métodos na prática.

Neste trabalho serão abordados de forma mais detalhada os algoritmos Bubble

Sort, Quick Sort e o Insertion Sort, com o intuito de apresentar a logica e

eficiência de cada método de acordo com a situação em que será aplicado.

A Ordenação é o processo de rearranjar um conjunto de objetos em uma

ordem ascendente ou descendente, ou seja, os algoritmos de ordenação

servem para organizar elementos na forma que se fizer necessário. O principal

objetivo da ordenação é facilitar a consulta de dados, de modo que haja

economia de tempo para tal consulta e de espaço para armazenamento dos

Um dos primeiros algoritmos de ordenação surgiu em 1890, quando Hermann

Hollerith, funcionário do United States Census Bureau (agência governamental

encarregada pelo censo nos Estados Unidos) e um dos fundadores da IBM,

desenvolveu, uma máquina para realizar as operações de recenseamento da

população. A máquina fazia a leitura de cartões de papel perfurados em código

BCD (Binarycoded Decimal). A informação perfurada no cartão era lida em uma

tabuladora que dispunha de uma estação de leitura equipada com uma espécie

de pente metálico em que cada dente estava conectado a um circuito elétrico.

Antes da utilização da máquina de cartões perfurados, o censo nos Estados

Unidos era realizado em 10 anos, o que prejudicava o bom andamento das

políticas públicas que precisavam dos dados dos censos para ser mais bem

planejadas. Após a máquina de Herman Hollerith o censo passou a ser

O algoritmo RadixSort surgiu com a necessidade de manter a ordenação dos

cartões perfurados e isso ocorreu porque o número de cartões que eram

necessários cresceu bastante, o que dificultava o controle. Além disso, uma

vez perfurados, as folhas ou cartões precisavam ser interpretados para ter

algum significado. Era necessário uma forma de interpretar e manter a ordem

das folhas, caso contrário, a máquina, que também interpretava os dados,

receberia dados errados no processamento das informações.

Foi então que surgiu o algoritmo RadixSort que ordenava cartões perfurados a

partir de uma chave única processada por partes. Nesse caso, a chave era um

número de 3 dígitos contido no cartão. A ordenação ocorria em 3 fases: na

primeira fase, os cartões eram ordenados considerando o dígito menos

significativo (mais à direita do número); na segunda fase, considerava-se o

dígito do meio e, na terceira fase, o dígito mais significativo. Vejam na imagem

a seguir, uma execução do algoritmo com vários números de 3 dígitos.

O RadixSort foi um dos primeiros algoritmos de ordenação a serem

desenvolvidos e largamente utilizado nas máquinas de cartões perfurados.

Todavia, é necessário destacar que, por ser estável e não efetuar várias

comparações torna-se eficiente quando comparado a outros algoritmos de

ordenação, sendo então utilizado até os dias atuais. Porém, possui algumas

desvantagens, pois nem sempre é fácil aperfeiçoar a inspeção de dígitos e só

se torna plausível quando o número de dígitos é pequeno.

Hermann Hollerith

3 - DESENVOLVIMENTO

O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é

um algoritmo de ordenação dos mais simples. A ideia é percorrer o vector

diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento

da sequência. Essa movimentação lembra a forma como as bolhas em um

tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

Neste