Classificação
Ordenação de Dados
Ordenação e Pesquisa de Dados
Marco Antonio Montebello Júnior
[email protected]
Ordenação dos dados




Facilitar e aumentar a eficiência das operações
de pesquisa sobre esses dados
Pode ser crescente ou decrescente
A seqüência de entrada, normalmente, é um
vetor com n elementos
Outras possibilidades de estruturas de dados
como por exemplo, uma lista encadeada
Ainda mais...






Na prática os números a serem ordenados, raramente, são
valores isolados
Normalmente, cada número é componente de um conjunto de
dados denominado registro
E o conjunto de registros forma uma tabela
Cada registro contém uma chave, que é o valor a ser ordenado,
e demais valores que sempre acompanham a chave
Numa operação de ordenação, sempre que for preciso trocar a
posição de uma chave, será necessário alterar a posição de
todos os elementos do registro
Na prática, quando os registros possuem uma grande
quantidade de dados (além da chave), a ordenação é realizada
sobre um vetor (ou lista) de ponteiros para os registros, com o
objetivo de minimizar as operações de movimentação de dados
Exemplos
Contigüidade Física


As entradas são fisicamente rearranjadas (todos os
elementos de um registro são ordenados fisicamente)
Tabela não ordenada
Reg Chave Outros campos
1
3
xxx xxx xxx
2
7
yyy yyy yyy
3
5
zzz zzz zzz
4
1
kkk kkk kkk
5
4
ttt
ttt
ttt
6
2
uuu uuu uuu

Tabela ordenada
Reg Chave Outros campos
1
1
kkk kkk kkk
2
2
uuu uuu uuu
3
3
xxx xxx xxx
4
4
ttt
ttt
ttt
5
5
zzz zzz zzz
6
7
yyy yyy yyy
Exemplo
Vetor Indireto de Ordenação

As entradas são mantidas nas posições originais. A seqüência é
dada por um vetor gerado durante o processo de classificação
(não envolve movimentação dos registros em uma tabela).

Tabela desordenada
Reg Chave
1
3
2
7
3
5
4
1
5
4
6
2
Outros campos
xxx xxx xxx
yyy yyy yyy
zzz zzz zzz
kkk kkk kkk
ttt
ttt
ttt
uuu uuu uuu

Vetor de ordenação
1
2
3
4
5
6
Índice da tabela
4
6
1
5
3
2
Exemplo
Encadeamento


As entradas são mantidas nas posições originais.
É formada uma lista encadeada com a ordenação. Utiliza-se um
campo a mais na tabela para armazenamento da lista, e não mais
o vetor adicional (vetor indireto de ordenação). É preciso utilizar
um ponteiro para o primeiro elemento
Reg. Chave
Demais Campos
Próx.
1
3
xxx xxx xxx xxx xxx xxx 5
2
7
yyy yyy yyy yyy yyy yyy 3
5
zzz zzz zzz zzz zzz zzz 2
4
1
kkk kkk kkk kkk kkk kkk 6
5
4
ttt ttt ttt ttt ttt ttt
3
6
2
uuu uuu uuu uuu uuu uuu 1
4
Ponteiro para o
primeiro elemento
da tabela (reg. 4
contém chave 1)
Ordenação Interna versus
Ordenação Externa





A ordenação interna é utilizada num conjunto de dados
pequeno
Neste caso a ordenação pode ser realizada inteiramente
(ou quase inteiramente) na memória principal
A ordenação externa é utilizada num conjunto de dados
grandes
A conseqüência é que a ordenação não pode ser
realizada na memória principal
Nesse caso a ordenação é realizada sobre dados
armazenados na memória secundária (disco, fita, etc.)
Principais métodos de
ordenação interna

Ordenação por Inserção



Ordenação por Troca



Inserção Direta
Incrementos Decrescentes (Shell Sort)
Método da Bolha (Bubble Sort)
Método da Troca e Partição (Quicksort)
Ordenação por Seleção


Seleção Direta
Seleção em Árvore (Heapsort)
Ordenação por Inserção

Nesse método os elementos são inseridos em
sua posição correta, em relação aos elementos
já classificados

Duas possibilidades :


Inserção Direta
Método Shell
Inserção Direta




É o método mais simples
Utilizado para um conjunto pequeno de dados
Possui baixa eficiência
Nesse método o vetor a ser ordenado é dividido
em dois segmentos:


