Classificação e Pesquisa

Prévia do material em texto

Algoritmos de 
Ordenação e Pesquisa 
Marco Antonio Moreira de Carvalho 
Algoritmos e Estrutura de Dados 
2 
Bibliografia Básica 
l  Cormen, Leiserson, Rivest. Introduction 
to Algorithms. 2nd edition. MIT Press, 
2001. Capítulos 2, 6, 7, 8. 
l  Aho, Alfred V., Hopcroft, John F., 
Ullman, Jeffrey D., Data Structure and 
Algorithms, Massachusetts: Addison-
Wesley, 1987. Capítulo 8. 
3 
Ordenação e Pesquisa 
l  Considerando um conjunto de dados: 
l  Organizá-los de acordo com algum critério (>, <, ≥, ≤, 
etc.); ou 
l  Encontrar algum que atenda um critério específico 
(maior, menor, =, etc.). 
l  Estas tarefas devem ser realizadas eficientemente 
l  O tempo para executá-las depende da quantidade de 
dados envolvidos. 
l  Aplicação direta: Organização e manipulação de 
dados. 
4 
Ordenação e Pesquisa 
l  Os elementos são chamados de chaves; 
l  Pode haver chaves de valores idênticos; 
l  Os valores não necessariamente são sequenciais. 
l  Chaves podem ser números, strings, registros, etc. 
5 
Estrutura de Dados 
l  Vetores 
l  Mantêm uma série de elementos sequenciais 
mantidos em uma ordem linear como um único, 
porém, com possibilidade de acesso individual; 
l  Cada elemento possui um índice que indica sua 
posição no vetor e permite acessá-lo diretamente; 
l  Vetores tem tamanhos fixos. 
0 1 2 3 4 5 
4 8 15 16 23 42 
Índice 
Valor 
6 
Pesquisa 
l  Dado um conjunto de n chaves {k1, k2, …, kn}: 
l  Determinar a existência e/ou determinar a posição de 
determinada chave ki; 
l  Determinar a maior, a menor, etc. 
l  Dada a sequência de chaves abaixo, como 
determinar a existência da chave 8? Não sabemos 
se as chaves estão ordenadas… 
? ? ? ? ? ? 
7 
Métodos de Pesquisa 
l  Pesquisa Sequencial 
l  Pesquisa Binária 
8 
Pesquisa Sequencial 
l  Método intuitivo: 
l  Dada uma chave k, compará-la a cada chave no 
vetor, caso haja uma igual, a chave está no vetor 
l  Caso todas as chaves tenham sido comparadas e não 
houve nenhuma igual, a chave não existe no vetor. 
42 16 4 15 8 23 
k = 8 
Chave encontrada! 
9 
Pesquisa Sequencial 
Código 
int Sequencial(int A[], int n, int k, int *posicao)!
{!
 int i;!
 int achou = 0;!
!
 for(i=0; i<n; i++)!
 if(A[i] == k)!
 {!
 *posicao = i;!
 achou = 1;!
 }!
! return achou;!
}!
!
!
!
!
//sinaliza se a chave foi encontrada!
!
//para cada chave!
//compara com a chave de busca!
!
//se encontrou!
//armazena a posição!
!
//indica se encontrou ou não!
10 
Pesquisa Sequencial 
Complexidade 
int Sequencial(int A[], int n, int k, int *posicao)!
{!
 int i;!
 int achou = 0;!
!
 for(i=0; i<n; i++)!
 if(A[i] == k)!
 {!
 *posicao = i;!
 achou = 1;!
 }!
 return achou;!
}!
Custo Repetições 
!
!
c1 ! !n!
c2 !!n-1!
Tempo = Θ(n) 
 
