Algoritmos de ordenação

Capítulo 3

Aula 4

Algoritmos de Ordenação

Os problemas considerados neste capítulo, fazem parte de uma classe de problemas combinatoriais. Em muitas aplicações, um conjunto de itens precisa ser rearranjado de acordo com alguma ordem específica.

Estamos sempre precisando de algoritmos para ordenar lista de clientes, produtos, alunos, arquivos e outros. Hoje o volume de dados é muito grande e os usuários cada vez mais exigentes quanto ao uso do seu tempo. Por isso, não podemos abrir mão de um algoritmo rápido e eficiente. Existem algoritmos clássicos de ordenação, com suas complexidades conhecidas e demonstrados através de simuladores.

Faremos um estudo comparativo dos algoritmos de ordenação (ou classificação) interna mais comuns, assumindo a mesma entrada para os diferentes algoritmos. Com isso, espera-se comparar o tempo de execução e apresentar as complexidades dos algoritmos.

Há cinco classes de algoritmos de ordenação interna:

1. Algoritmo de ordenação por troca 2. Algoritmo de ordenação por seleção 3. Algoritmo de ordenação por inserção

1) Algoritmo de ordenação por troca

O método de ordenação baseado em troca, consiste em intercalar pares de itens que não estão em ordem até que não exista mais pares. Existem dois algoritmos de troca: o bolha e o quicksort. Nesta seção veremos o algoritmo bolha. O quicksort será visto em capítulo posterior.

1. Bolha

O algoritmo de ordenação bolha é simples de entendimento e de fácil implementação. Está entre os mais conhecidos e difundidos métodos de ordenação de arranjos, mas não é um algoritmo eficiente.

O princípio do bolha é a troca de valores entre posições consecutivas, fazendo com que os valores mais altos (ou mais baixos) "borbulhem" para o final do arranjo (por isso o nome Bubblesort).

Para i = 1 até n - 1 faça

Para j = n até i+1 faça Se V [j] temp faça A[j] = A[j-1] j=j-1 A[j] = temp