O primeiro segmento contém os elementos já
ordenados;
O segundo segmento contém os elementos a serem
ordenados
Algoritmo – Inserção Direta



Primeiro elemento está no vetor ordenado e os
demais no vetor desordenado;
Retirar o primeiro elemento do vetor
desordenado e colocá-lo no vetor ordenado, na
sua posição correta;
Repetir o processo para todos os elementos do
vetor desordenado.
Algoritmo – Inserção Direta
Const
TAM = 10
Tipos
v = vetor[1..TAM] de inteiros
Var
vet: v
i, j, k, temp: inteiro
achei: lógico
+-------------------------+
| Exemplo:
|
|
|
| 5 | 2
3
4
8
7 |
| 2
5 | 3
4
8
7 |
| 2
3
5 | 4
8
7 |
| 2
3
4
5 | 8
7 |
| 2
3
4
5
8 | 7 |
| 2
3
4
5
7
8 ||
+-------------------------+
Início
Para i = 1 até TAM Faça
leia (vet[i])
Fim-Para
Para i = 2 até TAM Faça
j = 1
achei = FALSO
Enquanto (j < i) E (NÃO achei) Faça
Se vet[i] < vet[j] Então
achei = VERDADEIRO
Senão
j = j + 1
Fim-Se
Fim-Enquanto
Se achei Então
temp = vet[i]
k = i - 1
Enquanto k >= j Faça
vet[k+1] = vet[k]
k = k – 1
Fim-Enquanto
vet[j] = temp
Fim-Se
Fim-Para
Fim.
/*
/*
/*
/*
/*
Compara o */
vet[i] com */
os que estão */
à sua */
esquerda */
/* Desloca o */
/* vetor para */
/* a direita */
Algoritmo – Outra versão
Const
TAM = 10
Tipos
v = vetor[1..TAM] de inteiros
Var
vet: v
i, j, k, temp: inteiro
achei: lógico
Início
Para i = 1 até TAM Faça
leia (vet[i])
Fim-Para
Para j = 2 até TAM Faça
chave = vet[j]
i = j - 1
Enquanto (i > 0) E (vet[i] > chave) Faça
vet[i + 1] = vet[i]
i = i - 1
Fim-Enquanto
vet[i+1] = chave
Fim-Para
Fim.
Incrementos Decrescentes
(Shell Sort)





Proposto por Ronald L. Shell (1959)
É uma extensão do algoritmo de inserção direta
A diferença com relação à inserção direta é o
número de segmentos do vetor
Na inserção direta é considerado um único
segmento do vetor onde os elementos são
inseridos ordenadamente
No método do Shell são considerados diversos
segmentos
Descrição do Método Shell Sort

A ordenação é realizada em diversos passos. A
cada passo está associado um incremento I, o
qual determina os elementos que pertencem a
cada um dos segmentos:


segmento 1 - vet[1], vet[1 + I], vet[1 + 2I], ...
segmento 2 - vet[2], vet[2 + I], vet[2 + 2I], ...
...

segmento k - vet[k], vet[k + I], vet[k + 2I], ...
Descrição do Método Shell Sort




A cada passo todos os elementos (segmentos) são
ordenados isoladamente por inserção direta.
No final de cada passo o processo é repetido para um
novo incremento I igual a metade do anterior, até que
seja executado um passo com incremento I = 1.
O valor do incremento I é sempre uma potência inteira
de 2. O valor do incremento inicial é dado por 2**NP,
onde NP é o número de passos para ordenar o vetor
(fornecido pelo usuário, NP é uma aproximação inicial).
Assim, para NP = 3 o valor do incremento em cada
passo seria:




I = 2 ** 3 = 8 (23)
I = 2 ** 2 = 4 (22)
I = 2 ** 1 = 2 (21)
I = 2 ** 0 = 1 (20)
Exemplo: NP = 2
Vetor original (Desordenado)
1
2
3
4
5
6
7
15 27 40 13 19 20 45

8
35
9
50
Primeiro passo: I = 2 ** NP = 4 (22)
1 5 9
2 6 10
3 7 11
15 19 50
27 20 41
40 45 25
10
41
11 12
25 10


4 8 12
13 35 10
Aplicando inserção direta em cada segmento
15 19 50
20 27 41
 Obtém-se o vetor
