Algoritmos de Ordenação

Algoritmos de OrdenaçãoNo nosso dia-a-dia, com freqüência, nos ocorre de termos de procurar dados em listas ou tabelas. Quando estes dados nos são apresentados de forma desordenada, nosso trabalho é muito mais difícil do que se eles estivessem previamente classificados ou ordenados. Por isso, estudaremos os principais algoritmos para ordenação ou classificação de dados.

Algoritmos de Ordenação1. Ordenação por Seleção

2. Ordenação por Inserção

3. Ordenação por troça

a. Método da Bolha (Bubble Sort)

b. Método de Divisão e Troca (Quick Sort)

ORDENAÇÃO INTERNA

MÉTODOS SIMPLES OU DIRETOS

1.Ordenação por Seleção

O método da ordenação por seleção consiste em ordenar os elementos de uma lista seguindo-se os seguintes passos:

Escolhe-se o menor elemento do vetor e troca-se com o primeiro elemento. Dos elementos restantes, seleciona-se o de mais baixo valor e troca-se com o segundo. E assim por diante, até que o vetor esteja todo ordenado.

Este algoritmo somente deve ser utilizado para classificar listas pequenas, pois é muito ineficiente.

Algoritmos de Ordenação

Ordenação por Seleção DiretaAO R D E N

62 3 4 51

i = 1 OA R D E N

OA D R E Ni = 2

OA D E R Ni = 3

OA D E N Ri = 4

RA D E N Oi = 5

Chaves Iniciais

VARIÁVEISVetor : VETOR[0..10] DE INTEIROi : INTEIROPROCEDIMENTO SELECAO (vetor:VETOR DE INTEIRO, tamanho: INTEIRO)VARIÁVEISi, j, menor : INTEIROx : elemento da listaINÍCIO PARA i DE 1 ATÉ tamanho-1 FAÇA menor i PARA j DE i+1 ATÉ TAMANHO FAÇA SE vetor [j] < vetor [menor] FAÇA menor j FIMPARA x vetor [menor] vetor [menor] vetor [i] vetor [i] x FIMPARAFIM

Algoritmos de Ordenação

INÍCIO

PARA i DE 1 ATÉ 10 FAÇA

LEIA vetor [i]

FIMPARA

SELECAO (vetor, 10)

PARA i DE 1 ATÉ 10 FAÇA

ESCREVA vetor [i]

FIMPARA

FIM

Algoritmos de Ordenação

1.Ordenação por Inserção

Inicialmente, considara-se o primeiro elemento ordenado. O segundo elemento é, então, inserido na sua posição correta em relação ao primeiro, resultando as duas primeiras posições ordenadas. A seguir, o terceiro elemento é inserido na sua posição correta em relação aos dois primeiros, resultando nas três primeiras posições ordenadas. E assim sucessivamente. Ao inserir cada novo elemento, deslocamentos são feitos, se necessários.

Obs: O tempo de execução desse método cresce exponencialmente em relação ao tamanho da tabela. Todavia, tem comportamento natural, isto é, é bom para listas quase ordenadas.

Algoritmos de Ordenação

AO O R E N OD O R E Ni = 3

Ordenação por InserçãoAO R D E N

62 3 4 51

i = 2 AO R D E N

AD E O R Ni = 4

AD E N O Ri = 5

RA D E N Oi = 6

Chaves Iniciais O R

VARIÁVEIS

Vetor : VETOR[1..10] DE INTEIRO

i, j, chave : INTEIRO

INÍCIO

PARA i DE 1 ATÉ 10 FAÇA

LEIA vetor [i]

FIMPARA

PARA j DE 2 ATÉ 10 FAÇA

chave vetor [j]

i j - 1

ENQUANTO ( i > 0 ) E (vetor[i] > chave ) FAÇA

vetor [i + 1] vetor [i]

i i - 1

FIMENQUANTO

VETOR [i + 1] chave

FIMPARA

FIM

Algoritmos de Ordenação

Algoritmo da bolha - Bubble Sort

• Idéia básica– Troca pares de elementos adjacentes que estão fora

de ordem– Faz múltiplas passagens pelo array até que as trocas

não sejam mais necessárias– Invariante

•A cada passagem coloca o maior elemento na posição correta, a última posição para aquela passagem

Obs: Esse método é um dos mais conhecidos e simples, mas um dos piores.

Algoritmo da bolha: execução12 8 3 21 99 1 início

8 12 3 21 99 1 Compara, troca (1, 2)

8 3 12 21 99 1 Compara, troca (2, 3)

8 3 12 21 99 1 Compara, não troca

8 3 12 21 99 1 Compara, não troca

8 3 12 21 1 99 Compara, troca (5, 6)

8 3 12 21 1 99 maior na posição final

Algoritmo da bolha: execução (cont.)

8 3 12 21 1 99 Passo 2

3 8 12 21 1 99 troca (1, 2)

3 8 12 21 1 99 não troca

3 8 12 21 1 99 não troca

3 8 12 1 21 99 troca (4, 5)

3 8 12 1 21 99 21 na posição

Algoritmo da bolha: execução (cont.)3 8 12 1 21 99 Passo 3

3 8 12 1 21 99 não troca

3 8 12 1 21 99 não troca

3 8 1 12 21 99 não troca

3 8 1 12 21 99 troca (3, 4)

3 1 8 12 21 99 troca (2, 3)

1 3 8 12 21 99 troca (1, 2)

3 8 1 12 21 99 12 na posição; passo 4

3 1 8 12 21 99 8 na posição; passo 5

1 3 8 12 21 99 FEITO

VARIÁVEIS