11 
Pesquisa Sequencial 
l  Exercício 
l  Como torná-la mais rápida? 
l  2 versões. 
l  Qual é a complexidade desta pesquisa sequencial 
aprimorada? 
l  Se o elemento procurado for o primeiro? 
l  Se o elemento procurado for o último? 
l  E na média? 
12 
Pesquisa Binária 
l  Assume que as chaves estão ordenadas 
l  A partir disto, é possível diminuir o espaço de busca, 
restringindo-o por faixas de valores. 
l  Divide-se o problema ao meio seguidas vezes, até 
que a chave desejada seja encontrada ou determine-
se sua inexistência. 
13 
Pesquisa Binária 
l  Determina a chave central do vetor; 
l  Caso a chave pesquisada não seja a central, compare 
seus valores 
l  Se a chave pesquisada for menor, volte ao primeiro passo, 
porém, considere o vetor do início até o ponto da chave central; 
l  Se a chave pesquisada for maior, volte ao primeiro passo, 
porém, considere o vetor do ponto da chave central até o final. 
4 8 15 16 23 42 49 51 62 70 
k = 8 
14 
Pesquisa Binária 
l  Determina a chave central do vetor; 
l  Caso a chave pesquisada não seja a central, compare 
seus valores 
l  Se a chave pesquisada for menor, volte ao primeiro passo, 
porém, considere o vetor do início até o ponto da chave central; 
l  Se a chave pesquisada for maior, volte ao primeiro passo, 
porém, considere o vetor do ponto da chave central até o final. 
4 8 15 16 23 42 49 51 62 70 
k = 8 
15 
Pesquisa Binária 
l  Determina a chave central do vetor; 
l  Caso a chave pesquisada não seja a central, compare 
seus valores 
l  Se a chave pesquisada for menor, volte ao primeiro passo, 
porém, considere o vetor do início até o ponto da chave central; 
l  Se a chave pesquisada for maior, volte ao primeiro passo, 
porém, considere o vetor do ponto da chave central até o final. 
4 8 15 16 23 42 49 51 62 70 
k = 8 
16 
Pesquisa Binária 
l  Determina a chave central do vetor; 
l  Caso a chave pesquisada não seja a central, compare 
seus valores 
l  Se a chave pesquisada for menor, volte ao primeiro passo, 
porém, considere o vetor do início até o ponto da chave central; 
l  Se a chave pesquisada for maior, volte ao primeiro passo, 
porém, considere o vetor do ponto da chave central até o final. 
4 8 15 16 23 42 49 51 62 70 
k = 8 
Chave encontrada! 
17 
Pesquisa Binária - Código 
int PesquisaBinaria( int A[], int k, int n)!
{!
 int esquerda = 0; !
 int direita = n-1; !
 int meio;!
!
 while (esquerda <= direita) !
 {!
 meio = (esquerda+direita)/2;!
 !
! ! if (k == A[meio])!
 return meio;!
 else if (k < A[meio])!
 direita = meio-1;!
 else!
 esquerda = meio+1;!
 }!
 return -1; !
}!
!
!
!
//determina onde começa a busca!
//determina onde termina a busca!
//determina a chave central!
!
//enquanto houver mais que !
//uma chave no intervalo!
//calcula a chave central!
!
//testa se a central é a procurada!
!
//compara se é menor!
!
//caso contrário é maior!
!
!
//retorna -1 se não encontrou!
18 
Pesquisa Binária - 
Complexidade 
l  Melhor Caso 
l  A chave pesquisada é a primeira chave central: Θ(1); 
l  Pior Caso 
l  A chave procurada não existe no vetor, todas as 
divisões terão de ser feitas. 
⎩
⎨
⎧
Θ+
=Θ
=
.)1()2/(
,1)1(
)(
casosoutrosnosnT
nse
nT
19 
Teorema Mestre Resumido 
l  Alguns algoritmos têm sua complexidades 
determinadas através de recorrências da forma 
)()(.3
)log()(.2
1),()(.1 log
kk
kk
ak
nnTentãobaSe
nnnTentãobaSe
bparannTentãobaSe b
Θ∈<
Θ∈=
>Θ∈>
knbnaTnT += )/()(
l  O Teorema Mestre estabelece três casos que 
podem ser simplificados: 
20 
Pesquisa Binária - 
Complexidade 
l  Pelo segundo caso do Teorema Mestre, temos que 
no pior caso a complexidade da Pesquisa Binária é 
)(log)(
)1()2/()(
nOnT
nTnT
=
Θ+=
21 
Ordenação 
l  Dado um conjunto de n chaves {k1, k2, …, kn}, 
organizá-las tal que k’1 ≤ k’2 ≤ … ≤ k’n. 
l  Por exemplo, dado (5, 3, 1, 2, 4), n = 5, temos 1 ≤ 2 
≤ 3 ≤ 4 ≤ 5. 
l  Como ordenar a sequência de chaves abaixo? 
15 23 4 42 8 16 
4 8 15 16 23 42 
22 
Ordenação - Tipos 
l  Ordenação Interna 
l  Todas as chaves na memória principal – facilidade de 
acesso. 
l  Ordenação externa 
l  Chaves na memória principal e em memória externa – 
movimentação de chaves entre as duas. 
l  Diferentes métodos para cada tipo. 
23 
Ordenação - Propriedades 
l  Estabilidade 
l  Manutenção da ordem relativa entre chaves de 
mesmo valor; 
l  Especialmente importante para casos em que cada 
elemento possui mais de uma chave. 
l  Adaptabilidade 
l  Métodos adaptáveistêm o tempo de execução 
reduzido caso a entrada já esteja ordenada. 
24 
O que é importante saber 
sobre cada método 
l  Funcionamento; 
l  Tipo de ordenação efetuada; 
l  Complexidade 
l  Comportamento de acordo com o caso, em termos da 
quantidade de chaves. 
l  Estabilidade; 
l  Adaptabilidade; 
l  Especificidades; 
25 
Métodos de Ordenação 
l  Bubble Sort (Método Bolha) 
l  Insertion Sort (Método de Inserção) 
l  Selection Sort (Método de Seleção) 
l  Quicksort 
l  Heapsort 
l  Bucket Sort (Bin Sort) 
l  Radix Sort 
l  Merge Sort (Ordenação por Intercalação) 
26 
Bubble Sort 
(Método Bolha) 
l  O método mais simples: 
l  Suponha chaves em um vetor vertical A. Valores 
baixos são “leves” e valores altos são “pesados”. 
Como bolhas, os valores “leves” sobem no vetor um 
por vez, ao passo que os “pesados” descem. 
l  Operação Troca(A[i], A[j]): os elementos das 
posições i e j trocam de posição. 
27 
Bubble Sort - Funcionamento 
l  O vetor é analisado 
comparando-se pares de 
chaves; 
l  A mais “leve” sobe, a 
mais “pesada” desce; 
l  Caso já estejam na 
posição correta, o 
próximo par é analisado. 
1 ? 
2 ? 
3 3 
4 1 
Comparação: 1 e 3 
Posição Chave 
Troca(A[4], A[3]) 
28 
Bubble Sort – Procedimento 
de Troca 
Troca(int *i, int *j) 
{ 
 int temp; 
 temp = *i; 
 *i = *j; 
 *j = temp; 
} 
1 ? 
2 2 
3 1 
4 3 
Comparação: 1 e 2 
Posição Chave 
Troca(A[3], A[2]) 
29 
Bubble Sort - Funcionamento 
l  O vetor é analisado 
comparando-se pares de 
chaves; 
l  A mais “leve” sobe, a 
mais “pesada” desce; 
l  Caso já estejam na 
posição correta, o 
próximo par é analisado. 
1 4 
2 1 
3 2 
4 3 
Comparação: 1 e 4 
Posição Chave 
Troca(A[2], A[1]) 
30 
Bubble Sort - Funcionamento 
l  O vetor é analisado 
comparando-se pares de 
chaves; 
l  A mais “leve” sobe, a 
mais “pesada” desce; 
l  Caso já estejam na 
posição correta, o 
próximo par é analisado. 
1 1 
2 4 
3 2 
4 3 
A chave mais “leve” chegou ao topo. 
Posição Chave 
Não será utilizada em futuras comparações. 
31 
Bubble Sort - Funcionamento 
l  O vetor é analisado 
comparando-se pares de 
chaves; 
l  A mais “leve” sobe, a 
mais “pesada” desce; 
l  Caso já estejam na 
posição correta, o 
próximo par é analisado. 
1 1 
2 4 
3 2 
4 3 
Comparação: 3 e 2 
Posição Chave 
Não há troca. 
32 
Bubble Sort - Funcionamento 
l  O vetor é analisado 
comparando-se pares de 
chaves; 
l  A mais “leve” sobe, a 
mais “pesada” desce; 
l  Caso já estejam na 
posição correta, o 
próximo par é analisado. 
1 1 
2 4 
3 2 
4 3 
Comparação: 2 e 4 
Posição Chave 
Troca(A[3], A[2]) 
33 
Bubble Sort - Funcionamento 
l  O vetor é analisado 
comparando-se pares de 
chaves; 
l  A mais “leve” sobe, a 
mais “pesada” desce; 
l  Caso já estejam na 
posição correta, o 
próximo par é analisado. 
1 1 
2 2 
3 4 
4 3 
A segunda mais leve chegou 
à sua posição. 
Posição Chave 
34 
Bubble Sort - Funcionamento 
l  O vetor é analisado 
comparando-se pares de 
chaves; 
l  A mais “leve” sobe, a 
mais “pesada” desce; 
l  Caso já estejam na 
posição correta, o 
próximo par é analisado. 
1 1 
2 2 
3 4 
4 3 
Comparação: 3 e 4 
Posição Chave 
Troca(A[4], A[3]) 
35 
Bubble Sort - Funcionamento 
l  O vetor é analisado 
comparando-se pares de 
chaves; 
l  A mais “leve” sobe, a 
mais “pesada” desce; 
l  Caso já estejam na 
posição correta, o 
próximo par é analisado. 
1 1 
2 2 
3 3 
4 4 
Posição Chave 
Chaves ordenadas. 
36 
Bubble Sort - Código 
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]);!
}!
// Para cada “bolha”, exceto a última!
// Percorre o vetor, exceto as chaves já !
// ordenadas!
// Compara os pares!
// Se for mais “leve”, troca as posições!
37 
Bubble Sort – Complexidade 
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]);!
 }!
