Algoritmos de

Ordenao e Pesquisa

Marco Antonio Moreira de Carvalho

Algoritmos e Estrutura de Dados

Bibliografia Bsica
l

Cormen, Leiserson, Rivest. Introduction

to Algorithms. 2nd edition. MIT Press,
2001. Captulos 2, 6, 7, 8.

Aho, Alfred V., Hopcroft, John F.,

Ullman, Jeffrey D., Data Structure and
Algorithms, Massachusetts: AddisonWesley, 1987. Captulo 8.

Ordenao e Pesquisa
l

Considerando um conjunto de dados:

l

Estas tarefas devem ser realizadas eficientemente

l

Organiz-los de acordo com algum critrio (>, <, , ,

etc.); ou
Encontrar algum que atenda um critrio especfico
(maior, menor, =, etc.).
O tempo para execut-las depende da quantidade de
dados envolvidos.

Aplicao direta: Organizao e manipulao de

dados.
3

Ordenao e Pesquisa

l
l
l
l

Os elementos so chamados de chaves;

Pode haver chaves de valores idnticos;
Os valores no necessariamente so sequenciais.
Chaves podem ser nmeros, strings, registros, etc.

Estrutura de Dados
l

Vetores
l

Mantm uma srie de elementos sequenciais

mantidos em uma ordem linear como um nico,
porm, com possibilidade de acesso individual;
Cada elemento possui um ndice que indica sua
posio no vetor e permite acess-lo diretamente;
Vetores tem tamanhos fixos.
ndice

Valor

15

16

23

42
5

Pesquisa
l

Dado um conjunto de n chaves {k1, k2, , kn}:

l

Determinar a existncia e/ou determinar a posio de

determinada chave ki;
Determinar a maior, a menor, etc.

Dada a sequncia de chaves abaixo, como

determinar a existncia da chave 8? No sabemos
se as chaves esto ordenadas
?

Mtodos de Pesquisa

Pesquisa Sequencial

Pesquisa Binria

Pesquisa Sequencial
l

Mtodo intuitivo:
l

Dada uma chave k, compar-la a cada chave no

vetor, caso haja uma igual, a chave est no vetor
Caso todas as chaves tenham sido comparadas e no
houve nenhuma igual, a chave no existe no vetor.

k=8
42

16

15

23

Chave encontrada!