Vetor : VETOR[1..10] DE INTEIRO

i : INTEIRO

PROCEDIMENTO bublesort (vetor:VETORDE INTEIRO, tamanho: INTEIRO)

VARIÁVEIS

i, j, temp : INTEIRO

INÍCIO

PARA i DE 1 ATÉ tamanho FAÇA

PARA j DE 1 ATÉ TAMANHO-1 FAÇA

SE vetor [j] > vetor [j+1] FAÇA

temp vetor [j]

vetor [J] vetor [j+1]

vetor [j+1] temp

FIMSE

FIMPARA

FIMPARA

FIM

Algoritmos de Ordenação

INÍCIO

PARA i DE 1 ATÉ 10 FAÇA

LEIA vetor [i]

FIMPARA

bublesort (vetor, 10)

PARA i DE 1 ATÉ 10 FAÇA

ESCREVA vetor [i]

FIMPARA

FIM

Algoritmos de Ordenação

Algoritmo da bolha: uso

• quando se dispõe de uma quantidade de tempo enorme...– em situações reais, é duas vezes mais lento do que

os algoritmos de inserção direta e seleção direta– última escolha...

ORDENAÇÃO INTERNA

MÉTODOS SOFISTICADOS OU EFICIENTES

Ordenação por Particionamento ou Quicksort

• O Quicksort é o algoritmo mais rápido para ordenação interna já conhecido, sendo por isso o mais utilizado entre todos os algoritmos de ordenação para uma grande quantidade de situações.

• Princípio1. Dividir o problema de ordenar um conjunto de n itens

em dois problemas menores2. Ordenar independentemente os problemas menores3. Combinar os resultados para produzir a solução do

problema maior

Partição

• O procedimento de partição é uma parte complicada do método:– Deve-se rearranjar o vetor na forma A[Esq..Dir]

através da escolha arbitrária de um item x do vetor chamado pivô

– Ao final, o vetor A deverá ter duas partes, uma esquerda com chaves menores ou iguais que x e a direita com valores de chaves maiores ou iguais que x

Algoritmo Quicksort: Partição1. Escolher arbitrariamente um item do vetor e colocar

este valor em x

2. Percorrer o vetor a partir da esquerda até que um item A[i] x é encontrado; da mesma maneira, percorrer o vetor a partir da direita até que um item A[j] x é encontrado;

3. Como os itens A[i] e A[j] não estão na ordem correta no vetor final, eles devem ser trocados

4. Continuar o processo até que os índice i e j se cruzem em algum ponto do vetor

Funcionamento do Quicksort: Partição

• Ao final do processo, o vetor A[Esq..Dir] está particionado de tal forma que:– Os itens em A[Esq], A[Esq+1],..., A[j] são menores

ou iguais a x– Os itens em A[i], A[i+1],..., A[Dir] são maiores ou

iguais a x

Exemplo de Partição

AO R D E N

62 3 4 51

i = 2 OA R D E N

OA D R E Ni = 3

Chaves Iniciais D

• O pivô é escolhido como sendo A[(i+j) div 2]• Inicialmente, i=1 e j=6, e então x=A[3] = D• A varredura a partir da posição 1 pára no item O e a varredura

a partir da posição 6 pára em A, sendo os dois itens trocados• A varredura a partir da posição 2 pára em R e a varredura a

partir da posição 5 pára no item D, e então os dois itens são trocados

• Neste instante i e j se cruzam (i=3 e j=2), o que encerra o processo de partição

Procedimento Ordena

AO R D E N

62 3 4 51

i = 1 OA D R E N

OE R Ni = 3

ON Ri = 4

ROi = 5

Chaves Iniciais

A Di = 2

RA D E N Oi = 6

Procedimento PartiçãoVARIÁVEIS vetor : VETOR[0...10] DE INTEIRO i : INTEIRO PROCEDIMENTO quicksort(variavel vetor : VETOR DE

INTEIRO, primeiro : INTEIRO, último : INTEIRO)VARIÁVEIS menor : INTEIRO maior : INTEIRO separador : INTEIRO temp : INTEIRO INÍCIO menor primeiro maior último separador vetor[(primeiro + último) / 2]

Procedimento PartiçãoREPITA ENQUANTO vetor[menor] < separador FAÇA menor menor + 1 FIMENQUANTO ENQUANTO vetor[maior] > separador FAÇA maior maior - 1 FIMENQUANTO  SE menor <= maior FAÇA temp vetor[menor] vetor[menor] vetor[maior] vetor[maior] temp  menor menor + 1 maior maior - 1 FIMSE ATÉ QUE menor > maior

Procedimento PartiçãoSE primeiro < maior FAÇA quicksort(vetor, primeiro, maior) FIMSE SE menor < último FAÇA quicksort(vetor, menor, último) FIMSEFIMINÍCIO {Programa Principal} PARA i DE 1 ATÉ 10 FAÇA LEIA vetor[i] FIMPARA  quicksort(vetor, 1, 10)  PARA i DE 1 ATÉ 10 FAÇA ESCREVA vetor[i] FIMPARAFIM 

Analisando a procedure

• O vetor é uma variável global ao procedimento Partição

• Obs: note que o laço interno do algoritmo de partição só faz incrementos e decrementos; daí a velocidade do algoritmo

Referências

• Transparências disponibilizadas pelo Prof. Ziviani, a partir do Livro Projeto de Algoritmos com Implementação em Pascal e C, M. A. da Silva Bigonha e Nívio Ziviani, Campus

• Algoritmos e Estruturas de Dados, N. Wirth, Prentice-Hall

• Curso on-line Estrutura de Dados I, USP – São Carlos