Custo Repetições 
!
c1 ! !n!
!
c2 !!n-i!
c3 !!n-i!
!
c4 ! !n-i!
38 
Bubble Sort – Complexidade 
nccccnccc ⎟
⎠
⎞
⎜
⎝
⎛ +++
+⎟
⎠
⎞
⎜
⎝
⎛ ++
=
22
43212432
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛ −
+⎟⎟
⎠
⎞
⎜⎜
⎝
⎛ −
+⎟⎟
⎠
⎞
⎜⎜
⎝
⎛ −
+=
222
2
4
2
3
2
21
nncnncnncnc
∑ ∑∑
−
=
−
=
−
=
−+−+−+
1
1
1
1
43
1
1
21 )()()(
n
i
n
i
n
i
incincincnc
Tempo = O(n2) 
⎟
⎠
⎞
⎜
⎝
⎛ −+⎟
⎠
⎞
⎜
⎝
⎛ −+⎟
⎠
⎞
⎜
⎝
⎛ −+=
2
)1(
2
)1(
2
)1(
4321
nncnncnncnc
39 
Bubble Sort – Resumo 
l  Tipo de Ordenação: Interna. 
l  Complexidade: O(n2). 
l  Quantidade de dados: Poucos. 
l  Especificidades: Complexidade fixa e código 
compacto. 
l  Estabilidade: Sim. 
l  Adaptabilidade: Não. A implementação clássica 
realiza a mesma quantidade de operações mesmo 
se as chaves já estiverem ordenadas. 
40 
Insertion Sort 
(Método de Inserção) 
l  Analogia com a 
organização de cartas de 
baralho na mão; 
l  Cartas são recebidas e 
colocadas na mão 
aleatoriamente; 
l  Durante a organização, 
cada carta é colocada no 
seu lugar certo, uma por 
vez, deslocando as 
demais. 
 
Extraído de Cormen, Leiserson, Rivest, (2001). 
41 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
6 4 ? ? ? ? 
Chave 4 na posição errada. 
42 
Insertion Sort - Funcionamento 
6 ? ? ? ? 
Move-se as outras chaves para abrir o espaço. 
Valor da chave é armazenado. 4 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
43 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
4 6 ? ? ? ? 
Valor da chave armazenada é inserido na 
posição certa. 
44 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
4 6 7 ? ? ? 
Chaves nas posições corretas. 
45 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
4 6 7 5 ? ? 
Chaves 5 na posição errada 
46 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
4 6 7 ? ? 
Move-se as outras chaves para abrir o espaço. 
Valor da chave é armazenado. 5 
47 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
4 5 6 7 ? ? 
Valor da chave armazenada é inserido na 
posição certa. 
48 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocadana posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
4 5 6 7 1 ? 
Chave na posição errada. 
49 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
4 5 6 7 ? 
Move-se as outras chaves para abrir o espaço. 
Valor da chave é armazenado. 1 
50 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
1 4 5 6 7 ? 
Valor da chave armazenada é inserido na 
posição certa. 
51 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
1 4 5 6 7 2 
Chave na posição errada. 
52 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
1 4 5 6 7 
Move-se as outras chaves para abrir o espaço. 
Valor da chave é armazenado. 2 
53 
Insertion Sort - Funcionamento 
l  Compara-se os pares de chaves; 
l  Cada chave é colocada na posição correta 
l  Para isso, outras são movidas. 
l  Caso já esteja na posição certa, passa-se ao 
próximo par. 
1 2 4 5 6 7 
Valor da chave armazenada é inserido na 
posição certa. 
Chaves ordenadas. 
54 
Insertion Sort - Código 
int ChaveAtual;!
!
for(j=1; j<n; j++)!
{!
 ChaveAtual = A[j];!
 i = j-1;!
! !
 while(i>=0 && A[i] > ChaveAtual)!
 {!
 A[i+1] = A[i];!
 i--;!
 }!
!
 A[i+1] = ChaveAtual;!
}!
//Variável auxiliar para as comparações!
//Para cada uma das chaves, exceto a última!
//Chave comparada atualmente!
//Compara com as demais chaves!
//Abre o espaço entre as chaves maiores !
//Insere a chave na posição correta!
55 
Insertion Sort - Complexidade 
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;!
 }!
Custo Repetições 
 