Pesquisa Sequencial
Cdigo
!
! n, int k, int *posicao)!
int Sequencial(int A[], int
!
{!
!
int i;!
//sinaliza se a chave foi encontrada!
int achou = 0;!
!
!
//para cada chave!
for(i=0; i<n; i++)!
//compara com a chave de busca!
if(A[i] == k)!
!
{!
*posicao = i;! //se encontrou!
//armazena a posio!
achou = 1;!
!
}!
//indica se encontrou ou no!
! return achou;!
}!

Pesquisa Sequencial
Complexidade
int Sequencial(int A[], int n, int k, int *posicao)!
{!
int i;!
Custo Repeties
int achou = 0;!
!
!
!
for(i=0; i<n; i++)!
c1
!
!n!
if(A[i] == k)!
c2
!n-1!
{!
*posicao = i;!
achou = 1;!
}!
return achou;!
}!

Tempo = (n)

10

Pesquisa Sequencial
l
l

Exerccio
Como torn-la mais rpida?
l

2 verses.

Qual a complexidade desta pesquisa sequencial

aprimorada?
l
l
l

Se o elemento procurado for o primeiro?

Se o elemento procurado for o ltimo?
E na mdia?

11

Pesquisa Binria
l

Assume que as chaves esto ordenadas

l

A partir disto, possvel diminuir o espao de busca,

restringindo-o por faixas de valores.
Divide-se o problema ao meio seguidas vezes, at
que a chave desejada seja encontrada ou determinese sua inexistncia.

12

Pesquisa Binria
l
l

Determina a chave central do vetor;

Caso a chave pesquisada no seja a central, compare
seus valores
l

Se a chave pesquisada for menor, volte ao primeiro passo,

porm, considere o vetor do incio at o ponto da chave central;
Se a chave pesquisada for maior, volte ao primeiro passo,
porm, considere o vetor do ponto da chave central at o final.

k=8
4

15 16 23 42 49 51 62 70
13

Pesquisa Binria
l
l

Determina a chave central do vetor;

Caso a chave pesquisada no seja a central, compare
seus valores
l

Se a chave pesquisada for menor, volte ao primeiro passo,

porm, considere o vetor do incio at o ponto da chave central;
Se a chave pesquisada for maior, volte ao primeiro passo,
porm, considere o vetor do ponto da chave central at o final.

k=8
4

15 16 23 42 49 51 62 70
14

Pesquisa Binria
l
l

Determina a chave central do vetor;

Caso a chave pesquisada no seja a central, compare
seus valores
l

Se a chave pesquisada for menor, volte ao primeiro passo,

porm, considere o vetor do incio at o ponto da chave central;
Se a chave pesquisada for maior, volte ao primeiro passo,
porm, considere o vetor do ponto da chave central at o final.

k=8
4

15 16 23 42 49 51 62 70
15

Pesquisa Binria
l
l

Determina a chave central do vetor;

Caso a chave pesquisada no seja a central, compare
seus valores
l

Se a chave pesquisada for menor, volte ao primeiro passo,

porm, considere o vetor do incio at o ponto da chave central;
Se a chave pesquisada for maior, volte ao primeiro passo,
porm, considere o vetor do ponto da chave central at o final.

k=8
4

15 16 23 42 49 51 62 70

Chave encontrada!

16

Pesquisa Binria - Cdigo

!
! n)!
int PesquisaBinaria( int A[], int k, int
!
{!
//determina onde comea a busca!
int esquerda = 0; !
//determina onde termina a busca!
int direita = n-1; !
//determina a chave central!
int meio;!
!
!
//enquanto houver mais que !
while (esquerda <= direita) !
//uma chave no intervalo!
{!
meio = (esquerda+direita)/2;!//calcula a chave central!
!
!
//testa se a central a procurada!
!
! if (k == A[meio])!
!
return meio;!
//compara se menor!
else if (k < A[meio])!
!
direita = meio-1;!
//caso contrrio maior!
else!
!
esquerda = meio+1;!
!
}!
//retorna -1 se no encontrou!
return -1;
!
}!
17

Pesquisa Binria Complexidade

l

Melhor Caso
l

(1)
s

(n) = central: (1);

A chave pesquisada a primeiraTchave
T (n / 2) + (1) nos ou

Pior Caso
l

A chave procurada no existe no vetor, todas as

divises tero de ser feitas.

18

Teorema Mestre Resumido

l

Alguns algoritmos tm sua complexidades

determinadas atravs de recorrncias da forma

1. Se a > b k ento T (n) (n log a )

b

k
k
2
.
Se
a
=
b
ento
T
(
n
)

(
n
log
O Teorema Mestre estabelece trs casos que
podem ser simplificados: 3. Se a < b k ento T (n) (n k )

19

Pesquisa Binria Complexidade

l

Pelo segundo caso do Teorema Mestre, temos que

no pior caso a complexidade da Pesquisa Binria

20

Ordenao
l
l
l

Dado um conjunto de n chaves {k1, k2, , kn},

organiz-las tal que k 1 k 2 k n.
Por exemplo, dado (5, 3, 1, 2, 4), n = 5, temos 1 2
3 4 5.
Como ordenar a sequncia de chaves abaixo?
15

23

42

16

15

16

23

42
21

Ordenao - Tipos
l

Ordenao Interna
l

Ordenao externa
l

Todas as chaves na memria principal facilidade de

acesso.
Chaves na memria principal e em memria externa
movimentao de chaves entre as duas.

Diferentes mtodos para cada tipo.

22

Ordenao - Propriedades
l

Estabilidade
l

Manuteno da ordem relativa entre chaves de

mesmo valor;
l

Especialmente importante para casos em que cada

elemento possui mais de uma chave.

Adaptabilidade
l

Mtodos adaptveis tm o tempo de execuo

reduzido caso a entrada j esteja ordenada.

23

O que importante saber

sobre cada mtodo
l
l
l

Funcionamento;
Tipo de ordenao efetuada;
Complexidade
l

l
l
l

Comportamento de acordo com o caso, em termos da

quantidade de chaves.

Estabilidade;
Adaptabilidade;
Especificidades;

24

Mtodos de Ordenao
l
l
l
l
l
l
l
l

Bubble Sort (Mtodo Bolha)

Insertion Sort (Mtodo de Insero)
Selection Sort (Mtodo de Seleo)
Quicksort
Heapsort
Bucket Sort (Bin Sort)
Radix Sort
Merge Sort (Ordenao por Intercalao)
25

Bubble Sort
(Mtodo Bolha)
l

O mtodo mais simples:

l

Suponha chaves em um vetor vertical A. Valores

baixos so leves e valores altos so pesados .
Como bolhas, os valores leves sobem no vetor um
por vez, ao passo que os pesados descem.

Operao Troca(A[i], A[j]): os elementos das

posies i e j trocam de posio.

26

Bubble Sort - Funcionamento

l

Posio Chave
O vetor analisado
comparando-se pares de
1
?
chaves;
A mais leve sobe, a
2
?
mais pesada desce;
3
3
Caso j estejam na
posio correta, o
4
1
prximo par analisado.
Comparao: 1 e 3
Troca(A[4], A[3])
27

Bubble Sort Procedimento

de Troca
Troca(int *i, int *j)
{
int temp;
temp = *i;
*i = *j;
*j = temp;
}

Posio Chave
1

Comparao: 1 e 2
Troca(A[3], A[2])
28

Bubble Sort - Funcionamento

l

Posio Chave
O vetor analisado
comparando-se pares de
1
4
chaves;
A mais leve sobe, a
2
1
mais pesada desce;
3
2
Caso j estejam na
posio correta, o
4
3
prximo par analisado.
Comparao: 1 e 4
Troca(A[2], A[1])
29

Bubble Sort - Funcionamento

l

Posio Chave
O vetor analisado
comparando-se pares de
1
1
chaves;
A mais leve sobe, a
2
4
mais pesada desce;
3
2
Caso j estejam na
posio correta, o
4
3
prximo par analisado.
A chave mais leve chegou ao topo.
No ser utilizada em futuras comparaes.
30

Bubble Sort - Funcionamento

l

Posio Chave
O vetor analisado
comparando-se pares de
1
1
chaves;
A mais leve sobe, a
2
4
mais pesada desce;
3
2
Caso j estejam na
posio correta, o
4
3
prximo par analisado.
Comparao: 3 e 2
No h troca.
31

Bubble Sort - Funcionamento

l

Posio Chave
O vetor analisado
comparando-se pares de
1
1
chaves;
A mais leve sobe, a
2
4
mais pesada desce;
3
2
Caso j estejam na
posio correta, o
4
3
prximo par analisado.
Comparao: 2 e 4
Troca(A[3], A[2])
32

Bubble Sort - Funcionamento

l

Posio Chave
O vetor analisado
comparando-se pares de
1
1
chaves;
A mais leve sobe, a
2
2
mais pesada desce;
3
4
Caso j estejam na
posio correta, o
4
3
prximo par analisado.
A segunda mais leve chegou
sua posio.
33

Bubble Sort - Funcionamento

l

Posio Chave
O vetor analisado
comparando-se pares de
1
1
chaves;
A mais leve sobe, a
2
2
mais pesada desce;
3
4
Caso j estejam na
posio correta, o
4
3
prximo par analisado.
Comparao: 3 e 4
Troca(A[4], A[3])
34

Bubble Sort - Funcionamento

l

Posio Chave
O vetor analisado
comparando-se pares de
1
1
chaves;
A mais leve sobe, a
2
2
mais pesada desce;
3
3
Caso j estejam na
posio correta, o
4
4
prximo par analisado.
Chaves ordenadas.
35

Bubble Sort - Cdigo

// Para cada

for(i=0; i<n-1; i++)!

{!
//
for(j=n-1; j>i; j--)!
//
//
if(A[j] < A[j-1])!
Troca(&A[j], &A[j-1]);!//
}!

bolha , exceto a ltima!

Percorre o vetor, exceto as chaves j !

ordenadas!
Compara os pares!
Se for mais

leve , troca as posies!

36

Bubble Sort Complexidade

Custo
1 for(i=0; i<n-1; i++)!
{!
2
for(j=n-1; j>i; j--)!
3
if(A[j] < A[j-1])!
4
Troca(&A[j], &A[j-1]);!
}!

!
c1
!
c2
c3
!

c4

Repeties
!n!

!n-i!
!n-i!

!n-i!

37

 n n
n n
+ c3
+
= c1 n + c2
2
2

Bubble Sort Complexidade

c 2 + c3 + c4 2 c1
=
n +
2

Tempo = O(n2)

38

Bubble Sort Resumo

l
l
l
l

l
l

Tipo de Ordenao: Interna.

Complexidade: O(n2).
Quantidade de dados: Poucos.
Especificidades: Complexidade fixa e cdigo
compacto.
Estabilidade: Sim.
Adaptabilidade: No. A implementao clssica
realiza a mesma quantidade de operaes mesmo
se as chaves j estiverem ordenadas.
39

Insertion Sort
(Mtodo de Insero)
l

Analogia com a
organizao de cartas de
baralho na mo;
Cartas so recebidas e
colocadas na mo
aleatoriamente;
Durante a organizao,
cada carta colocada no
seu lugar certo, uma por
vez, deslocando as
demais.

Extrado de Cormen, Leiserson, Rivest, (2001).

40

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.
6

Chave 4 na posio errada.

41

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.
6

Valor da chave armazenado.

Move-se as outras chaves para abrir o espao.

42

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Valor da chave armazenada inserido na

posio certa.
43

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Chaves nas posies corretas.

44

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Chaves 5 na posio errada

45

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Valor da chave armazenado.

Move-se as outras chaves para abrir o espao.

46

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Valor da chave armazenada inserido na

posio certa.
47

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Chave na posio errada.

48

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Valor da chave armazenado.

Move-se as outras chaves para abrir o espao.

49

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Valor da chave armazenada inserido na

posio certa.
50

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Chave na posio errada.

51

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Valor da chave armazenado.

Move-se as outras chaves para abrir o espao.

52

Insertion Sort - Funcionamento

l
l

Compara-se os pares de chaves;

Cada chave colocada na posio correta
l

Para isso, outras so movidas.

Caso j esteja na posio certa, passa-se ao

prximo par.

Valor da chave armazenada inserido na

posio certa.
Chaves ordenadas.
53

Insertion Sort - Cdigo

int ChaveAtual;!
//Varivel auxiliar para as comparaes!
!
//Para cada uma das chaves, exceto a ltima!
for(j=1; j<n; j++)!
{!
ChaveAtual = A[j];!
//Chave comparada atualmente!
i = j-1;!
! !
while(i>=0 && A[i] > ChaveAtual)!
//Compara com as demais chaves!
{!
A[i+1] = A[i];!
//Abre o espao entre as chaves maiores !
i--;!
}!
!
A[i+1] = ChaveAtual;!
//Insere a chave na posio correta!
}!

54

Insertion Sort - Complexidade

Custo Repeties
1 for(j=1; j<n; j++)!
{!
2
ChaveAtual = A[j];!
3
i = j-1;!
! !
4
while(i>=0 && A[i] > ChaveAtual)!
! {!
5
A[i+1] = A[i];!
6
i--;!
! }!
!
7
A[i+1] = ChaveAtual;!
}!

c1
!
c2
c3
!
!

c4

!n!

!n-1!
!n-1!

!j!

!
!

!j-1
!j-1

!n-1!

c5
c6

!!
!!

!
!
c7

55

Insertion
c c c
c c cSort

- Complexidade

= + + n + c + c + c + + + + c n (c
4

+ c3 + c 4 +

Pior caso = O(n2)

56

Insertion Sort Resumo

l
l
l
l

l
l

Tipo de Ordenao: Interna.

Complexidade: O(n2).
Quantidade de dados: Poucos.
Especificidades: A complexidade, apesar de alta,
no fixa.
Estabilidade: Sim.
Adaptabilidade: Sim.

57

Selection Sort
(Mtodo de Seleo)
l
l

Princpio simples;
A cada iterao procura a chave de menor valor ainda
no ordenada;
Depois de encontrada, ela inserida na posio correta
do vetor.

58

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave ?
Posio

59

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 6
Posio

60

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 4
Posio

61

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 3
Posio

62

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 3
Posio

63

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 1
Posio

64

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 1
Posio

65

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 3
Acelerando

Posio

66

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 3
Posio

67

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave ?
Posio

68

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 4
Acelerando

Posio

69

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 4
Posio

70

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave ?
Posio

71

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 5
Acelerando

Posio

72

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Menor chave 5
Posio

73

Selection Sort - Funcionamento

l

A cada iterao procura a chave de menor valor

ainda no ordenada;
Depois de encontrada, ela inserida na posio
correta.

Chaves ordenadas.
74

Selection Sort - Cdigo

for(i=0; i<n-1; i++)!
{!
MenorChave = A[i];!
!
indice = i;!
!
!
!
!
!
!
!
!
!

for(j=i+1; j<n; j++)!

{!
if(A[j] < MenorChave)!
! {!
!
MenorChave = A[j];!
!
indice = j;!
! }!
}!

!
!

Troca(&A[i], &A[indice]);!
}!

//para cada uma das chaves,!

//exceto a ltima!
//inicializa o menor valor!
//e menor ndice!
!
//Entre as chaves no ordenadas!
!

//Procura a menor!
!
//atualiza as variveis!
!

!
!
//Troca de lugar com a primeira!
//chave no ordenada!

75

Selection Sort - Complexidade

Custo
for(i=0; i<n-1; i++)!
{!
MenorChave = A[i];!
!
indice = i;!
!
!
!
!
!
!
!
!
!

for(j=i+1; j<n; j++)!

{!
if(A[j] < MenorChave)!
! {!
!
MenorChave = A[j];!
!
indice = j;!
! }!
}!

Troca(&A[i], &A[indice]);!
}!

c1 !
!
c2 !
c3 !
!
c4 !
!
c5 !
!
c6 !
c7 !
!
!
!
c8 !
!

Repeties
!

!n!

!
!

!n-1!
!n-1!

!n-i!

!n-i

!!

!
!

!n-i
!n-i!

!!

!n-1!

76

c c c c
c4 c5 c6 c7 2

+ + + n + c1 + c2 + c3 + 4 + 5 + 6 + 7 + c8 n (c2 + c3 +
2 2 2 2
2 2 2 2

Selection Sort - Complexidade

Tempo = O(n2)
77

Selection Sort Resumo

l
l
l
l
l

Tipo de Ordenao: Interna.

Complexidade: O(n2).
Quantidade de dados: Poucos.
Especificidades: A complexidade fixa.
Estabilidade: Depende da implementao. A
apresentada estvel.
Adaptabilidade: No.

78

Quicksort
l

Provavelmente o mais eficiente para ordenao

interna;
Baseado no paradigma Dividir-e-Conquistar ;
l

l
l
l

Divide o problema original em problemas menores,

semelhantes.

Procedimento recursivo;
Complexidade varia com o caso;
Funcionamento no trivial como os anteriores.

79

Quicksort
l

Trs passos bsicos:

l

Dividir:Escolha uma chave piv e divida o vetor em

dois subvetores (possivelmente vazios) tal que as
chaves do subvetor esquerda sejam menores que a
chave piv, que por sua vez menor que as chaves
do subvetor direita;
Conquistar: Ordene os subvetores recursivamente,
dividindo-os tambm;
Combinar: Uma vez que todos os subvetores estejam
ordenados, o vetor original tambm estar.
80

Quicksort - Funcionamento
l

Escolhe-se o piv: primeira chave do vetor (existem outras

estratgias);
Percorre-se o vetor de esquerda a direita, comparando-se as
chaves;
Menores para a esquerda, maiores para a direita.

Piv

Chave 1 permanecer esquerda.

81

Quicksort - Funcionamento
l

Percorre-se o vetor de esquerda a direita, comparando-se as

chaves;
Menores para a esquerda, maiores para a direita.

Piv

Diviso

Chave 4 permanecer direita.

82

Quicksort - Funcionamento
l

Percorre-se o vetor de esquerda a direita, comparando-se as

chaves;
Menores para a esquerda, maiores para a direita.

Piv

Diviso

Chave 1 permanecer esquerda.

83

Quicksort - Funcionamento
l

Percorre-se o vetor de esquerda a direita, comparando-se as

chaves;
Menores para a esquerda, maiores para a direita.

Piv

Diviso

Chave 4 permanecer direita.

84

Quicksort - Funcionamento
l

Percorre-se o vetor de esquerda a direita, comparando-se as

chaves;
Menores para a esquerda, maiores para a direita.

Piv

Diviso

Chave 9 permanecer direita.

85

Quicksort - Funcionamento
l

Percorre-se o vetor de esquerda a direita, comparando-se as

chaves;
Menores para a esquerda, maiores para a direita.

Piv

Diviso

Chave 2 permanecer esquerda.

86

Quicksort - Funcionamento
l

Percorre-se o vetor de esquerda a direita, comparando-se as

chaves;
Menores para a esquerda, maiores para a direita.

Piv

Diviso

Chave 6 permanecer direita.

87

Quicksort - Funcionamento
l

Percorre-se o vetor de esquerda a direita, comparando-se as

chaves;
Menores para a esquerda, maiores para a direita.

Piv

Diviso

Chave 5 permanecer direita.

88

Quicksort - Funcionamento
l

Percorre-se o vetor de esquerda a direita, comparando-se as

chaves;
Menores para a esquerda, maiores para a direita.

Piv

Diviso

Chave 5 permanecer direita.

89

Quicksort - Funcionamento
l

Inserir o piv na posio correta.

Piv

Diviso
90

Quicksort - Funcionamento
l
l

Inserir o piv na posio correta;

Agora o vetor deve ser dividido em duas partes:
l
l

Do incio a antes do piv;

De depois do piv ao final.

91

Quicksort - Funcionamento
l
l

Cada metade do vetor submetida ao mesmo processo

individualmente, podendo ser dividida novamente;
No fim, junta-se as partes ordenadas.

Piv
92

Quicksort - Funcionamento
3

93

Quicksort - Cdigo
int Particao(int A[], int esquerda, int direita) !
!
{!
!
int i;!
!
int j;!
!
!
//varivel de controle!
i = esquerda;!
//percorre o subvetor!
for(j=esquerda+1; j<=direita; j++) !
!
{!
//se a chave analisada!
if (A[j] < A[esquerda]) !
//for menor que o piv!
! {!
!
i++;!
//troca as chaves de !
Troca(&A[i], &A[j]);!
//posio!
}!
!
}!
!
!
//insere o piv na !
Troca(&A[esquerda], &A[i]);!
//posio correta!
!
return i;!
}!
!
94

Quicksort - Cdigo

Quicksort(int A[], int esquerda, int direita) !

{!
!
int p;!
//piv!
!
!
if (direita > esquerda) !
{!
//se o subvetor no !
p = Dividir(A, esquerda, direita);!
//for vazio !
Quicksort(A, esquerda, p-1);!
//ele ordenado!
Quicksort(A, p+1, direita);!
//divide em parte esquerda!
}!
//e parte direita!
}!

95

Quicksort - Complexidade
int Particao(int A[], int esquerda, int direita) !
{!
int i;!
int j;!
!
i = esquerda;!
1 for(j=esquerda+1; j<=direita; j++) !
{!
2
if (A[j] < A[esquerda]) !
! {!
3
i++;!
4
Troca(&A[i], &A[j]);!
}!
}!
!
Troca(&A[esquerda], &A[i]);!
!
return i;!
}!

!
!
Custo
!
c1 !
!
c2 !
!
c3 !
c4 !

Repeties
!

!n!

!n-1!

!
!

!n-1!
!n-1!

Tempo = (n)
96

Quicksort - Complexidade
l

Suponha que para ordenar n chaves, a

complexidade dada pela recorrncia
T(n) = T(i)+T(n-i-1) + (n)

l
l

Em que i representa o tamanho da partio obtida e

T(0) = (1).
O pior caso do Quicksort ocorre quando as
parties nunca so eficientes: o vetor dividido em
um parte com n-1 chaves e outra com 0 chaves, ou
seja, no h partio efetiva em nenhuma das
chamadas recursivas;
Isto ocorre quando o vetor j est ordenado;
97

Quicksort - Complexidade
l

No pior caso, para i=0, temos ento:

No melhor caso, para i=

perfeita), temos: n

ou

-1 (partio

n
T (n) T + T n 1 + (n)
2
2

n
T (n) 2T + (n)
2
T (n) = O(n log n)

(Pelo Teorema Mestre, caso 2)

98

Quicksort - Complexidade
l

Para o caso mdio, suponhamos que todas as

possveis parties (0 e n-1, 1 e n-2, , n-1 e 0)
possuem a mesma probabilidade de acontecer, ou
seja, 1/n para cada;
Isto quer dizer que, na rvore de recurso, parties
boa e ruins se alternaro aleatoriamente em cada
nvel;
razovel pensar que elas se alternam em cada
nvel deterministicamente no caso mdio.

99

Quicksort - Complexidade
l

A pior partio

A melhor partio

100

Quicksort - Complexidade
l

[(n-1)/2]-1

Uma m partio seguida por uma boa partio

Temos 3 subvetores, obtidos aos custos

(n)+(n-1) = (n)
l

O custo das boas parties absorvem o das ms.

101

Quicksort - Complexidade
l

Logo, se a complexidade para boas parties

(nlogn), para o caso mdio temos uma constante
maior, resultando ainda em O(nlogn).
Esta no uma prova da complexidade, uma
intuio sobre a mesma, que pode ser confirmada
matematicamente.

102

Quicksort Resumo
l
l

l
l

Tipo de Ordenao: Interna.

Complexidade: O(n2) no pior caso e O(nlogn) no melhor caso
e tambm no caso mdio.
Quantidade de dados: Muitos.
Especificidades: Estratgias de seleo de piv e partio
podem influenciar o tempo de execuo. Apesar de ser
quadrtico no pior caso, o caso mdio justifica sua utilizao.
Estabilidade: Depende da partio. A verso apresentada
instvel. Uma verso in place estvel. Infelizmente,
mtodos eficientes so instveis.
Adaptabilidade: No.
103

Heapsort
l
l
l

Utiliza uma estrutura de dados especfica: o Heap

rvore binria completa em todos os nveis, exceto
o ltimo (possivelmente);
Tambm pode ser visto como um vetor e possui as
seguintes propriedades:
l
l

A raiz da rvore armazenada em A[1];

Para um dado n i:
l O seu n pai
;
l Seu filho esquerda 2i;
l Seu filho direita 2i+1;

104

Heapsort - Heaps

16
2

14

10

10

10

16 14 10 8

105

Heaps
l

Os heaps podem ser mximos ou mnimos;

l
l

No Heapsort, chaves so inseridas em um heap

mximo;
l

Raiz com o maior valor e pais com valor que os

filhos MaxHeap.
Raiz com o menor valor e pais com valor que os
filhos MinHeap.

Ao serem retiradas do heap, as chaves estaro

ordenadas;

necessrio manter as propriedades do heap

durante as inseres e excluses.
106

Heapsort Funcionamento
l

Utiliza 3 operaes sobre heaps:

l

MAX-HEAPIFY: mantm a propriedade do heap

mximo;
BUILD-MAX-HEAP: produz um heap a partir de um
vetor de entrada;
HEAPSORT: ordena o vetor que representa o heap.

107

Heapsort MAX-HEAPIFY
l

Cada subrvore deve ser um heap mximo,

portanto, um n pai no pode ser maior que os ns
filhos;
Caso o n pai seja menor que um dos filhos, ele
trocar de posio com o maior deles;
aplicado recursivamente para garantir que uma
mudana realizada no viola a propriedade em
outras subrvores.

108

Heapsort MAX-HEAPIFY
4
14
8

10

109

Heapsort

14
MAX-HEAPIFY
4
5
4

10

10
6
9

110

Heapsort

14
MAX-HEAPIFY
4
5
8

10

10
6
9

111

MAX-HEAPIFY - Cdigo
void MAX_HEAPIFY(int A[], int i, int n){! !!
int esquerdo;!
//determina o filho esquerdo!
int direito;!
//determina o filho direito!
!
int maior;!
!

!
!
!
if(esquerdo <= n && A[esquerdo] > A[i])!//se o filho esquerdo for!
//maior que o pai, registra!
!
maior = esquerdo;!
!
else!
//seno!
!
maior = i;!
//o maior o pai mesmo!
//se o direito maior que o maior!
if (direito <= n && A[direito] > A
!
[maior])!
//registra!
!
maior = direito;!
!
if(maior != i)
{!
//se o maior no o pai!
Troca(&A[i], &A[maior]);!
!
//troca as posies!
!
MAX_HEAPIFY(A, maior, n);!
//verifica se a subrvore viola a !
}!
//propriedade!

esquerdo = 2*i;!
direito = 2*i+1;!

}!

!
!
!

112

MAX-HEAPIFY - Complexidade
l
l
l

T(

(1) para fazer as trocas em um mesmo nvel;

Uma subrvore pode ter no mximo tamanho 2n/3;
No pior caso ento, a complexidade dada pela
recorrncia

=T

(Pelo teorema mestre, caso 2)

113

Heapsort BUILD-MAX-HEAP
l

l
l

Utiliza o procedimento anterior para transformar um

vetor em um heap mximo;
aplicado de baixo para cima na rvore;
Da metade do vetor em diante esto as folhas da
rvore, ento o procedimento aplicado deste
ponto para trs no vetor;
A propriedade do heap mantida pelo
procedimento anterior.

114

1
4

Heapsort BUILD-MAX-HEAP
2
16

10

14

16

10

14

7
115

Heapsort BUILD-MAX-HEAP
4
2

16

10

14

116

Heapsort BUILD-MAX-HEAP
4
2

14

16

10

117

Heapsort BUILD-MAX-HEAP
4
2

10

14

16

10

118

Heapsort BUILD-MAX-HEAP
4
2

16

10

14

10

119

Heapsort BUILD-MAX-HEAP
16
2

14

10

10

120

BUILD-MAX-HEAP - Cdigo

void BUILD_MAX_HEAP(int A[],int n)!

{!
int i;!
!
!
//Para cada uma das subrvores,!
for(i=n/2; i>0; i--)!
//verifica corrige a propriedade !
MAX_HEAPIFY(A, i, n);!
//do heap!
}!
//folhas no so verificadas!

121

BUILD-MAX-HEAP
Complexidade
l
l

Aparentemente, a complexidade O(nlogn);

Porm, analisando-se a quantidade mxima de ns
por nvel do heap, e a quantidade de nveis,
possvel provar que a complexidade do
procedimento pode ser limitada por O(n);
Em outras palavras, construir um heap a partir de
um vetor aleatrio possvel em tempo linear.

122

Heapsort - Funcionamento
l
l

l
l

Inicialmente constri um heap (BUILD-MAX-HEAP);

A maior chave estar na raiz do heap, ento ela
ser a ltima chave na ordenao ela removida
do heap;
A nova raiz pode violar a propriedade do heap,
portanto, aplica-se o procedimento MAX-HEAPIFY;
Agora, a segunda maior chave est na raiz, ela ser
a penltima na ordenao final;
E assim por diante
A rvore diminui a cada remoo.
123

16

Heapsort - Funcionamento
10

14
8
2

7
4

124

14

Heapsort - Funcionamento
10

8
4

16

Como esta chave veio

parar aqui?

125

10

Heapsort - Funcionamento
9

8
4
2

7
14

16

126

Heapsort - Funcionamento
3

8
4
i

10

7
14

16

127

Heapsort - Funcionamento

7
4
10

2
14

16

128

Heapsort - Funcionamento
3

4
i

1
10

2
14

16

129

Heapsort - Funcionamento
3

2
i

1
10

7
14

16

130

Heapsort - Funcionamento
1

2
4
10

7
14

16

131

Heapsort - Funcionamento

1
4
10

7
14

16

132

Heapsort - Funcionamento
4

14

10

16

10

14

16
133

Heapsort - Cdigo
void HEAPSORT(int A[], int n)!
{!
int i;!
!
BUILD_MAX_HEAP(A, n-1);!
!
for(i=n-1; i>0; i--)!
{!
Troca(&A[1], &A[i]);!
!
MAX_HEAPIFY(A, 1, i-1);!
}!
}!

!
!

!
!
//constri o heap inicial!
!
//para cada chave!
//coloca a raiz do heap na !
//posio correta da ordenao!
//verifica e corrige a!
//propriedade do heap!

134

Heapsort - Complexidade
void HEAPSORT(int A[], int n)!
{!
int i;!
!
BUILD_MAX_HEAP(A, n-1);!
!
for(i=n-1; i>0; i--)!
{!
Troca(&A[1], &A[i]);!
!
MAX_HEAPIFY(A, 1, i-1);!
}!
}!

Custo
O(n)
!
c1!
!
c3!
O(logn)

Repeties
!

!1!

!n!

!
!

!n-1!
!n-1!

!
!
!
!
!
135

Heapsort - Complexidade

Tempo = O(nlogn)

136

Heapsort Resumo
l
l
l
l

l
l

Tipo de Ordenao: Interna.

Complexidade: O(nlogn) no pior caso.
Quantidade de dados: Muitos.
Especificidades: Melhor complexidade, porm, uma
boa implementao do Quicksort melhor na
prtica, devido a questes de hardware (cache).
Estabilidade: No.
Adaptabilidade: No.

137

Bucket Sort (Bin Sort)

l

Pressupe que a entrada consiste em nmeros

inteiros distribudos uniformemente sobre um
intervalo
l

l
l

Ou seja, que h um limite nos valores das chaves.

O intervalo ento dividido em n subintervalos de

tamanhos iguais, os chamados buckets (baldes);
Cada chave vai para o balde correspondente sua
faixa de valor
l

Considerando a uniformidade da distribuio, no

esperamos muitas chaves em um mesmo balde.

138

n A[i]

Bucket Sort Funcionamento

l

Cada balde posteriormente ordenado,

isoladamente dos demais;
Considerando o limite [0,1), e chaves com dois
dgitos decimais, determinamos o nmero de baldes
como 10 (0, 9).
A funo para determinao do ndice balde correto

139

Bucket Sort Funcionamento

B
0

/
A

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

140

Bucket Sort Funcionamento

B
0

7
8

/
A

0,78

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

141

Bucket Sort Funcionamento

B
0

/
0,17

1
2

7
8

/
A

0,78

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

142

Bucket Sort Funcionamento

B
0

1
2

0,17

0,39

3
4

7
8

/
A

0,78

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

143

Bucket Sort Funcionamento

B
0

0,17

0,26

0,39

7
8

/
A

0,78

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

144

Bucket Sort Funcionamento

B
0

0,17

0,26

0,39

0,72

/
A

0,78

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

145

Bucket Sort Funcionamento

B
0

0,17

0,26

0,39

7
8

0,72

0,78

9
A

0,94

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

146

Bucket Sort Funcionamento

B
0

0,17

0,21

0,39

7
8

/
0,26

0,78

0,72

9
A

0,94

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

147

Bucket Sort Funcionamento

B
0

0,12

0,17

0,21

0,26

0,39

0,78

7
8

0,72

9
A

0,94

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

148

Bucket Sort Funcionamento

B
0

0,12

0,17

0,23

0,21

0,39

7
8

/
0,26

0,72

0,78

9
A

0,94

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

149

Bucket Sort Funcionamento

B
0

0,12

0,17

0,23

0,21

0,39

0,68

0,72

0,78

/
0,26

9
A

0,94

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

150

Bucket Sort Funcionamento

B
0

0,12

0,17

0,23

0,21

0,39

0,68

0,72

0,78

/
0,26

Balde desordenado.

9
A

0,94

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

151

Bucket Sort Funcionamento

B
0

0,12

0,17

0,21

0,23

0,39

0,68

0,72

0,78

/
0,26

9
A

0,94

0,78

0,17

0,39

0,26

0,72

0,94

0,21

0,12

0,23

0,68

152

Bucket Sort Pseudo Cdigo

void BucketSort(int A[], int n)!
{!
int i;!
!
for(i=0; i<n; i++)!
InserirLista (B[int floor(n*A[i])], A[i]);!
!
for(i=0; i<n-1; i++)!
!
InsertionSortLista(&B[i])!
!
ConcatenarListasEncadeadas(n-1);!
}!

153

Bucket Sort Complexidade

void BucketSort(int A[], int n)!
{!
int i;!
!
Custo
!
!
c1!
for(i=0; i<n; i++)!
O(1)
InserirLista!
!
!
c3!
for(i=0; i<n-1; i++)!
O(ni2)
!
InsertionSortLista(&B[i]);!
!
ConcatenarListasEncadeadas(n-1);!
}!

!
!
!
!

Repeties
!n!
!n-1!
!n-1!
!n-1!

154

Bucket Sort - Complexidade

l

O custo das sucessivas chamadas a ordenao por

insero pode ser calculado pela recorrncia

Em que ni denota a quantidade de chaves no balde i;

Tomando as expectativas de ambos os lados e usando a
linearidade de expectativa, temos:

E[T (n)] = E (

n 1

= (n) + E[O
0

n 1

= ( n ) + O ( E
1550

Bucket Sort - Complexidade

l
l

l
l

O valor esperado para

2-1/n;
Substituindo na ltima equao, temos

Desta maneira, o Bucket Sort linear;

Pode ser provado que, mesmo a entrada no sendo
uma distribuio uniforme o Bucket Sort ainda
executar em tempo linear.

156

Bucket Sort Resumo

l
l
l
l

l
l

Tipo de Ordenao: Interna.

Complexidade: O(n).
Quantidade de dados: Muitos, porm, com valores
limitados.
Especificidades: Pressupe caractersticas da
entrada, e a implementao depende de tais
caractersticas. Um Bucket Sort com apenas dois
buckets na verdade o Quicksort (com pivoteamento
ruim).
Estabilidade: Depende do algoritmo de ordenao
interna dos buckets.
Adaptabilidade: Depende do algoritmo de ordenao
interna dos buckets.
157

Radix Sort
l
l

l
l

Utiliza o conceito do Bucket Sort;

Pressupe que as chaves de entrada possuem
limite no valor e no tamanho (quantidade de
dgitos);
essencial utilizar um segundo algoritmo estvel
para realizar a ordenao;
Ordena nmeros um digito de cada vez;
l
l

A partir do menos significativo;

Ou a partir do menos significativo.

158

Radix Sort
l

Como os valores possuem limite, e a quantidade de

dgitos fixa, possvel aplicar o Bucket Sort para
cada nvel;
l

Cria-se um balde para cada possvel valor dos dgitos

(0-9, ao invs de para cada faixa de valores), de
modo a no ser necessrio ordenar os baldes
internamente.
O Bucket Sort linear neste caso, uma vez que no
necessrio ordenar os baldes isoladamente.

159

Radix Sort - Funcionamento

l

A partir dos dgitos menos significativos, ordene as

chaves.
3
4
6
8
4
7
3

2
5
5
3
3
2
5

9
7
7
9
6
0
5
160

Radix Sort - Funcionamento

l

A partir dos dgitos menos significativos, ordene as

chaves.
3
4
6
8
4
7
3

2
5
5
3
3
2
5

9
7
7
9
6
0
5

7
3
4
4
6
3
8

2
5
3
5
5
2
3

0
5
6
7
7
9
9
161

Radix Sort - Funcionamento

l

A partir dos dgitos menos significativos, ordene as

chaves.
3
4
6
8
4
7
3

2
5
5
3
3
2
5

9
7
7
9
6
0
5

7
3
4
4
6
3
8

2
5
3
5
5
2
3

0
5
6
7
7
9
9
162

Radix Sort - Funcionamento

l

A partir dos dgitos menos significativos, ordene as

chaves.
3
4
6
8
4
7
3

2
5
5
3
3
2
5

9
7
7
9
6
0
5

7
3
4
4
6
3
8

2
5
3
5
5
2
3

0
5
6
7
7
9
9

7
3
4
8
3
4
6

2
2
3
3
5
5
5

0
9
6
9
5
7
7
163

Radix Sort - Funcionamento

l

A partir dos dgitos menos significativos, ordene as

chaves.
3
4
6
8
4
7
3

2
5
5
3
3
2
5

9
7
7
9
6
0
5

7
3
4
4
6
3
8

2
5
3
5
5
2
3

0
5
6
7
7
9
9

7
3
4
8
3
4
6

2
2
3
3
5
5
5

0
9
6
9
5
7
7
164

Radix Sort - Funcionamento

l

A partir dos dgitos menos significativos, ordene as

chaves.
3
4
6
8
4
7
3

2
5
5
3
3
2
5

9
7
7
9
6
0
5

7
3
4
4
6
3
8

2
5
3
5
5
2
3

0
5
6
7
7
9
9

7
3
4
8
3
4
6

2
2
3
3
5
5
5

0
9
6
9
5
7
7

3
3
4
4
6
7
8

2
5
3
5
5
2
3

9
5
6
7
7
0
9
165

Radix Sort Pseudo Cdigo

l

Como dito anteriormente, o Radix Sort consiste em

usar um outro mtodo de ordenao (estvel) para
ordenar as chaves em relao a cada dgito;
O cdigo, portanto, muito simples:
RadixSort(A[], d)!
{!
for(i=0; i<d; i++)!
BucketSort(A, d);!
}!

Em que d o dgito em relao ao qual as chaves

sero ordenadas.
166

Radix Sort - Complexidade

l

Considerando n chaves de d dgitos e valores at k,

temos:

Quando d constante e k = O(n), que o caso

quando usamos o Bucket Sort, temos:

167

Radix Sort Resumo

l
l
l

Tipo de Ordenao: Interna.

Complexidade: O(n).
Quantidade de dados: Muitos, porm, com chaves de
tamanhos limitados.
Especificidades: Pressupe caractersticas da entrada, e a
implementao depende de tais caractersticas.
Estabilidade: Usando o dgito menos significativo sim, usando o
mais significativo, no.
Especificidades: Apesar da complexidade melhor deste
mtodo, na prtica o Quicksort ainda melhor, por fazer
melhor uso de cache do computador, alm de melhores
constantes.
168
Adaptabilidade: No.

Merge Sort
(Ordenao por Intercalao)
l

Baseado no paradigma Dividir-e-Conquistar

l

l
l

Divide o problema original em problemas menores

semelhantes;
Resolve os problemas menores mais fceis ;
Combina os problemas menores para formar a
soluo para o problema original
l

mais fcil ordenar chaves parcialmente ordenadas.

um algoritmo recursivo.

169

Merge Sort
l

Baseado em dois procedimentos:

l

MERGE: Cria dois subvetores, cada um

correspondente a uma metade do vetor original,
depois intercala os menores valores, copiando-os de
volta ao vetor original;
MERGE_SORT: Divide o problema original em
subproblemas, e usa o procedimento anterior para
resolv-los.

170

Merge Sort - MERGE

l

Cria dois subvetores, cada um correspondente a

uma metade do vetor original, depois intercala os
menores valores, copiando-os de volta ao vetor
original.
A

p
l
l
l

p: Limite esquerdo do vetor;

r: Limite direito do vetor;
q: Meio do vetor
;

(
171

Merge Sort - MERGE

l

Cria dois subvetores, cada um correspondente a

uma metade do vetor original, depois intercala os
menores valores, copiando-os de volta ao vetor
original.
A

2
p

q Sentinela

q+1

172
r Sentinela

Merge Sort - MERGE

l

Cria dois subvetores, cada um correspondente a

uma metade do vetor original, depois intercala os
menores valores, copiando-os de volta ao vetor
original.
A

173

Merge Sort - MERGE

l

Cria dois subvetores, cada um correspondente a

uma metade do vetor original, depois intercala os
menores valores, copiando-os de volta ao vetor
original.
A

174

Merge Sort - MERGE

l

Cria dois subvetores, cada um correspondente a

uma metade do vetor original, depois intercala os
menores valores, copiando-os de volta ao vetor
original.
A

175

Merge Sort - MERGE

l

Cria dois subvetores, cada um correspondente a

uma metade do vetor original, depois intercala os
menores valores, copiando-os de volta ao vetor
original.
A

176

Merge Sort - MERGE

l

Cria dois subvetores, cada um correspondente a

uma metade do vetor original, depois intercala os
menores valores, copiando-os de volta ao vetor
original.
A

177

Merge Sort - MERGE

l

Cria dois subvetores, cada um correspondente a

uma metade do vetor original, depois intercala os
menores valores, copiando-os de volta ao vetor
original.
A

178

Merge Sort - MERGE

l

Cria dois subvetores, cada um correspondente a

uma metade do vetor original, depois intercala os
menores valores, copiando-os de volta ao vetor
original.
A

179

Merge Sort - MERGE

l

S um valor suficientemente grande, tal que,

sempre que comparado, ser maior que o elemento
original do vetor.

180

Merge Sort - MERGE

l

Para que funcione, o vetor original deve ter

subvetores ordenados;
Para isso, aplica-se recursivamente o algoritmo
l

Quando chegar ao ponto deste exemplo, os subvetores estaro

ordenados.

181

MERGE - Cdigo
MERGE(int A[], int p, int q, int r)!
{!
n1 = q-p+1;!
n2 = r-q;!
!
for(i=0; i<n1; i++)!
E[i] = A[p+i];!
for(i=0; i<n2; i++)!
!
D[i] = A[q+i+1];!
!
E[n1] = INT_MAX;!
D[n2] = INT_MAX;!
i = j = 0;!
!
for(k=p; k<=r; k++)!
if(E[i] <= D[j])
! {!
!
! A[k] = E[i]; i++;!
! }!
! else
! {!
!
A[k] = D[j]; j++;!
! }!
}!

//define o tamanho dos subvetores !

//esquerdo e direito!
!
//preenche o subvetor esquerdo!
!
//preenche o subvetor direito!
!
!
//sentinela esquerda!
//sentinela direita!
!
!
//Intercala as menores chaves!
!
!
//e copia para o vetor original!

Exerccio: Alocao dos vetores E e D

dinamicamente, e posterior liberao da memria.
182

MERGE - Complexidade
MERGE(int A[], int p, int q, int r)!
{!
n1 = q-p+1;!
n2 = r-q;!
!
for(i=0; i<n1; i++)!
E[i] = A[p+i];!
for(i=0; i<n2; i++)!
!
D[i] = A[q+i+1];!
!
E[n1] = INT_MAX;!
D[n2] = INT_MAX;!
i = j = 0;!
!
for(k=p; k<=r; k++)!
if(E[i] <= D[j])
! {!
!
! A[k] = E[i]; i++;!
! }!
! else
! {!
!
A[k] = D[j]; j++;!
! }!
}!

!
Custo
!
!
c1 !
!
c2 !
!
!
!
!
!
!
c3 !
!

Repeties
!

!(n/2)+1!

!(n/2)+1!

!n!

!
!

Tempo = (n)

183

Merge Sort MERGE_SORT

l

Divide o vetor ao meio recursivamente at que no

seja mais possvel
l

Subvetor com apenas uma chave.

Na volta das chamadas recursivas, combina e

ordena os ltimos 2 subvetores
l

Na primeira vez, dois subvetores de apenas uma

chave.
Os subvetores vo aumentando de tamanho, at
formar o vetor original.

184

MERGE_SORT

185

MERGE_SORT

186

MERGE_SORT
5

187

MERGE_SORT
5

Intercala
188

MERGE_SORT
52

25

189

MERGE_SORT
52

25

Intercala
190

MERGE_SORT
52

25

191

MERGE_SORT
52

25

Intercala

192

MERGE_SORT
52

25

193

MERGE_SORT
52

25

194

MERGE_SORT
52

25

Intercala
195

MERGE_SORT
52

25

Intercala
196

MERGE_SORT
52

25

Intercala

197

MERGE_SORT
Intercala

52

25

198

MERGE_SORT
52

25

199

MERGE_SORT - Cdigo
!

MERGE_SORT(int A[], int p, int r)!

{!
int q;!
!
if(p < r)!
{!
q = (p+r)/2;!
!
MERGE_SORT(A, p, q);!
!
MERGE_SORT(A, q+1, r);!
!
MERGE(A, p, q, r);!
}!
}!
!
!

//dividir!
//conquistar!
!
//combinar!

!
l

Primeira chamada: MERGE_SORT(A, 0, n-1);!

200

Merge Sort - Complexidade

l

A anlise da complexidade do Merge Sort

baseada nos trs passos do paradigma:
l
l

(1)
se

T (n) =
/ 2) + D(n) + C (n) nos out
2T (nrecursivo,
Em se tratando de um algoritmo
a
complexidade definida por uma recorrncia:
l

Dividir D(n);
Conquistar;
Combinar C(n).

201

Merge Sort - Complexidade

l

Claramente, dividir o problema leva tempo

constante, logo:

Para resolver dois subproblemas, que consistem na

metade do problema original, temos:

Para combinar os subproblemas, usamos o

procedimento MERGE, que conforme vimos, possui
complexidade:
202

Merge Sort - Complexidade

l

Voltando recorrncia, temos ento:

De acordo com o Teorema Mestre, caso 2 temos

que:

T ( n) =

T ( n) =

203

Merge Sort Resumo

l
l
l
l

l
l

Tipo de Ordenao: Interna/Externa.

Complexidade: (nlogn).
Quantidade de dados: Muitos.
Especificidades: Alto consumo de memria, devido s
vrias chamadas recursivas.
Estabilidade: Sim.
Adaptabilidade:No.

204