1
15
2
20
3
25
4
10
5
19
6
27
25 40 45
7
40
8
13
9
50
10 13 35
10
41
11
45
12
35
Exemplo: NP = 2

Segundo passo: I = I DIV 2 = 2 (I/2)
ou NP = NP - 1, I = 2 ** NP = 2 (21)
Segmento 1
1 3 5 7 9 11
15 25 19 40 50 45

Aplicando inserção direta em cada segmento:
15 19 25 40 45 50

Segmento 2
2 4 6 8 10 12
20 10 27 13 41 35
10 13 20 27 35 41
Obtém-se o vetor
1
15
2
10
3
19
4
13
5
25
6
20
7
40
8
27
9
45
10
35
11
50
12
41
Exemplo: NP = 2



1
10
Terceiro passo: I = I DIV 2 = 1
ou: NP = NP - 1, I = 2 ** NP = 1 (20)
Nesse último passo os elementos estão próximos das
suas posições finais, o que leva a um menor número de
trocas.
Aplicando inserção direta ao vetor obtido no passo
anterior obtém-se o vetor ordenado:
2
13
3
15
4
19
5
20
6
25
7
27
8
35
9
40
10
41
11
45
12
50
Algoritmo do Método Shell
Const TAM = 12
Tipos v = vetor[1..TAM] de inteiros
Var
vet: v
np, i, j, inc : inteiro
Início
Para i = 1 até TAM Faça
Leia (vet[i])
Fim-Para
Leia (np)
Para i = np até 0 Passo -1 Faça
inc = 2 ** i //2i
Para j = 1 até inc Faça
Método_Shell (vet, inc, j, TAM)
Fim-Para
Fim-Para
Fim.
Algoritmo do Método Shell
Procedimento Método_Shell (Ref vet, r, s, n)
Início
Var
i, j, k, temp: inteiro
achei: lógico
Para i = (s + r) até n passo r Faça
j = s
achei = FALSO
Enquanto (j < i) E (NÃO achei) Faça
Se vet[i] < vet[j] Então
achei = VERDADEIRO
Senão
j = j + r
Fim-Se
Fim-Enquanto
Se achei Então
temp = vet[i]
k = i + r
Enquanto k > (j - r) Faça
vet[k + r] = vet[k]
k = k - r
Fim-Enquanto
vet[j] = temp
Fim-Se
Fim-Para
Fim-Método_Shell
Ordenação por Troca




Durante o caminhamento no vetor, se dois elementos
são encontrados fora de ordem, suas posições são
trocadas
São realizadas comparações sucessivas de pares de
elementos
A estratégia de escolha dos pares de elementos
estabelece a diferença entre os dois métodos de
ordenação por troca.
Dois métodos principais:


Método da Bolha (Bubble Sort)
Método da Partição (Quick Sort)
Método da Bolha (Bubble Sort)



É um método bastante simples, porém lento
O nome bolha se deve ao fato de que os valores
flutuam até a sua correta posição como bolhas
O algoritmo é o seguinte:



A cada passo, cada elemento é comparado com o
próximo. Se o elemento estiver fora de ordem, a troca
é realizada;
Realizam-se tantos passos quantos necessários até
que não ocorram mais trocas.
Obs.: Logo no primeiro passo o maior valor vai
para o fim
Exemplo do Mecanismo do
Método Bolha
500
Passo 1: 85
Passo
Passo
Passo
Passo
Passo
2:
3:
4:
5:
6:
85
515
60
60
515
910
170
170
910
890
890
275
650
430
910
430
430
890
890
890
890
910
910
910
910
910
910
500
85 500
60
85
60 500
60
85 170
60
85 170
60
85 170
nenhuma troca
515
170
500
275
275
170
515
275
500
430
890
275
515
430
500
910
275
275
650
430
515
515
910
650
650
430
650
650
650
Algoritmo do Método Bolha
/*Nesse algoritmo, a cada passo, a variável k contém a última posição trocada.
Após esta, todas já estão classificadas.*/
Const
TAM = 20
Tipos
v = vetor[1..TAM] de inteiros
Var
vet: v
i, temp, lim, k: inteiro
troca: lógico
Início
Para i = 1 até TAM Faça
Leia (vet[i])
Fim-Para
troca = VERDADEIRO
lim = TAM - 1
Enquanto troca Faça
troca = FALSO
Para i = 1 até lim Faça
Se vet[i] > vet[i + 1] Então
temp = vet[i]
vet[i] = vet[i + 1]
vet[i + 1] = temp
k = i
troca = VERDADEIRO
Fim-Se
Fim-para
lim = k
Fim-Enquanto
Fim.
Método da Troca e Partição
(Quick Sort)