c1 ! !n!
!
c2 !!n-1!
c3 !!n-1!
!
!
c4 ! !j!
!
c5 ! !j-1 !!
c6 ! !j-1 !!
!
!
c7 ! !n-1!
56 
Insertion Sort - Complexidade 
∑ ∑∑
−
=
−
=
−
=
−+−+−++−+−+
1
1
7
1
1
65
1
1
4321 )1()1()1()()1()1(
n
j
n
j
n
j
ncjcjcjcncncnc
)(
222222 74327
654
321
2654 ccccncccccccnccc +++−⎟
⎠
⎞
⎜
⎝
⎛
+++++++⎟
⎠
⎞
⎜
⎝
⎛
++=
Pior caso = O(n2) 
 
7765433221 2
)1(
2
)1(1
2
)1( cncnncnncnnccnccncnc −+⎟
⎠
⎞
⎜
⎝
⎛ −+⎟
⎠
⎞
⎜
⎝
⎛ −+⎟
⎠
⎞
⎜
⎝
⎛ −
+
+−+−+=
57 
Insertion Sort – Resumo 
l  Tipo de Ordenação: Interna. 
l  Complexidade: O(n2). 
l  Quantidade de dados: Poucos. 
l  Especificidades: A complexidade, apesar de alta, 
não é fixa. 
l  Estabilidade: Sim. 
l  Adaptabilidade: Sim. 
58 
Selection Sort 
(Método de Seleção) 
l  Princípio simples; 
l  A cada iteração procura a chave de menor valor ainda 
não ordenada; 
l  Depois de encontrada, ela é inserida na posição correta 
do vetor. 
 
59 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
? ? ? ? ? 
? Menor chave 
? Posição 
60 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
6 ? ? ? ? 
6 Menor chave 
1 Posição 
61 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
6 4 ? ? ? 
4 Menor chave 
2 Posição 
62 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
6 4 3 ? ? 
3 Menor chave 
3 Posição 
63 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
6 4 3 5 ? 
3 Menor chave 
3 Posição 
64 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
6 4 3 5 1 
1 Menor chave 
5 Posição 
65 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
6 4 3 5 
1 Menor chave 
5 Posição 
66 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
1 6 4 3 5 
3 Menor chave 
4 Posição 
Acelerando… 
67 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
1 6 4 5 
3 Menor chave 
4 Posição 
68 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
1 3 6 4 5 
? Menor chave 
? Posição 
69 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
1 3 6 4 5 
4 Menor chave 
4 Posição 
Acelerando… 
70 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
1 3 6 5 
4 Menor chave 
4 Posição 
71 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
1 3 4 6 5 
? Menor chave 
? Posição 
72 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
1 3 4 6 5 
5 Menor chave 
5 Posição 
Acelerando… 
73 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
1 3 4 6 
5 Menor chave 
5 Posição 
74 
Selection Sort - Funcionamento 
l  A cada iteração procura a chave de menor valor 
ainda não ordenada; 
l  Depois de encontrada, ela é inserida na posição 
correta. 
1 3 4 5 6 
Chaves ordenadas. 
75 
Selection Sort - Código 
 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 não ordenadas!
!
//Procura a menor!
!
//atualiza as variáveis!
!
!
!
//Troca de lugar com a primeira!
//chave não ordenada!
76 
SelectionSort - Complexidade 
 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 ! ! !n!
!
c2 ! ! !n-1!
c3 ! ! !n-1!
!
c4 ! ! !n-i!
!
c5 ! ! !n-i !!
!
c6 ! ! !n-i !!
c7 ! ! !n-i!
!
!
!
c8 ! ! !n-1!
!
Custo Repetições 
77 
Selection Sort - Complexidade 
)1()()()()()1()1( 8
1
1
1
1
7
1
1
65
1
1
4321 −+−+−+−+−+−+−+ ∑ ∑∑∑
−
=
−
=
−
=
−
=
ncincincincincncncnc
n
i
n
i
n
i
n
i
88765433221 2
)1(
2
)1(
2
)1(
2
)1( cncnncnncnncnnccnccncnc −+⎟
⎠
⎞
⎜
⎝
⎛ −+⎟
⎠
⎞
⎜
⎝
⎛ −+⎟
⎠
⎞
⎜
⎝
⎛ −+⎟
⎠
⎞
⎜
⎝
⎛ −+−+−+
)(
22222222 8328
7654
321
27654 cccnccccccccncccc ++−⎟
⎠
⎞
⎜
⎝
⎛
++++++++⎟
⎠
⎞
⎜
⎝
⎛
+++
Tempo = O(n2) 
78 
Selection Sort – Resumo 
l  Tipo de Ordenação: Interna. 
l  Complexidade: O(n2). 
l  Quantidade de dados: Poucos. 
l  Especificidades: A complexidade é fixa. 
l  Estabilidade: Depende da implementação. A 
apresentada é estável. 
l  Adaptabilidade: Não. 
79 
Quicksort 
l  Provavelmente o mais eficiente para ordenação 
interna; 
l  Baseado no paradigma “Dividir-e-Conquistar”; 
l  Divide o problema original em problemas menores, 
semelhantes. 
l  Procedimento recursivo; 
l  Complexidade varia com o caso; 
l  Funcionamento não trivial como os anteriores. 
 
80 
Quicksort 
l  Três passos básicos: 
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; 
l  Conquistar: Ordene os subvetores recursivamente, 
dividindo-os também; 
l  Combinar: Uma vez que todos os subvetores estejam 
ordenados, o vetor original também estará. 
81 
Quicksort - Funcionamento 
l  Escolhe-se o pivô: primeira chave do vetor (existem outras 
estratégias); 
l  Percorre-se o vetor de esquerda a direita, comparando-se as 
chaves; 
l  Menores para a esquerda, maiores para a direita. 
3 1 ? ? ? ? ? ? ? ? 
Pivô 
Chave 1 permanecerá à esquerda. 
82 
Quicksort - Funcionamento 
l  Percorre-se o vetor de esquerda a direita, comparando-se as 
chaves; 
l  Menores para a esquerda, maiores para a direita. 
3 1 4 ? ? ? ? ? ? ? 
Pivô 
Chave 4 permanecerá à direita. 
Divisão 
83 
Quicksort - Funcionamento 
l  Percorre-se o vetor de esquerda a direita, comparando-se as 
chaves; 
l  Menores para a esquerda, maiores para a direita. 
3 1 4 1 ? ? ? ? ? ? 
Pivô 
Chave 1 permanecerá à esquerda. 
Divisão 
84 
Quicksort - Funcionamento 
l  Percorre-se o vetor de esquerda a direita, comparando-se as 
chaves; 
l  Menores para a esquerda, maiores para a direita. 
3 1 1 4 5 ? ? ? ? ? 
Pivô 
Chave 4 permanecerá à direita. 
Divisão 
85 
Quicksort - Funcionamento 
l  Percorre-se o vetor de esquerda a direita, comparando-se as 
chaves; 
l  Menores para a esquerda, maiores para a direita. 
3 1 1 4 5 9 ? ? ? ? 
Pivô 
Chave 9 permanecerá à direita. 
Divisão 
86 
Quicksort - Funcionamento 
l  Percorre-se o vetor de esquerda a direita, comparando-se as 
chaves; 
l  Menores para a esquerda, maiores para a direita. 
3 1 1 4 5 9 2 ? ? ? 
Pivô 
Chave 2 permanecerá à esquerda. 
Divisão 
87 
Quicksort - Funcionamento 
l  Percorre-se o vetor de esquerda a direita, comparando-se as 
chaves; 
l  Menores para a esquerda, maiores para a direita. 
3 1 1 2 5 9 4 6 ? ? 
Pivô 
Chave 6 permanecerá à direita. 
Divisão 
88 
Quicksort - Funcionamento 
l  Percorre-se o vetor de esquerda a direita, comparando-se as 
chaves; 
l  Menores para a esquerda, maiores para a direita. 
3 1 1 2 5 9 4 6 5 ? 
Pivô 
Chave 5 permanecerá à direita. 
Divisão 
89 
Quicksort - Funcionamento 
l  Percorre-se o vetor de esquerda a direita, comparando-se as 
chaves; 
l  Menores para a esquerda, maiores para a direita. 
3 1 1 2 5 9 4 6 5 3 
Pivô 
Chave 5 permanecerá à direita. 
Divisão 
90 
Quicksort - Funcionamento 
l  Inserir o pivô na posição correta. 
3 1 1 2 5 9 4 6 5 3 
Pivô Divisão 
91 
Quicksort - Funcionamento 
l  Inserir o pivô na posição correta; 
l  Agora o vetor deve ser dividido em duas partes: 
l  Do início a antes do pivô; 
l  De depois do pivô ao final. 
2 1 1 3 5 9 4 6 5 3 
92 
Quicksort - Funcionamento 
l  Cada metade do vetor é submetida ao mesmo processo 
individualmente, podendo ser dividida novamente; 
l  No fim, junta-se as partes ordenadas. 
2 1 1 
Pivô 
1 1 2 
93 
Quicksort - Funcionamento 
2 1 1 3 5 9 4 6 5 3 
2 1 1 5 9 4 6 5 3 
1 1 2 3 4 5 6 5 9 
1 1 3 4 6 5 9 
1 1 3 4 5 6 9 
3 1 4 1 5 9 2 6 5 3 
94 
int Particao(int A[], int esquerda, int direita) !
{!
 int i;!
 int j;!
 !
 i = esquerda;!
 for(j=esquerda+1; j<=direita; j++) !
 {!
 if (A[j] < A[esquerda]) !
! {!
 i++;!
 Troca(&A[i], &A[j]);!
 }!
 }!
!
 Troca(&A[esquerda], &A[i]);!
 !
 return i;!
}!
 !
Quicksort - Código 
!
!
!
!
//variável de controle!
//percorre o subvetor!
!
//se a chave analisada!
//for menor que o pivô!
!
//troca as chaves de !
//posição!
!
!
//insere o pivô na !
//posição correta!
95 
Quicksort - Código 
Quicksort(int A[], int esquerda, int direita) !
{!
 int p;!
 !
 if (direita > esquerda) !
 {!
 p = Dividir(A, esquerda, direita);!
 Quicksort(A, esquerda, p-1);!
 Quicksort(A, p+1, direita);!
 }!
}!
!
//pivô!
!
//se o subvetor não !
//for vazio !
//ele é ordenado!
//divide em parte esquerda!
//e parte direita!
96 
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;!
}!
 !
