UNIP - Trabalho de Algoritmo de Ordenação de Dados

...

Embora você não perceba, utiliza algoritmos de forma intuitiva e automática diariamente quando executa tarefas comuns. Como estas atividades são simples e dispensam ficar pensando nas instruções necessárias para fazê-las, o algoritmo presente nelas acaba passando despercebido.

3.1.1 EXEMPLO DE ALGORITMOS NO COTIDIANO

Início

Verifica se o interruptor está desligado;

Procura uma lâmpada nova;

Pega uma escada;

Leva a escada até o local;

Posiciona a escada;

Sobe os degraus;

Para na altura apropriada;

Retira a lâmpada queimada;

Coloca a lâmpada nova;

Desce da escada;

Aciona o interruptor;

Se a lâmpada não acender, então:

Retira a lâmpada queimada;

Coloca outra lâmpada nova

Senão

Tarefa terminada;

Joga a lâmpada queimada no lixo;

Guarda a escada;

Fim

3.2 COMO ESCREVER UM ALGORITMO

Os algoritmos são muito utilizados na área de programação, descrevendo as etapas que precisam ser efetuadas para que um programa execute as tarefas que lhe são designadas. Existem diversas formas de escrever um algoritmo, podendo ser citadas o pseudocódigo (ou português estruturado), fluxograma, diagrama de Chapin e descrição narrativa.

A sequência escrita no exemplo da troca da lâmpada estava em descrição narrativa, por exemplo. Esta forma não é muito utilizada em informática porque pode ser ambígua e dar margem a interpretações erradas.

3.2.1 MÉTODOS MAIS USADOS

Os dois tipos mais comuns são o pseudocódigo que utiliza uma forma mais estruturada, assemelhando-se àquelas utilizadas pelas linguagens de programação e o fluxograma que emprega figuras geométricas para ilustrar os passos a serem seguidos.

4 ALGORITMOS DE ORDENAÇÃO

Um tipo de algoritmo muito usado na resolução de problemas computacionais são os algoritmos de ordenação, que servem para ordenar/organizar uma lista de números ou palavras de acordo com a sua necessidade. As linguagens de programação já possuem métodos de ordenação, mas é bom saber como funcionam os algoritmos, pois há casos de problemas em que o algoritmo de ordenação genérico não resolve, às vezes é necessário modificá-lo.

Os mais populares algoritmos de ordenação são: Insertion Sort, Selection Sort, Bubble Sort, Comb Sort, Quick Sort, Merge Sort, Heap Sort e Shell Sort. Neste artigo serão estudados os algoritmos Bubble Sort, Selection Sort, e o Insertion Sort, explicando o funcionamento de cada um deles.

4.1 BUBBLE SORT

Bubble Sort é o algoritmo mais simples, mas o menos eficiente. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes (vide figura abaixo).

[pic 1]

4.1.1 FUNCIONAMENTO

- É verificado se o 3 é maior que 5, por essa condição ser falsa, não há troca.

- É verificado se o 5 é maior que 1, por essa condição ser verdadeira, há uma troca.

- É verificado se o 5 é maior que 2, por essa condição ser verdadeira, há uma troca.

- É verificado se o 5 é maior que 4, por essa condição ser verdadeira, há uma troca.

O método retorna ao início do vetor realizando os mesmos processos de comparações, isso é feito até que o vetor esteja ordenado.

TESTES

BubbleSort (Crescente)

Elementos

1º Ciclo

2º Ciclo

3º Ciclo

Média

100

0,0ms

0,0ms

0,0ms

0,0ms

1000

0,001ms

0,000ms

0,003ms

0,0013ms

10000

0,126ms

0.069ms

0,116ms

0,103ms

BubbleSort (Decrescente)

Elementos

1º Ciclo

2º Ciclo

3º Ciclo

Média

100

0,0ms

0,015ms

0,017ms

0,010ms

1000

0,016ms

0,015ms

0,022ms

0,017ms