É o mais rápido entre os métodos apresentados
até o momento
E também o mais utilizado
Foi proposto por C. A. R. Hoare em 1962
Parte do princípio que é mais rápido classificar
dois vetores com n/2 elementos cada um, do
que um com n elementos (dividir um problema
maior em dois menores)
Descrição do Método Quick Sort


A parte mais delicada do método é o
particionamento do vetor
O vetor é particionado em três segmentos:



V[1], ..., V[i - 1]
(segmento 1)
V[i]
(segmento 2)
V[i + 1], ..., V[n]
(segmento 3)
A partição é realizada através da escolha
arbitrária de um elemento (V[i]) de modo que os
elementos no segmento 1 sejam menores, e os
elementos no segmento 3 sejam maiores do que
o elemento escolhido V[i]
Descrição do Método Quick Sort

Após a ordenação dos segmentos 1 e 3, tem-se
o vetor original classificado. O processo de
partição pode ser repetido para os segmentos 1
e3

Obs.: Quando um segmento apresenta um
número de elementos menor ou igual a M (um
número pré-estabelecido), aplica-se um método
simples de ordenação
Algoritmo do Quick Sort







Escolher arbitrariamente um elemento do vetor
(normalmente o meio) e colocá-lo em uma variável
auxiliar X;
Inicializar dois ponteiros I e J (I = 1 e J = n);
Percorrer o vetor a partir da esquerda até que se
encontre um V[I] >= X (incrementando o valor de I);
Percorrer o vetor a partir da direita até que se encontre
um V[J] <= X (decrementando o valor de J);
Trocar os elementos V[I] e V[J] (estão fora de lugar) e
fazer: I = I + 1 e J = J - 1;
Continuar esse processo até que I e J se cruzem em
algum ponto do vetor;
Após obtidos os dois segmentos do vetor através do
processo de partição, cada um é ordenado
recursivamente
Quicksort – Exemplo (1)
Quicksort – Exemplo (2)
Quicksort – Exemplo (3)
Quicksort – Exemplo (4)
Quicksort – Exemplo (5)
Quicksort – Exemplo (6)
Quicksort – Animação
Algoritmo em pseudocódigo
Procedimento QuickSort (esq, dir: inteiro)
Início
Var
x, i, j, aux: inteiro
i = esq
j = dir
x = v[(i + j) DIV 2]
Repita //Faça
Enquanto x > v[i] Faça
i = i + 1
Fim-Enquanto
Enquanto x < v[i] Faça
j = j - 1
Fim-Enquanto
Se i <= j Então
aux = v[i]
v[i] = v[j]
v[j] = aux
i = i + 1
j = j - 1
Fim-Se
Até Que i > j //Enquanto i < j
Se esq < j Então
QuickSort (esq, j)
Fim-Se
Se dir > i Então
QuickSort (i, dir)
Fim-Se
Fim.
Ordenação por Seleção




É realizada uma seleção sucessiva do menor (ou
maior) valor contido no vetor
A cada passo este menor (maior) valor é
colocado na sua posição correta
Repete-se o processo para o segmento que
contém os elementos não selecionados
Duas possibilidades:


Seleção direta
Seleção em árvore
Seleção Direta




A cada passo encontra-se o menor elemento
dentro do segmento com os elementos não
selecionados;
Troca-se este elemento com o primeiro elemento
do segmento;
Atualiza-se o tamanho do segmento (menos um
elemento);
Este processo é repetido até que o segmento
fique com apenas um elemento
Exemplo
19
10
10
10
10
10
10
10
25
25
13
13
13
13
13
13
10
19
19
15
15
15
15
15
18
18
18
18
17
17
17
17
35
35
35
35
35
18
18
18
17
17
17
17
18
35
19
19
15
15
15
19
19
19
35
25
13
13
25
25
25
25
25
35
TAM = 8
TAM = 7
TAM = 6
TAM = 5
TAM = 4
TAM = 3
TAM = 2
TAM = 1
Algoritmo da Seleção Direta
Const
TAM = 15
Tipos
v = vetor[1..TAM] de inteiros
Var
vet: v
i, j, temp, pos_menor: inteiro
Início
Para i = 1 até TAM Faça
Leia (vet[i])
Fim-Para
Para i = 1 até TAM - 1 Faça
pos_menor = i
Para j = i + 1 até TAM Faça
Se vet[j] < vet[pos_menor] Então
pos_menor = j
Fim-Se
Fim-Para
temp = vet[i]
vet[i] = vet[pos_menor]
vet[pos_menor] = temp
Fim-Para
Fim.
Seleção em Árvore (Heap Sort)