Quicksort - Complexidade 
!
!
!
c1 ! ! !n!
!
c2 ! ! !n-1!
!
c3 ! ! !n-1!
c4 ! ! !n-1!
Custo Repetições 
Tempo = Θ(n) 
97 
Quicksort - Complexidade 
l  Suponha que para ordenar n chaves, a 
complexidade é dada pela recorrência 
T(n) = T(i)+T(n-i-1) + Θ(n) 
l  Em que i representa o tamanho da partição obtida e 
T(0) = Θ(1). 
l  O pior caso do Quicksort ocorre quando as 
partições nunca são eficientes: o vetor é dividido em 
um parte com n-1 chaves e outra com 0 chaves, ou 
seja, não há partição efetiva em nenhuma das 
chamadas recursivas; 
l  Isto ocorre quando o vetor já está ordenado; 
 
98 
Quicksort - Complexidade 
l  No pior caso, para i=0, temos então: 
⎡ ⎤2/n
)()(
)()1()(
2nOnT
nnTnT
=
Θ+−=
l  No melhor caso, para i= ou -1 (partição 
perfeita), temos: 
)log()(
)(
2
2)(
)(1
22
)(
nnOnT
nnTnT
nnnTnTnT
=
Θ+⎟
⎠
⎞
⎜
⎝
⎛≤
Θ+⎟
⎠
⎞
⎜
⎝
⎛ −−+⎟
⎠
⎞
⎜
⎝
⎛≤
(Pelo Teorema Mestre, caso 2) 
⎣ ⎦2/n
99 
Quicksort - Complexidade 
l  Para o caso médio, suponhamos que todas as 
possíveis partições (0 e n-1, 1 e n-2, …, n-1 e 0) 
possuem a mesma probabilidade de acontecer, ou 
seja, 1/n para cada; 
l  Isto quer dizer que, na árvore de recursão, partições 
boa e ruins se alternarão aleatoriamente em cada 
nível; 
l  É razoável pensar que elas se alternam em cada 
nível deterministicamente no caso médio.100 
Quicksort - Complexidade 
n
0 n-1
Θ(n) n
(n-1)/2
Θ(n)
(n-1)/2
l  A pior partição l  A melhor partição 
101 
Quicksort - Complexidade 
l  Uma má partição seguida por uma boa partição 
n
n-1
Θ(n)
(n-1)/2[(n-1)/2]-1
0
l  Temos 3 subvetores, obtidos aos custos 
Θ(n)+Θ(n-1) = Θ(n) 
l  O custo das boas partições absorvem o das más. 
102 
Quicksort - Complexidade 
l  Logo, se a complexidade para boas partições é Θ
(nlogn), para o caso médio temos uma constante 
maior, resultando ainda em O(nlogn). 
l  Esta não é uma prova da complexidade, é uma 
intuição sobre a mesma, que pode ser confirmada 
matematicamente. 
103 
Quicksort – Resumo 
l  Tipo de Ordenação: Interna. 
l  Complexidade: O(n2) no pior caso e O(nlogn) no melhor caso 
e também no caso médio. 
l  Quantidade de dados: Muitos. 
l  Especificidades: Estratégias de seleção de pivô e partição 
podem influenciar o tempo de execução. Apesar de ser 
quadrático no pior caso, o caso médio justifica sua utilização. 
l  Estabilidade: Depende da partição. A versão apresentada é 
instável. Uma versão in place é estável. Infelizmente, 
métodos eficientes são instáveis. 
l  Adaptabilidade: Não. 
104 
Heapsort 
l  Utiliza uma estrutura de dados específica: o Heap 
l  Árvore binária completa em todos os níveis, exceto 
o último (possivelmente); 
l  Também pode ser visto como um vetor e possui as 
seguintes propriedades: 
l  A raiz da árvore é armazenada em A[1]; 
l  Para um dado nó i: 
l  O seu nó pai é ; 
l  Seu filho à esquerda é 2i; 
l  Seu filho à direita é 2i+1; 
⎣ ⎦2/i
105 
Heapsort - Heaps 
16
10
9 3
14
8 7
2 4 1
1
2 3
4 5 6 7
8 9 10
1423978101416 1423978101416
 1 2 3 4 5 6 7 8 9 10
Θ(lgn)
106 
Heaps 
l  Os heaps podem ser máximos ou mínimos; 
l  Raiz com o maior valor e pais com valor ≥ que os 
filhos – MaxHeap. 
l  Raiz com o menor valor e pais com valor ≤ que os 
filhos – MinHeap. 
l  No Heapsort, chaves são inseridas em um heap 
máximo; 
l  Ao serem retiradas do heap, as chaves estarão 
ordenadas; 
l  É necessário manter as propriedades do heap 
durante as inserções e exclusões. 
107 
Heapsort – Funcionamento 
l  Utiliza 3 operações sobre heaps: 
l  MAX-HEAPIFY: mantém a propriedade do heap 
máximo; 
l  BUILD-MAX-HEAP: produz um heap a partir de um 
vetor de entrada; 
l  HEAPSORT: ordena o vetor que representa o heap. 
108 
Heapsort – MAX-HEAPIFY 
l  Cada subárvore deve ser um heap máximo, 
portanto, um nó pai não pode ser maior que os nós 
filhos; 
l  Caso o nó pai seja menor que um dos filhos, ele 
trocará de posição com o maior deles; 
l  É aplicado recursivamente para garantir que uma 
mudança realizada não viola a propriedade em 
outras subárvores. 
109 
Heapsort – MAX-HEAPIFY 
16
10
9 3
4
14 7
2 8 1
1
2 3
4 5 6 7
8 9 10
110 
Heapsort – MAX-HEAPIFY 
16
10
9 3
14
4 7
2 8 1
1
2 3
4 5 6 7
8 9 10
111 
Heapsort – MAX-HEAPIFY 
16
10
9 3
14
8 7
2 4 1
1
2 3
4 5 6 7
8 9 10
112 
MAX-HEAPIFY - Código 
void MAX_HEAPIFY(int A[], int i, int n){!
 int esquerdo;!
 int direito;!
 int maior;!
!
 esquerdo = 2*i;!
 direito = 2*i+1;!
!
 if(esquerdo <= n && A[esquerdo] > A[i])!
! maior = esquerdo;!
 else!
! maior = i;!
!
 if (direito <= n && A[direito] > A
[maior])!
! maior = direito;!
!
 if(maior != i) {!
 Troca(&A[i], &A[maior]);!
! MAX_HEAPIFY(A, maior, n);!
 }!
}!
!
!
//determina o filho esquerdo!
//determina o filho direito!
!
!
!
!
//se o filho esquerdo for!
//maior que o pai, registra!
!
//senão!
//o maior é o pai mesmo!
//se o direito é maior que o maior!
!
//registra!
!
//se o maior não é o pai!
!
//troca as posições!
//verifica se a subárvore viola a !
//propriedade!
!
!
!
113 
MAX-HEAPIFY - Complexidade 
l  Θ(1) para fazer as trocas em um mesmo nível; 
l  Uma subárvore pode ter no máximo tamanho 2n/3; 
l  No pior caso então, a complexidade é dada pela 
recorrência 
)(log)(
)1(
3
2)(
nOnT
nTnT
==
Θ+⎟
⎠
⎞
⎜
⎝
⎛=
(Pelo teorema mestre, caso 2) 
114 
Heapsort – BUILD-MAX-HEAP 
l  Utiliza o procedimento anterior para transformar um 
vetor em um heap máximo; 
l  É aplicado de baixo para cima na árvore; 
l  Da metade do vetor em diante estão as folhas da 
árvore, então o procedimento é aplicado deste 
ponto para trás no vetor; 
l  A propriedade do heap é mantida pelo 
procedimento anterior. 
115 
Heapsort – BUILD-MAX-HEAP 
4
3
9 10
1
2 16
14 8 7
1
2 3
4 5 6 7
8 9 10
4 1 3 2 16 9 10 14 8 7 
116 
Heapsort – BUILD-MAX-HEAP 4
3
9 10
1
2 16
14 8 7
1
2 3
4 5 6 7
8 9 10
117 
Heapsort – BUILD-MAX-HEAP 4
3
9 10
1
14 16
2 8 7
1
2 3
4 5 6 7
8 9 10
118 
Heapsort – BUILD-MAX-HEAP 4
10
9 3
1
14 16
2 8 7
1
2 3
4 5 6 7
8 9 10
119 
Heapsort – BUILD-MAX-HEAP 4
10
9 3
16
14 7
2 8 1
1
2 3
4 5 6 7
8 9 10
120 
Heapsort – BUILD-MAX-HEAP 
16
10
9 3
14
8 7
2 4 1
1
2 3
4 5 6 7
8 9 10
121 
BUILD-MAX-HEAP - Código 
void BUILD_MAX_HEAP(int A[],int n)!
{!
 int i;!
!
 for(i=n/2; i>0; i--)!
 MAX_HEAPIFY(A, i, n);!
}!
 
 
!
//Para cada uma das subárvores,!
//verifica corrige a propriedade !
//do heap!
//folhas não são verificadas!
122 
BUILD-MAX-HEAP 
Complexidade 
l  Aparentemente, a complexidade é O(nlogn); 
l  Porém, analisando-se a quantidade máxima de nós 
por nível do heap, e a quantidade de níveis, é 
possível provar que a complexidade do 
procedimento pode ser limitada por O(n); 
l  Em outras palavras, construir um heap a partir de 
um vetor aleatório é possível em tempo linear. 
123 
Heapsort - Funcionamento 
l  Inicialmente constrói um heap (BUILD-MAX-HEAP); 
l  A maior chave estará na raiz do heap, então ela 
será a última chave na ordenação – ela é removida 
do heap; 
l  A nova raiz pode violar a propriedade do heap, 
portanto, aplica-se o procedimento MAX-HEAPIFY; 
l  Agora, a segunda maior chave está na raiz, ela será 
a penúltima na ordenação final; 
l  E assim por diante… 
l  A árvore diminui a cada remoção. 
124 
Heapsort - Funcionamento 
16
10
9 3
14
8 7
2 4 1
125 
Heapsort - Funcionamento 
14
10
9 3
8
4 7
2 1 16
i
Como esta chave veio 
parar aqui? 
126 
Heapsort - Funcionamento 
10
9
1 3
8
4 7
2 16
i
14
127 
Heapsort - Funcionamento 
9
3
1 2
8
4 7
10 16
i
14
128 
Heapsort - Funcionamento 
8
3
1 9
7
4 2
10 16
i
14
129 
Heapsort - Funcionamento 
7
3
8 9
4
1 2
10 16
i
14
130 
Heapsort - Funcionamento 
4
3
8 9
2
1 7
10 16
i
14
131 
Heapsort - Funcionamento 
3
1
8 9
2
4 7
10 16
i
14
132 
Heapsort - Funcionamento 
2
3
8 9
1
4 7
10 16
i
14
133 
Heapsort - Funcionamento 
1
3
8 9
2
4 7
10 16
i
14
1 2 3 4 7 8 9 10 14 16 
134 
Heapsort - Código 
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);!
 }!
}!
!
!
!
!
//constrói o heap inicial!
!
//para cada chave!
//coloca a raiz do heap na !
//posição correta da ordenação!
//verificae corrige a!
//propriedade do heap!
135 
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);!
 }!
}!
O(n) ! !1!
!
c1! ! !n!
!
!
c3! ! !n-1!
O(logn) ! !n-1!
!
!
!
!
!
Custo Repetições 
 
 
 
 
 