Utiliza uma estrutura de árvore binária para a
ordenação

A ordenação é realizada em duas fases
Seleção em Árvore (Heap Sort)
Fase 1

Monta-se uma árvore binária (heap) contendo todos os
elementos do vetor de forma que o valor contido em
qualquer nodo seja maior do que os valores de seus
sucessores. A árvore binária é estruturada no próprio
vetor da seguinte forma:



sucessor à esquerda de i: 2i + 1
sucessor à direita de i: 2i + 2
(se 2i + 1 < n)
(se 2i + 2 < n)
Transformação da árvore num heap: é realizada do
menor nível até a raiz, trocando-se cada nodo com o
maior de seus sucessores imediatos. Repete-se este
processo até cada nodo ser maior que seus sucessores
imediatos
Seleção em Árvore (Heap Sort)
Fase 2


Após a formação do heap segue-se a fase de
classificação propriamente dita, na qual o valor
que está na raiz da árvore (maior valor contido
na árvore) é colocado na sua posição correta,
trocando-o com o elemento de maior índice da
árvore (a árvore fica com 1 elemento a menos).
Este novo elemento colocado na raiz pode violar
a propriedade do heap, de modo que deve-se
restaurar o heap novamente. Este procedimento
é repetido até que a árvore fique com um único
elemento.
Exemplos de Heaps
98
98
66
10
10
66
98
98
80
66
98
44
24
32
11
66
Exemplos de Não Heaps
98
12
44
66
24
78
11
66
98
10
Heap – Exemplo (1)
Entrada:
Heap:
Heap – Exemplo (2)
Heap – Exemplo (3)
Heap – Exemplo (4)
Heap – Exemplo (5)
Comparação entre os Métodos


São apresentados quadros comparativos do
tempo gasto na ordenação de vetores com 500,
5000, 10000 e 30000 elementos, organizados de
forma aleatória, em ordem crescente
(1, 2, 3, 4, ..., n) e em ordem
decrescente (n, n-1, n - 2, ..., 1)
Em cada tabela, o método que levou menos
tempo para realizar a ordenação recebeu o valor
1 e os demais receberam valores relativos ao
mais rápido (valor 1)
Comparação entre os Métodos
500
Inserção 11.3
Shell
1.2
Quick
1
Seleção 16.2
Heap
1.5

5000 10000 30000
87
161
1.6
1.7
2
1
1
1
124 228
1.6
1.6
1.6
Ordem Aleatória
500
Inserção
1
Shell
3.9
Quick
4.1
Seleção 128
Heap
12.2
5000 10000 30000
1
1
1
6.8
7.3
8.1
6.3
6.8
7.1
1524 3066
20.8 22.4 24.6
Ordem Ascendente
Ordem Descendente


500
Inserção 40.3
Shell
1.5
Quick
1
Seleção 29.3
Heap
2.5
5000 10000 30000
305 575
1.5
1.6
1.6
1
1
1
221 417
2.7
2.7
2.9
Recomendações




Tamanho <= 50
Inserção
Tamanho <= 5000
Shell Sort
Até 1000 elementos o Shell é mais vantajoso
Tamanho > 5000
Quick Sort


Necessita de memória adicional por ser recursivo. Evitar
chamadas recursivas para pequenos intervalos. Colocar um
teste antes da recursividade (se n <= 50 inserção; se n <=
1000, shell sort)
Heap Sort

De 2 a 3 vezes mais lento que o quick sort. Seu tempo é
sempre  n log n, não importando a ordem dos elementos. Esse
método deve ser utilizado quando as aplicações não podem
tolerar eventuais variações no tempo esperado para ordenação