136 
Heapsort - Complexidade 
nn
nccnn
nnncncncn
nnncncn
log
)1(log)1(
loglog
)1(log)1(
31
331
31
=
+++−=
−+−++=
−+−++
Tempo = O(nlogn) 
137 
Heapsort – Resumo 
l  Tipo de Ordenação: Interna. 
l  Complexidade: O(nlogn) no pior caso. 
l  Quantidade de dados: Muitos. 
l  Especificidades: Melhor complexidade, porém, uma 
boa implementação do Quicksort é melhor na 
prática, devido a questões de hardware (cache). 
l  Estabilidade: Não. 
l  Adaptabilidade: Não. 
138 
Bucket Sort (Bin Sort) 
l  Pressupõe que a entrada consiste em números 
inteiros distribuídos uniformemente sobre um 
intervalo 
l  Ou seja, que há um limite nos valores das chaves. 
l  O intervalo é então dividido em n subintervalos de 
tamanhos iguais, os chamados buckets (baldes); 
l  Cada chave vai para o balde correspondente à sua 
faixa de valor 
l  Considerando a uniformidade da distribuição, não 
esperamos muitas chaves em um mesmo balde. 
139 
Bucket Sort – Funcionamento 
l  Cada balde é posteriormente ordenado, 
isoladamente dos demais; 
l  Considerando o limite [0,1), e chaves com dois 
dígitos decimais, determinamos o número de baldes 
como 10 (0, …9). 
l  A função para determinação do índice balde correto 
é ; 
⎣ ⎦][iAn×
140 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 / 
2 / 
3 / 
4 / 
5 / 
6 / 
7 / 
8 / 
9 / 
A
 
B 
141 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 / 
2 / 
3 / 
4 / 
5 / 
6 / 
7 
8 / 
9 / 
A
 
B 
0,78 / 
142 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 / 
3 / 
4 / 
5 / 
6 / 
7 
8 / 
9 / 
A
 
B 
0,78 / 
0,17 / 
143 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 / 
3 
4 / 
5 / 
6 / 
7 
8 / 
9 / 
A
 
B 
0,78 / 
0,17 / 
0,39 / 
144 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 
3 
4 / 
5 / 
6 / 
7 
8 / 
9 / 
A
 
B 
0,78 / 
0,17 / 
0,39 / 
0,26 / 
145 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 
3 
4 / 
5 / 
6 / 
7 
8 / 
9 / 
A
 
B 
0,72 
0,17 / 
0,39 / 
0,26 / 
0,78 / 
146 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 
3 
4 / 
5 / 
6 / 
7 
8 / 
9 
A
 
B 
0,72 
0,17 / 
0,39 / 
0,26 / 
0,78 / 
0,94 / 
147 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 
3 
4 / 
5 / 
6 / 
7 
8 / 
9 
A
 
B 
0,72 
0,17 / 
0,39 / 
0,21 
0,78 / 
0,94 / 
0,26 / 
148 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 
3 
4 / 
5 / 
6 / 
7 
8 / 
9 
A
 
B 
0,72 
0,12 
0,39 / 
0,21 
0,78 / 
0,94 / 
0,26 / 
0,17 / 
149 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 
3 
4 / 
5 / 
6 / 
7 
8 / 
9 
A
 
B 
0,72 
0,12 
0,39 / 
0,23 
0,78 / 
0,94 / 
0,26 / 
0,17 / 
0,21 
150 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 
3 
4 / 
5 / 
6 
7 
8 / 
9 
A
 
B 
0,72 
0,12 
0,39 / 
0,23 
0,78 / 
0,94 / 
0,26 / 
0,17 / 
0,21 
0,68 / 
151 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 
3 
4 / 
5 / 
6 
7 
8 / 
9 
A
 
B 
0,72 
0,12 
0,39 / 
0,23 
0,78 / 
0,94 / 
0,26 / 
0,17 / 
0,21 
0,68 / 
Balde desordenado. 
152 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,26 0,72 0,94 0,21 0,12 0,23 0,68 
0 / 
1 
2 
3 
4 / 
5 / 
6 
7 
8 / 
9 
A
 
B 
0,72 
0,12 
0,39 / 
0,21 
0,78 / 
0,94 / 
0,26 / 
0,17 / 
0,23 
0,68 / 
153 
Bucket Sort – Pseudo Código 
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);!
}!
154 
Bucket Sort – Complexidade 
void BucketSort(int A[], int n)!
{!
 int i;!
!
 for(i=0; i<n; i++)!
 InserirLista…!
!
 for(i=0; i<n-1; i++)!
! InsertionSortLista(&B[i]);!
!
 ConcatenarListasEncadeadas(n-1);!
}!
!
!
c1! ! !n!
O(1) ! !n-1!
!
c3! ! !n-1!
O(ni2) ! !n-1!
Custo Repetições 
155 
Bucket Sort - Complexidade 
l  O custo das sucessivas chamadas a ordenação por 
inserção pode ser calculado pela recorrência 
∑
−
=
+Θ=
1
0
2 )()()(
n
i
inOnnT
l  Em que ni denota a quantidade de chaves no balde i; 
l  Tomando as expectativas de ambos os lados e usando a 
linearidade de expectativa, temos: 
∑
∑
∑
−
−
−
+Θ=
+Θ=
⎥⎦
⎤
⎢⎣
⎡ +Θ=
1
0
2
1
0
2
1
0
2
])[()(
)]([)(
)()()]([
n
i
n
i
n
i
nEOn
nOEn
nOnEnTE
156 
Bucket Sort - Complexidade 
l  O valor esperado para é 2-1/n; 
l  Substituindo na última equação, temos 
][ 2inE
)()/12()( nnOnn Θ=−×+Θ
l  Desta maneira, o Bucket Sort é linear; 
l  Pode ser provado que, mesmo a entrada não sendo 
uma distribuição uniforme o Bucket Sort ainda 
executará em tempo linear. 
157 
Bucket Sort – Resumo 
l  Tipo de Ordenação: Interna. 
l  Complexidade: O(n). 
l  Quantidade de dados: Muitos, porém, com valores 
limitados. 
l  Especificidades: Pressupõe características da 
entrada, e a implementação depende de tais 
características. Um Bucket Sort com apenas dois 
buckets é na verdade o Quicksort (com pivoteamento 
ruim). 
l  Estabilidade: Depende do algoritmo de ordenação 
interna dos buckets. 
l  Adaptabilidade: Depende do algoritmo de ordenação 
interna dos buckets. 
158 
Radix Sort 
l  Utiliza o conceito do Bucket Sort; 
l  Pressupõe que as chaves de entrada possuem 
limite no valor e no tamanho (quantidade de 
dígitos); 
l  É essencial utilizar um segundo algoritmo estável 
para realizar a ordenação; 
l  Ordena números um digito de cada vez; 
l  A partir do menos significativo; 
l  Ou a partir do menos significativo. 
159 
Radix Sort 
l  Como os valores possuem limite, e a quantidade de 
dígitos é fixa, é possível aplicar o Bucket Sort para 
cada nível; 
l  Cria-se um balde para cada possível valor dos dígitos 
(0-9, ao invés de para cada faixa de valores), de 
modo a não ser necessário ordenar os baldes 
internamente. 
l  O Bucket Sort é linear neste caso, uma vez que não é 
necessário ordenar os baldes isoladamente. 
160 
Radix Sort - Funcionamento 
l  A partir dos dígitos menos significativos, ordene as 
chaves. 
3 2 9
4 5 7
6 5 7
8 3 9
4 3 6
7 2 0
3 5 5
161 
Radix Sort - Funcionamento 
l  A partir dos dígitos menos significativos, ordene as 
chaves. 
3 2 9
4 5 7
6 5 7
8 3 9
4 3 6
7 2 0
3 5 5
7 2 0
3 5 5
4 3 6
4 5 7
6 5 7
3 2 9
8 3 9162 
Radix Sort - Funcionamento 
l  A partir dos dígitos menos significativos, ordene as 
chaves. 
3 2 9
4 5 7
6 5 7
8 3 9
4 3 6
7 2 0
3 5 5
7 2 0
3 5 5
4 3 6
4 5 7
6 5 7
3 2 9
8 3 9
163 
Radix Sort - Funcionamento 
l  A partir dos dígitos menos significativos, ordene as 
chaves. 
3 2 9
4 5 7
6 5 7
8 3 9
4 3 6
7 2 0
3 5 5
7 2 0
3 5 5
4 3 6
4 5 7
6 5 7
3 2 9
8 3 9
7 2 0
3 2 9
4 3 6
8 3 9
3 5 5
4 5 7
6 5 7
164 
Radix Sort - Funcionamento 
l  A partir dos dígitos menos significativos, ordene as 
chaves. 
3 2 9
4 5 7
6 5 7
8 3 9
4 3 6
7 2 0
3 5 5
7 2 0
3 5 5
4 3 6
4 5 7
6 5 7
3 2 9
8 3 9
7 2 0
3 2 9
4 3 6
8 3 9
3 5 5
4 5 7
6 5 7
165 
Radix Sort - Funcionamento 
l  A partir dos dígitos menos significativos, ordene as 
chaves. 
3 2 9
4 5 7
6 5 7
8 3 9
4 3 6
7 2 0
3 5 5
7 2 0
3 5 5
4 3 6
4 5 7
6 5 7
3 2 9
8 3 9
7 2 0
3 2 9
4 3 6
8 3 9
3 5 5
4 5 7
6 5 7
3 2 9
3 5 5
4 3 6
4 5 7
6 5 7
7 2 0
8 3 9
166 
Radix Sort – Pseudo Código 
l  Como dito anteriormente, o Radix Sort consiste em 
usar um outro método de ordenação (estável) para 
ordenar as chaves em relação a cada dígito; 
l  O código, portanto, é muito simples: 
 
RadixSort(A[], d)!
{!
 for(i=0; i<d; i++)!
 BucketSort(A, d);!
}!
l  Em que d é o dígito em relação ao qual as chaves 
serão ordenadas. 
167 
Radix Sort - Complexidade 
l  Considerando n chaves de d dígitos e valores até k, 
temos: 
))(( knd +Θ
l  Quando d é constante e k = O(n), que é o caso 
quando usamos o Bucket Sort, temos: 
)(nΘ
168 
Radix Sort – Resumo 
l  Tipo de Ordenação: Interna. 
l  Complexidade: O(n). 
l  Quantidade de dados: Muitos, porém, com chaves de 
tamanhos limitados. 
l  Especificidades: Pressupõe características da entrada, e a 
implementação depende de tais características. 
l  Estabilidade: Usando o dígito menos significativo sim, usando o 
mais significativo, não. 
l  Especificidades: Apesar da complexidade melhor deste 
método, na prática o Quicksort ainda é melhor, por fazer 
melhor uso de cache do computador, além de melhores 
constantes. 
l  Adaptabilidade: Não. 
169 
Merge Sort 
(Ordenação por Intercalação) 
l  Baseado no paradigma Dividir-e-Conquistar 
l  Divide o problema original em problemas menores 
semelhantes; 
l  Resolve os problemas menores – mais “fáceis”; 
l  Combina os problemas menores para formar a 
solução para o problema original 
l  É mais fácil ordenar chaves parcialmente ordenadas. 
l  É um algoritmo recursivo. 
170 
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; 
l  MERGE_SORT: Divide o problema original em 
subproblemas, e usa o procedimento anterior para 
resolvê-los. 
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. 
2 4 5 7 1 2 3 6 
p q r 
l  p: Limite esquerdo do vetor; 
l  r: Limite direito do vetor; 
l  q: Meio do vetor ; 
A 
⎣ ⎦2/)( rp +
172 
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. 
2 4 5 7 1 2 3 6 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
p q r q+1 Sentinela Sentinela 
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. 
? ? ? ? ? ? ? ? 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
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. 
1 ? ? ? ? ? ? ? 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
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. 
1 2 ? ? ? ? ? ? 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
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. 
1 2 2 ? ? ? ? ? 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
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. 
1 2 2 3 ? ? ? ? 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
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. 
1 2 2 3 4 ? ? ? 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
179 
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. 
1 2 2 3 4 5 ? ? 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
180 
Merge Sort - MERGE 
l  S é um valor suficientemente grande, tal que, 
sempre que comparado, será maior que o elemento 
original do vetor. 
1 2 2 3 4 5 6 ? 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
181 
Merge Sort - MERGE 
l  Para que funcione, o vetor original deve ter 
subvetores ordenados; 
l  Para isso, aplica-se recursivamente o algoritmo 
l  Quando chegar ao ponto deste exemplo, os subvetores estarão 
ordenados. 
1 2 2 3 4 5 6 7 
2 4 5 7 S 1 2 3 6 S 
A 
E D 
182 
MERGE - Código 
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!
Exercício: Alocação dos vetores E e D 
dinamicamente, e posterior liberação da memória. 
183 
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++;!
! }!
}!
!
!
!
c1 ! ! !(n/2)+1!
!
c2 ! ! !(n/2)+1!
!
!
!
!
!
!
c3 ! ! !n!
!
!
!
Custo Repetições 
Tempo = Θ(n) 
184 
Merge Sort – MERGE_SORT 
l  Divide o vetor ao meio recursivamente até que não 
seja mais possível 
l  Subvetor com apenas uma chave. 
l  Na volta das chamadas recursivas, combina e 
ordena os últimos 2 subvetores 
l  Na primeira vez, dois subvetores de apenas uma 
chave. 
l  Os subvetores vão aumentando de tamanho, até 
formar o vetor original. 
185 
MERGE_SORT 
5 2 4 7 1 3 2 6 
186 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
187 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
188 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 75 2 4 7
5 2
Intercala 
189 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
190 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
Intercala 
191 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
192 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
Intercala 
193 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
2 4 5 7
194 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
2 4 5 7
1 3 2 6 
195 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
2 4 5 7
1 3 2 6 
1 3
Intercala 
196 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
2 4 5 7
1 3 2 6 
1 3 2 6
Intercala 
197 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
2 4 5 7
1 3 2 6 
1 3 2 6
Intercala 
198 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
2 4 5 7
1 3 2 6 
1 3 2 6
1 2 3 6 
Intercala 
199 
MERGE_SORT 
5 2 4 7 1 3 2 6 
1 3 2 6 5 2 4 7
5 2 4 7
5 2
2 5
74
2 4 5 7
1 3 2 6 
1 3 2 6
1 2 3 6 
1 2 2 3 4 5 6 7 
200 
MERGE_SORT - Código 
!
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);!
 }!
}!
!
!
!
l  Primeira chamada: MERGE_SORT(A, 0, n-1);!
//dividir!
//conquistar!
!
//combinar!
201 
Merge Sort - Complexidade 
l  A análise da complexidade do Merge Sort é 
baseada nos três passos do paradigma: 
l  Dividir – D(n); 
l  Conquistar; 
l  Combinar – C(n). 
l  Em se tratando de um algoritmo recursivo, a 
complexidade é definida por uma recorrência: 
⎩
⎨
⎧
++
=Θ
=
.)()()2/(2
,1)1(
)(
casosoutrosnosnCnDnT
nse
nT
202 
Merge Sort - Complexidade 
l  Claramente, dividir o problema leva tempo 
constante, logo: 
)2/(2 nT
l  Para resolver dois subproblemas, que consistem na 
metade do problema original, temos: 
l  Para combinar os subproblemas, usamos o 
procedimento MERGE, que conforme vimos, possui 
complexidade: 
)()( nOnC =
)1()( Θ=nD
203 
Merge Sort - Complexidade 
l  Voltando à recorrência, temos então: 
⎩
⎨
⎧
Θ+
=Θ
=
.)()2/(2
,1)1(
)(
casosoutrosnosnnT
nse
nT
l  De acordo com o Teorema Mestre, caso 2 temos 
que: 
)log()(
)()2/(2)(
nnnT
nnTnT
Θ=
Θ+=
204 
Merge Sort – Resumo 
l  Tipo de Ordenação: Interna/Externa. 
l  Complexidade: Θ(nlogn). 
l  Quantidade de dados: Muitos. 
l  Especificidades: Alto consumo de memória, devido às 
várias chamadas recursivas. 
l  Estabilidade: Sim. 
l  Adaptabilidade:Não.