Slides 2

Prévia do material em texto

Algoritmos de Ordenação
Universidade de São Paulo
Instituto de Ciências Matemáticas e de Computação
Departamento de Ciências de Computação
Rodrigo Fernandes de Mello
http://www.icmc.usp.br/~mello
mello@icmc.usp.br
   
Eficiência de Algoritmos
● Antes  de  abordarmos  os  algoritmo de  ordenacão  iremos  falar 
um pouco sobre a Eficiência de Algoritmos
● Isso nos ajudará a avaliar os algoritmos de ordenação
● Computadores apresentam recursos limitados
● Nosso  tempo  também  é  limitado  para  aguardar  por  uma 
solução
● Portanto:
● É importante estudar técnicas para medir o quão bom é um 
algoritmo para resolver dado problema
● Podemos encontrar um algoritmo melhor para resolver certo 
problema?
   
Eficiência de Algoritmos
● Aspectos essenciais envolvidos no estudo de Algoritmos:
● O Algoritmo projetado é capaz de resolver o problema?
– Resolver significa encontrar a solução ideal
● Qual a quantidade de recursos necessária para o algoritmo 
executar sobre certa entrada?
– Envolve requisitos de memória
– Envolve requisitos de processamento
   
Eficiência de Algoritmos
● Muitas pessoas acreditam que é mais  importante comprar um 
computador melhor que estudar o Algoritmo, no entanto:
● Suponha  dois  computadores  com  as  seguintes 
capacidades:
– Computador A   1000 MIPS→
– Computador B     200 MIPS→
   
Eficiência de Algoritmos
● Muitas pessoas acreditam que é mais  importante comprar um 
computador melhor que estudar o Algoritmo, no entanto:
● Suponha dois algoritmos feitos para ordenar uma sequencia 
de números inteiros:
– Algoritmo 1   realiza 2n→ 2 operacões
● Este  algoritmo  foi  escrito  por  um  especialista  na 
tentativa  de  aumentar  a  eficiência  de  um  algoritmo 
ordenação existente chamado INSERTION­SORT
– Algoritmo 2   realiza 50 n log n operacões→
● Um  iniciante  em  programação  teve  acesso  a  um 
algoritmo  de  ordenação  chamado  MERGE­SORT  e 
apenas o implementou
   
Eficiência de Algoritmos
● Muitas pessoas acreditam que é mais  importante comprar um 
computador melhor que estudar o Algoritmo, no entanto:
● Considere que o:
– Computador A irá executar o Algoritmo 1
– Computador B irá executar o Algoritmo 2
● Considerando a ordenação de uma sequencia com 1 bilhão 
de números inteiros
   
Eficiência de Algoritmos
● Muitas pessoas acreditam que é mais  importante comprar um 
computador melhor que estudar o Algoritmo, no entanto:
● Considere que o:
– Computador A irá executar o Algoritmo 1 em:
– Computador B irá executar o Algoritmo 2 em:
(50 * 1,000,000,000 * log
2
 1,000,000,000) / 200 = 7,47 * 109 segs
   
Eficiência de Algoritmos
● É importante ter acesso a um computador veloz
● No  entanto,  é  MAIS  IMPORTANTE  projetar  um  bom 
algoritmo para resolver SEU problema
● Logo,  iremos  estudar  a  eficiência  de  algoritmos 
considerando o volume de operações que eles executam
– Da mesma maneira poderíamos considerar a ocupação 
de memória
● Mas  como  calculamos  quantas  operações  um  algoritmo 
realiza?
   
Eficiência de Algoritmos
● Calculemos  quantas  operacões  duas  versões  de  algoritmos 
para calcular potências realizam:
● Primeiro algoritmo: Baseado em Produtos Sucessivos
● Segundo algoritmo: Bit shift
   
Eficiência de Algoritmos
● Primeiro algoritmo: Baseada em Produtos Sucessivos
int power(int base, int exponent) {
int i, value = base;
for (i = 1; i < exponent; i++) {
value *= base;
}
return value;
}
c1
n-1
c2
c3
   
Eficiência de Algoritmos
● Primeiro algoritmo: Baseada em Produtos Sucessivos
f(n) = c1 + (n-1)*c2 + c3
f(n) = c2*n + c1 – c2 + c3
Sendo:
a = c2
b = c1 – c2 + c3
Temos:
f(n) = a*n + b // Custo linear
   
Eficiência de Algoritmos
● Segundo algoritmo: Bit shift
int power(int exponent) {
return 2 << exponent;
}
c1
Portanto:
f(n) = c1 // Custo constante
   
Eficiência de Algoritmos
● Calculemos, agora, o número de operações envolvidas em dois 
algoritmos distintos que buscam por inteiros em vetores:
● Primeiro algoritmo: Busca Sequencial
● Segundo algoritmo: Busca Binária
   
Eficiência de Algoritmos
● Primeiro algoritmo: Busca Sequencial
● Para encontrar um inteiro, temos que:
● No pior caso: passar por todos os inteiros do vetor
● No melhor caso: seria o primeiro elemento do vetor
● No caso médio: percorreríamos metade do vetor
7 5 8 4 9 2 3 6 1
   
Eficiência de Algoritmos
● Segundo algoritmo: Busca Binária
● Agora considere que ordenamos o vetor:
● Obtendo:
● Lembre­se que desconhecemos os valores no vetor!
7 5 8 4 9 2 3 6 1
1 2 3 4 5 6 7 8 9
   
Eficiência de Algoritmos
● Vamos  calcular  o  pior  caso  em  termos  de  operações  por 
algoritmo
● Busca Sequencial   f(n) = n operações→
   
Eficiência de Algoritmos
● Busca Binária
Valor Central
Metade à 
Esquerda
Metade à 
Direita
   
Eficiência de Algoritmos
● Busca Binária
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
1 operação de 
comparação
1 operação
1 operação
1 operação
   
Eficiência de Algoritmos
● Busca Binária
● Qual a profundidade da árvore?
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Considere que a árvore 
tem n elementos
Sempre dividimos em dois 
ramos, cada um com 
metade dos elementos do 
nível anterior
Logo temos uma potência 
de dois
   
Eficiência de Algoritmos
● Busca Binária
● Qual a profundidade da árvore?
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Tendo uma potência de 2:
Qual o número de níveis 
que satisfaz:
2níveis = n
Sendo n o número de 
elementos na árvore
   
Eficiência de Algoritmos
● Busca Binária
● Qual a profundidade da árvore?
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Simplificando
2níveis = n
Temos:
log2 n
   
Eficiência de Algoritmos
● Busca Binária
Temos portanto log2 n níveis na árvore
Temos 1 operação por nível
Logo:
f(n) = 1 * log2 n
Ou simplesmente:
f(n) = log2 n
   
Eficiência de Algoritmos
● Agora  estudemos  com  calma  esses  algoritmos  em  função  do 
pior caso:
● Busca Sequencial   f(n) = n→
● Busca Binária   f(n) = log→
2
 n
● Vamos plotar o número de operações!
● Qual algoritmo é melhor? Qual deles utilizar?
● É importante avaliar o número de operações de um algoritmo?
   
Exercícios
● Exercícios:
● Sejam  dois  algoritmos  A  e  B.  Sabe­se  que  algoritmo  A  realiza  2n2 
operações e que o algoritmo B realiza 50 log n operações. Sabendo que 
n é um inteiro em que n >= 1, para quais valores de n:
– O algoritmo A gera menos operações que B?
– O algoritmo B gera menos operações que A?
● Qual o menor valor de n tal que um algoritmo cujo número de operações 
é  100*n2  executa  mais  rápido  que  outro  algoritmo  cujo  número  de 
operações é 2*n sobre o mesmo computador?
   
Exercícios
● Exercícios:
● Para cada função f(n) e  tempo  t na  tabela a seguir, determine o maior 
inteiro n que pode ser  resolvido em  tempo  t,  sabendo que o algoritmo 
leva f(n) microsegundos para executar
   
Algoritmos de Ordenacão
● A  partir  de  agora  iremos  estudar  os  seguintes  algoritmos  de 
ordenacão e analisar suas eficiências:
● Insertion Sort
● Merge Sort
● Heapsort
● Quicksort
● Counting Sort
● Radix Sort
● Bucket Sort
   
Algoritmos de Ordenacão
● O que são algoritmos de ordenacão?
● Por que é importante estudar algoritmos de ordenacão?
● Bancos de dados ordenam elementos para realizar buscas
● Sistemas  operacionais  ordenam processos  de  acordo  com 
suas prioridades para conceder CPU
● Search  Engines  ordenam  nossa  busca  de  acordo  com 
critérios de relevância
   
Algoritmos de Ordenacão
● Ordenar  um  vetor  v  com  elementos,  significa  obter  uma 
permutacão final tal que:
v1 ≤ v2 ≤ v3 ≤ … ≤ vn
● Os  elementos  que  desejamos  ordenar  são  denominados 
chaves
   
Insertion Sort
● Funcionamento do Insertion Sort
● Considere  parte  de  um  baralho  (com  apenas  um  naipe) 
sobre a mesa com as faces das cartas para baixo
●Uma pessoa é responsável por retirar cartas do baralho
● Por  enquanto  essa  pessoa  não  tem  nenhuma  carta  nas 
mãos
● A pessoa retira uma carta
– Ordena essa carta em funcão das cartas que  já  tem na 
mão
   
Insertion Sort
● Código
void insertion(int *vector, int n) {
int key, j, i;
for (j = 1; j < n; j++) {
key = vector[j];
i = j - 1;
while (i >= 0 && vector[i] > key) {
vector[i+1] = vector[i];
i--;
}
vector[i+1] = key;
}
}
   
Insertion Sort
● Funcionamento...
7 5 8 4 9 2 3 6 1vector
j
key = vector[j];
Temos na mão (paralelo com cartas na 
mão) apenas a chave 7
Cartas sobre a mesa
Cartas já 
ordenada
s na mão
i
   
Insertion Sort
● Funcionamento...
5 7 8 4 9 2 3 6 1vector
j
Cartas sobre a mesa
Cartas já 
ordenada
s na mão
i
   
Insertion Sort
● Analisando o Algoritmo Insertion Sort
● Assume­se que o vetor tem n elementos
for (j = 1; j < n; j++) {
key = vector[j];
i = j – 1;
while (i >= 0 && vector[i] > key) {
vector[i+1] = vector[i];
i--;
}
vector[i+1] = key;
}
Custo
c1
c2
c3
c4
c5
c6
c7
Laco mais 
externo 
ocorre n-1 
vezes
   
Insertion Sort
● Analisando o Algoritmo Insertion Sort
● Assume­se que o vetor tem n elementos
for (j = 1; j < n; j++) {
key = vector[j];
i = j – 1;
while (i >= 0 && vector[i] > key) {
vector[i+1] = vector[i];
i--;
}
vector[i+1] = key;
}
Custo
c1
c2
c3
c4
c5
c6
c7
Laco mais 
interno 
depende do 
vetor
   
Insertion Sort
● Analisando o Laco mais interno:
● Se vetor já ordenado, então:
– Ocorrerão apenas as comparacões:
i >= 0 && vector[i] > key
– Essas comparacões ocorrerão por n­1 vezes
● Se  vetor  ordenado  de  maneira  decrescente  (pior  caso) 
então:
– Para  primeira  operacão  do  laco  externo,  o  laco  interno 
executará uma vez
– Para segunda  operacão  do  laco  externo, o  laco  interno 
executará 2 vezes
– Para  a  operacão  k  do  laco  externo,  o  laco  interno 
executará k vezes    
Insertion Sort
● O laco mais externo ocorre por n vezes   uma vez a mais que →
suas operacões, pois há assim mesmo um teste final para sair 
do laco
for (j = 1; j < n; j++) {
key = vector[j];
i = j – 1;
while (i >= 0 && vector[i] > key) {
vector[i+1] = vector[i];
i--;
}
vector[i+1] = key;
}
Custo
c1
c2
c3
c4
c5
c6
c7
# Vezes
n
n-1
n-1
n-1
   
Insertion Sort
● Assumimos  que  o  laco  interno  ocorre  t  vezes  para  cada 
iteracão do laco externo, assim:
for (j = 1; j < n; j++) {
key = vector[j];
i = j – 1;
while (i >= 0 && vector[i] > key) {
vector[i+1] = vector[i];
i--;
}
vector[i+1] = key;
}
Custo
c1
c2
c3
c4
c5
c6
c7
# Vezes
n
n-1
n-1
n-1    
Insertion Sort
● Calculando o número de operacões, temos:
   
Insertion Sort
● No  melhor  caso,  o  vetor  já  está  ordenado  e,  portanto,  não 
executamos operacões do laco interno
● Executamos apenas o teste do laco interno
● Assim temos:
● Simplificando:
Número Linear 
de Operacões 
no melhor caso!
   
Insertion Sort
● No pior caso, temos o vetor em ordem reversa
● Assim o laco interno executará o maior número de vezes
while (i >= 0 && vector[i] > key) {
vector[i+1] = vector[i];
i--;
}
Custo
c4
c5
c6
# Vezes
   
Insertion Sort
● No pior caso, temos o vetor em ordem reversa
● Para  primeira  operacão  do  laco  externo,  o  laco  interno 
executará uma vez
– Para segunda  operacão  do  laco  externo, o  laco  interno 
executará 2 vezes
– Para  a  operacão  k  do  laco  externo,  o  laco  interno 
executará k vezes 
   
Insertion Sort
● No pior caso, temos o vetor em ordem reversa
● Considere um vetor com n = 10
● Nesse caso:
● Substituindo, temos:
   
Insertion Sort
● No pior caso, temos o vetor em ordem reversa
● Simplificando, obtemos:
No pior caso obtemos 
um número quadrático 
de operacões!
   
Insertion Sort
● Melhor plotar as funcões que definem o número de operacões 
para o melhor e o pior caso
● Como fica o caso médio?
● Deve  contar  com metade  dos elementos  do vetor  for  a  de 
ordem
● Isso  reduz  pela  metade  o  volume  de  operacões  do  laco 
interno
● No entanto, a funcão continua quadrática
– Melhor plotar!
   
Insertion Sort
● Usualmente projetistas de algoritmos:
● Calculam apenas o pior caso
● Pois o algoritmo nunca executará mais operacões que isso
– Assim  temos um upper bound ou  limite  superior para o 
número de operacões
   
Exercícios
● Exercícios:
● Ilustre por meio de figuras o funcionamento do algoritmo Insertion Sort 
para as seguintes chaves:
31, 41, 59, 26, 41, 58
● Reescreva  o  algoritmo  Insertion  Sort  para  ordenar  de  maneira 
decrescente
● Considerando  uma  funcão  de  distribuicão  de  probabilidades  Uniforme 
com valor mínimo 0 e máximo MAX­1. Gere um arquivo com n números 
aleatórios, em que n é definido pelo usuário:
– Leia  esse  arquivo  em  memória  dinamicamente  alocada  (Memória 
Heap)
– Ordene o vetor com todas essas chaves usando Insertion Sort
– Varie  n  e  calcule  o  tempo  consumido  na  carga  das  chaves  em 
memória e na ordenacão em separado  (usando as  funcões  time e 
gettimeofday)
   
Bubblesort
● Outro algoritmo muito popular para a ordenacão é o Bubblesort 
ou algoritmo da Bolha
void bubblesort(int *vector, int n) {
int i, j;
int aux;
for (i = 0; i < n-1; i++) {
for (j = n-1; j >= i+1; j--) {
if (vector[j] < vector[j-1]) {
aux = vector[j];
vector[j] = vector[j-1];
vector[j-1] = aux;
}
}
}
}    
Bubblesort
● Ao analisar o pior caso de execucão:
● Teríamos um vetor ordenado de maneira decrescente...
void bubblesort(int *vector, int n) {
int i, j;
int aux;
for (i = 0; i < n-1; i++) {
for (j = n-1; j >= i+1; j--) {
if (vector[j] < vector[j-1]) {
aux = vector[j];
vector[j] = vector[j-1];
vector[j-1] = aux;
}
}
}
}
Custo e # operacões
c1 * (n­1)
c2 * (n*(n­1)) / 2 + 1
c3 * (n*(n­1)) / 2
c4 * (n*(n­1)) / 2
c5 * (n*(n­1)) / 2
c6 * (n*(n­1)) / 2
   
Bubblesort
● Ao analisar o pior caso de execucão:
● Temos:
● Simplificando:
● Temos uma funcão de ordem quadrática para definirmos o 
número de operacões para o Bubblesort no pior caso    
Bubblesort
● No pior caso há diferencas significativas entre o Bubblesort e o 
Insertion Sort?
● No melhor caso há diferencas significativas entre ambos?
   
Exercícios
● Exercícios:
● Considerando  uma  funcão  de  distribuicão  de  probabilidades  Uniforme 
com valor mínimo 0 e máximo MAX­1. Gere um arquivo com n números 
aleatórios, em que n é definido pelo usuário:
– Leia  esse  arquivo  em  memória  dinamicamente  alocada  (Memória 
Heap)
– Ordene  o  vetor  com  todas  essas  chaves  usando  Bubblesort  e 
compare  seu  resultado  ao  Insertion  Sort,  conforme  o  número  de 
chaves aumenta
– Varie  n  e  calcule  o  tempo  consumido  na  carga  das  chaves  em 
memória e na ordenacão em separado  (usando as  funcões  time e 
gettimeofday)
   
Merge Sort
● O algoritmo Insertion Sort, utiliza uma abordagem incremental
● Ou seja, mantém um grupo (ou elemento do lado esquerdo 
do vetor) ordenados
● Novos  elementos  são  avaliados  e  ordenados  com  base 
nesse grupo
● Há outras maneiras de projetar algoritmos:
● Uma  das  mais  conhecidas  é  baseada  no  paradigma  de 
divisão e conquista
● O  algoritmo  de  ordenacão  Merge  Sort  é  baseado  nesse 
paradigma
   
Merge Sort
● Considere o vetor:
● Merge Sort:
● Divide o problema em problemas menores
● Ordena os subproblemas até chegar ao vetor final ordenado
5 2 4 7 1 3 2 6
   
Merge Sort
● Merge Sort   Etapa de Divisão:→
5 2 4 7 1 3 2 6
25 4 7 1 3 2 6
45 2 7 1 23 6
5 2 4 7 1 3 2 6
   
Merge Sort
● Merge Sort   Etapa de Merge:→
5 2 4 7 1 3 2 6
52 4 7 1 3 2 6
52 4 7 1 32 6
5 2 4 7 1 3 2 6
   
Merge Sort
● Merge Sort:
● A etapa de divisão requer alguns conhecimentos extras
● Logo, comecemos com a etapa de Merge
   
Merge Sort
● Etapa de Merge:
void merge(int *vector, int p, int q, int r) {
 int k, i, j;
 int n1 = q - p + 2;
 int n2 = r - q + 1;
 // criando vetores auxiliares
 int *left= (int *) malloc(sizeof(int) * n1);
 int *right= (int *) malloc(sizeof(int) * n2);
 // copiando para vetores auxiliares
 for (i = 0; i < n1-1; i++)
 left[i] = vector[p + i];
 for (j = 0; j < n2-1; j++)
 right[j] = vector[q + 1 + j];
 left[n1-1] = 1000;
 right[n2-1] = 1000;
Custo e 
# Operacões
c1
c2
c3
c4
c5 * (n/2+1)
c6 * (n/2)
c7 * (n/2+1)
c8 * (n/2)
c9
c10
   
Merge Sort
● Etapa de Merge:
 i = 0;
 j = 0;
 for (k = p; k <= r; k++) {
 if (left[i] <= right[j]) {
 vector[k] = left[i];
 i++;
 } else {
 vector[k] = right[j];
 j++;
 }
 }
}
Custo e 
# Operacões
c11
c12
c13 * (n + 1)
c14 * n
c15 * n/2
c16 * n/2
c17 * n/2
c18 * n/2
   
Merge Sort
● Etapa de Merge:
● Observe que o número de operacões é de ordem linear
● Ou seja:
   
Merge Sort
● No entanto, há ainda a etapa de divisão:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Merge requer um 
número linear de 
operacões para 
resolver cada nó 
dessa árvore!
   
Merge Sort
● No entanto, há ainda a etapa de divisão:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Por exemplo, o 
custo neste nível 
depende da soma 
de 8 funcões 
lineares
   
Merge Sort
● No entanto, há ainda a etapa de divisão:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
A soma de oito 
funcões lineares 
resulta em outra 
funcão linear!
   
Merge Sort
● No entanto, há ainda a etapa de divisão:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
O mesmo 
ocorre nos 
demais níveis!
   
Merge Sort
● No entanto, há ainda a etapa de divisão:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Pensando no pior 
caso:
- Podemos simplificar 
e assumir n operacões 
por nível!
- Dessa maneira só o 
termo mais 
importante, ou seja, 
aquele que domina o 
número de operacões, 
será considerado
- esse termo é 
chamado de ordem de 
crescimento ou 
simplesmente ordem
   
Merge Sort
● No entanto, há ainda a etapa de divisão:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Ordem de crescimento 
das operacões para o 
procedimento Merge:
n
n
n
n
   
Merge Sort
● No entanto, há ainda a etapa de divisão:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Resta apenas 
conhecermos a altura 
dessa árvore:
Como dividimos em 2 
ramos temos:
2níveis = número total de 
termos no vetor a ser 
ordenado
O que pode ser 
simplificado para:
log2 n
   
Merge Sort
● No entanto, há ainda a etapa de divisão:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Como temos operacões 
da ordem de crescimento 
n por nível
E temos log2 n níveis
Logo o número total de 
operacões é da ordem de:
n log2 n operacões
   
Merge Sort
● Podemos calcular de maneira exata para um computador
● Para isso precisaremos das constantes da equacão:
● E  aplicaremos  essa  equacão  para  cada  nó  da  árvore  em 
que o vetor original foi dividido
   
Merge Sort
● Assim teremos o número exato de operacões de ordem  linear 
por nível da árvore:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Neste caso temos:
f(n)+ f(n) + f(n) + f(n)
Pois há quatro níveis na árvore
Considerando que a árvore tem 
em suas folhas apenas um 
elemento, o vetor original tem 15 
elementos
Assim log
2
 15 = 3.906
Precisamos do teto desse valor, 
ou seja:
Assim ceiling(log
2
 15) = 4
   
Merge Sort
● Assim teremos o número exato de operacões de ordem  linear 
por nível da árvore:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8
Agora podemos computar:
f(n) * ceiling(log
2
 15)
E obter o número total de 
operacões para certo 
computador
Mas repare que a ordem de 
crescimento é mais importante
Ou seja, a tendência de uma 
funcão DOMINA seu 
comportamento em termos do 
número de operacões!
   
Merge Sort
● Comparemos  Insertion  Sort  e  Merge  Sort  em  termos  do 
número de operacões no pior caso:
● Plotar
– Insertion Sort:
– Merge Sort:
   
Merge Sort
● Vimos que o Merge Sort requer um número significativamente 
menor de operacões que o Insertion Sort
● Mas  resta  implementar  o  procedimento  que  realiza  a  divisão, 
ou  seja,  cria  a  árvore  para  que  essa  seja,  posteriormente, 
encaminhada para o procedimento de merge
● Esse procedimento de merge utiliza o conceito de recorrência 
ou recursão
● Quebra de um problema em subproblemas mais simples
● Simplifica resolucão
   
Merge Sort
● Procedimento  de  divisão  para  funcionamento  do  algoritmo 
Merge Sort:
● Vamos analisar esse procedimento...
void merge_sort(int *vector, int p, int r) {
 if (p < r) {
 int q = (int) (p+r)/2.0;
 merge_sort(vector, p, q);
 merge_sort(vector, q+1, r);
 merge(vector, p, q, r);
 }
}
   
Merge Sort
● Primeiramente note que a funcão é denominada merge_sort
● Essa funcão recebe parâmetros
● Observe  que  dentro  da  funcão  ocorrem  duas  chamadas 
para a própria funcão
– Isso é recursão!
void merge_sort(int *vector, int p, int r) {
 if (p < r) {
 int q = (int) (p+r)/2.0;
 merge_sort(vector, p, q);
 merge_sort(vector, q+1, r);
 merge(vector, p, q, r);
 }
}
   
Merge Sort
● Vamos ver recursão com calma e voltamos ao Merge Sort...
   
Recursão
● Em  matemática,  Recursão  é  o  ato  de 
definir  um  objeto  (geralmente  uma 
funcão) em termos do próprio objeto
● Em  computacão,  Recursão  ocorre 
quando  um dos  passos  de um  algoritmo 
envolve  a  repeticão  desse  mesmo 
algoritmo
Imagem obtida em: http://www.megamonalisa.com/recursion/index.php?page=comments
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
   
Recursão
● Em Recursão precisamos definir:
● Caso base:
– Parte não recursiva, também chamada de âncora, ocorre 
quando a resposta para o problema é trivial
● Passo indutivo:
– Especifica  como  cada  solucão  é  gerada  à  partir  da 
anterior
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
   
Recursão
● Por exemplo:
● A funcão fatorial n! pode ser definida como:
– Dado um número inteiro positivo n:
● Vamos implementar...
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
   
Recursão
● Funcão recursiva para o cálculo do Fatorial
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
unsigned long fatorial(int n) {
unsigned long resultado = 1; // caso base
if (n > 1)
resultado = n * fatorial(n-1); // passo indutivo
return resultado;
}
   
Recursão
● Funcionamento:
● A  forma  que  um  compilador  implementa  um  procedimento 
recursivo é por meio de uma Pilha
● Há  duas  memórias  quando  um  processo  (ou  programa) 
inicia execucão:
– Memória Pilha
● Quando  processo  inicia,  ele  “ganha”  uma  região  da  memória 
RAM para servir de Pilha
● Tem tamanho máximo fixo
– Memória Heap
● É a memória dinâmica
● É aquela que alocamos quando usamos malloc, free e realloc
● Devemos liberar após uso
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
fatorial(4);
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4Parâmetro (n) é colocado na Pilha
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
fatorial(4);
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
Endereco de retorno da funcão 
fatorial é colocado na Pilha
0x00FF00FF
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
fatorial(4);
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
Variável local (resultado) é 
definida na Pilha
0x00FF00FF
unsigned long fatorial(int n) {
unsigned long resultado = 1; // caso base
if (n > 1)
resultado = n * fatorial(n-1); // passo indutivo
return resultado;}
1
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
fatorial(4);
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
Variável local (resultado) é 
definida na Pilha
0x00FF00FF
unsigned long fatorial(int n) {
unsigned long resultado = 1; // caso base
if (n > 1)
resultado = n * fatorial(n-1); // passo indutivo
return resultado;
}
1
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
fatorial(4);
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
Como n > 1, então chamada 
ocorre novamente! 0x00FF00FF
unsigned long fatorial(int n) {
unsigned long resultado = 1; // caso base
if (n > 1)
resultado = n * fatorial(n-1); // passo indutivo
return resultado;
}
1
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
fatorial(4);
fatorial(3);
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
0x00FF00FF
1
3Parâmetro n=3 é colocado na Pilha
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
fatorial(4);
fatorial(3);
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
0x00FF00FF
1
3
Endereco de retorno é colocado na Pilha 0x00AA00AA
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
fatorial(4);
fatorial(3);
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
0x00FF00FF
1
3
Variável local (resultado) é definida na Pilha
0x00AA00AA
1
Isso continua a ocorrer até...
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
fatorial(4);
fatorial(3);
fatorial(2);
fatorial(1);
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
0x00FF00FF
1
3
0x00AA00AA
1
2
0x00AA00AA
1
1
0x00AA00AA
1
Agora comecam os returns...
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
0x00FF00FF
1
3
0x00AA00AA
1
2
0x00AA00AA
1
Fatorial(1) retorna 1 para a 
chamada predecessora
unsigned long fatorial(int n) {
unsigned long resultado = 1;
if (n > 1)
resultado = n * fatorial(n-1);
return resultado;
}
1
0x00AA00AA
1
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
0x00FF00FF
1
3
0x00AA00AA
1
2
0x00AA00AA
1
A chamada predecessora 
multiplica o retorno de fatorial(1) 
por n e armazenada em sua 
variável local
Depois retorna a variável local
unsigned long fatorial(int n) {
unsigned long resultado = 1;
if (n > 1)
resultado = n * fatorial(n-1);
return resultado;
}
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
0x00FF00FF
1
3
0x00AA00AA
1
2
0x00AA00AA
2
Assim...
E agora retorna para a chamada 
predecessora...
unsigned long fatorial(int n) {
unsigned long resultado = 1;
if (n > 1)
resultado = n * fatorial(n-1);
return resultado;
}
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
0x00FF00FF
1
3
0x00AA00AA
6
Assim...
E agora retorna para a chamada 
predecessora a qual multiplica por n 
e armazena em sua variável local
unsigned long fatorial(int n) {
unsigned long resultado = 1;
if (n > 1)
resultado = n * fatorial(n-1);
return resultado;
}
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
4
0x00FF00FF
24
A mesma etapa ocorre uma vez 
mais...
E a funcão retorna sua variável local 
resultado = 24 para quem invocou 
fatorial(4)
unsigned long fatorial(int n) {
unsigned long resultado = 1;
if (n > 1)
resultado = n * fatorial(n-1);
return resultado;
}
   
Recursão
● Exemplo de funcionamento da Pilha na execucão de:
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
Finalmente toda memória alocada na Pilha (Stack) é 
liberada!
É interessante saber que qualquer procedimento ou 
funcão que chamamos usa a Pilha → Não importa se é 
ou não recursivo!
unsigned long fatorial(int n) {
unsigned long resultado = 1;
if (n > 1)
resultado = n * fatorial(n-1);
return resultado;
}
   
Recursão
● Alguns pontos importantes sobre recursividade:
● Saber quando parar:
– Devemos definir o caso base
● Decidir como fazer o primeiro passo:
– Pensar em como quebrar o problema em subproblemas 
que possam ser resolvidos
● Definir a recorrência:
– Encontrar uma maneira para que uma funcão chame a si 
mesma, passando via parâmetros, problemas menores a 
serem resolvidos
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
Fonte: http://www.dcc.ufam.edu.br/~ruiter/icc/martin4.html
   
Recursão
● Vamos criar  uma  funcão  recursiva para  Fibonacci  e  comparar 
com a versão iterativa
● Quando devemos evitar Recursão?
● Pode  haver  muitas  chamadas  recursivas  e  estourar  a 
Memória Pilha ou Memória Stack
● No entanto, pode haver um problema de recursão infinita:
– Não definimos o caso base
– Assim recursão nunca para
● Na verdade termina com Stack Overflow
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
   
Recursão
● Ainda sobre recursão:
● Há a recursão indireta:
– Uma funcão A chama a funcão B que chama C, a qual, 
por sua vez, chama A novamente
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
   
Exercícios
● Exercícios:
● Implemente uma funcão recursiva que exiba todas as substrings de uma 
string. Dica: apresente todas as subtrings que comecam com o primeiro 
caracter. Existem n substrings para uma string com tamanho n. Depois 
remova  o  primeiro  caracter  e  enumere  suas  strings  e  assim 
sucessivamente. Exemplo: substrings de rum: r, ru, rum, u, um, m
● Crie  uma  funcão  que  recebe  um  vetor  e  retorna  o  maior  elemento 
contido nele. Dica: Subdivida o vetor em partes menores e continue sua 
busca pelo maior
Slide baseado no material de Moacir Ponti Jr (ICMC­USP)
   
Exercícios
● Exercícios:
● Implemente uma funcão recursiva para calcular a série, em que n é um 
inteiro maior ou igual a 1:
● Pitágoras  estudou  e  formulou  muitos  dos  aspectos  de  música  hoje 
conhecidos. Ele percebeu que ao  tocar uma corda de um  instrumento, 
essa  vibrava  não  somente  na  sua  extensão  total,  mas  também  em 
seções menores.  Assim,  a  frequência  final  de  uma  corda é  dada  pela 
soma abaixo. Implemente um procedimento recursivo para calculá­la:
   
Merge Sort
● Voltemos agora ao estudo do Merge Sort...
● Vejamos novamente o procedimento Merge Sort
void merge_sort(int *vector, int p, int r) {
 if (p < r) {
 int q = (int) (p+r)/2.0;
 merge_sort(vector, p, q);
 merge_sort(vector, q+1, r);
 merge(vector, p, q, r);
 }
}
   
Exercícios
● Exercícios:
● Por  meio  de  figuras,  ilustre  o  funcionamento  do  algoritmo  Merge  Sort 
para o vetor com chaves: 3, 41, 52, 26, 38, 57, 9, 49
● Insertion  Sort  pode  ser  expresso  como  um  procedimento  recursivo? 
Como seria implementado?
● Observe  que  se  o  vetor  estiver  ordenado,  podemos  implementar  uma 
busca que verifica o elemento central do vetor, eliminando metade dos 
elementos. Busca binária repete esse procedimento recursivamente:
– Implemente uma busca binária usando recursão sobre um vetor de 
inteiros. Essa funcão recebe um inteiro denominado chave, o qual é 
o  inteiro que desejamos encontrar no vetor. Dica: Nessa técnica de 
busca  comparamos  nosso  inteiro  ao  elemento  central  do  vetor,  se 
menor continuamos nossa busca à esquerda do vetor, caso contrário 
à  direita.  Assim  reduzimos,  a  cada  passo,  a  quantidade  de 
elementos a serem considerados
– Prove que o pior caso desse algoritmo requer 1+ ⌊log
2
n⌋ operacões
   
Exercícios
● Exercícios:
● Considerando  uma  funcão  de  distribuicão  de  probabilidades  Uniforme 
com valor mínimo 0 e máximo MAX­1. Gere um arquivo com n números 
aleatórios, em que n é definido pelo usuário:
– Leia  esse  arquivo  em  memória  dinamicamente  alocada  (Memória 
Heap)– Ordene  o  vetor  com  todas  essas  chaves  usando  Merge  Sort  e 
compare seu resultado ao Insertion Sort e ao Bubblesort, conforme 
o número de chaves aumenta
– Varie  n  e  calcule  o  tempo  consumido  na  carga  das  chaves  em 
memória e na  ordenacão em separado  (usando  as  funcões  time e 
gettimeofday)
   
Eficiência Assintótica de Algoritmos
● Não  precisamos  computar  com  detalhes  o  número  de 
operacões que um algoritmo realiza em funcão das entradas
● Mas  sim  a  ordem  de  crescimento  da  funcão  que  define  o 
número de operacões do algoritmo em funcão da entrada
● Por  exemplo,  podemos  representar  o  número  de  operacões 
para o pior caso conforme:
● Insertion Sort   da ordem de n→ 2 operacões
● Bubble Sort   da ordem de n→ 2 operacões
● Merge Sort   da ordem de n log→
2
 n operacões
   
Eficiência Assintótica de Algoritmos
● A partir dessas funcões de crescimento:
● Podemos  estudar  o  comportamento  assintótico  dos 
algoritmos
● O  comportamento  assintótico  é  aquele  para  entrada  cujo 
tamanho tende ao infinito
   
Eficiência Assintótica de Algoritmos
● Há  uma  notacão  específica  para  representar  a  eficiência  de 
Algoritmos, ela envolve:
● A notacão Θ (Teta maiúsculo)
● A notacão O (O maiúsculo)
● A notacão Ω (Omega maiúsculo)
● A notacão o (o minúsculo)
● A notacão ω(omega minúsculo)
   
Eficiência Assintótica de Algoritmos
● Definicão da Notacão Θ (Teta maiúsculo)
● Quando usada, esta notacão representa que há constantes que 
se multiplicadas  por  g(n),  permitem  “cercar”  tanto  por  valores 
menores quanto maiores a funcão f(n)
● Assim sabemos que basta multiplicar g(n) por duas constantes 
distintas  para  obtermos um  limite  inferior e  um  limite  superior 
para f(n)
   
Eficiência Assintótica de Algoritmos
● Definicão da Notacão Θ (Teta maiúsculo)
c1 * g(n)
c2 * g(n)
f(n)
Tamanho de n
#
 O
pe
ra
cõ
es
Temos, assim, uma 
notacão assintótica 
para representar 
limites “estreitos” 
que permitem que 
conhecamos as 
tendências de um 
algoritmo para 
entradas de 
grandes tamanhos
n0
   
Eficiência Assintótica de Algoritmos
● Notacão Θ (Teta maiúsculo)
● Em estudos anteriores, calculamos com detalhes o número 
de operacões para alguns algoritmos
● Depois notamos que não a necessidade de tantos detalhes, 
mas sim da ordem de crescimento do número de operacões
● Assuma, por exemplo, que a  funcão a seguir define o número 
de operacões para um algoritmo:
● Conforme  vimos  poderíamos  simplificar  e  dizer  que  esse 
algoritmo requer da ordem de n2 operacões, mas como provar 
isso?
   
Eficiência Assintótica de Algoritmos
● Notacão Θ (Teta maiúsculo)
● Definimos,  então  duas  constantes  que  devem  ser  usadas 
para  criar  um  limite  superior  e  outro  inferior  ao  redor  da 
funcão f(n), na forma:
● Agora  podemos  definir  os  valores  para  as  constantes, 
permitindo que tenhamos dois limites
Dividindo por n2 cada termo temos:
   
Eficiência Assintótica de Algoritmos
● Notacão Θ (Teta maiúsculo)
● Essas funcões que definem o número de operacões NUNCA 
podem:
– ser negativas
– Produzir valor igual a zero
● Ambos os casos seriam irreais
● Verificando  as  constantes,  notamos  que  para  n ≥  7,  ambas 
constantes  tornam­se  positivas  e,  portanto  as  funcões  que 
definem os limites inferior e superior também serão positivas
   
Eficiência Assintótica de Algoritmos
● Notacão Θ (Teta maiúsculo)
● Assim, escolhendo, por exemplo:
c1 = 1/14
c2 = ½
n
0
 = 7
● Temos que a relacão abaixo é válida:
● Ou seja, há  limites bem estreitos que nos permitem afirmar 
que o número de operacões desse algoritmo é da ordem de 
n2
   
Eficiência Assintótica de Algoritmos
● Notacão Θ (Teta maiúsculo)
● Quando um algoritmo tem número constante de operacões, 
podemos escrever:
● Também  podemos  provar  que  um  algoritmo  com                     
operacões não tem limites estreitos na forma:
● Ou seja:
   
Eficiência Assintótica de Algoritmos
● Segundo a Notacão Θ devemos encontrar:
● Dividindo os termos por n2 temos:
● Note, no entanto, que chegamos a:
● Mas  c2  é  uma  constante  e  assim  n  nunca  poderia  ser 
suficientemente grande!
● Essa contradicão permite provar que:
   
Eficiência Assintótica de Algoritmos
● Notacão O (O maiúsculo)
● A  notacão Θ representa  um  limite  inferior  e outro  superior 
para o número de operacões executadas por um algoritmo
● Quando temos apenas um limite superior, usamos a notacão O, 
na forma:
   
Eficiência Assintótica de Algoritmos
● Notacão O (O maiúsculo)
c * g(n)
f(n)
Tamanho de n
#
 O
pe
ra
cõ
es
Temos, assim, uma 
notacão assintótica 
para representar 
um limite superior 
um algoritmo
n0
   
Eficiência Assintótica de Algoritmos
● Notacão O (O maiúsculo)
● Note que a notacão Θ é mais forte que a notacão O
● A notacão Θ implica na notacão O
● Por  exemplo,  um  algoritmo  com  número  linear  de  operacões 
tem Θ(n) no entanto pode ter O(n), O(n2), … 
● Ou  seja  a  notacão O  não é  necessariamente  próxima  ou  um 
limite estreito para f(n) tal como Θ
   
Eficiência Assintótica de Algoritmos
● No  entanto,  a  notacão  O  (O  maiúsculo)  é  comumente 
empregada na literatura como limite superior estreito
● Como a notacão O não é um limite superior estreito, podemos 
calculá­la  simplesmente  observando  estruturas  gerais  de  um 
algoritmo
● Por exemplo, para um algoritmo com dois lacos, um interno 
e outro externo  tal  como o  Insertion Sort ou o BubbleSort, 
podemos definir O(n2)
   
Eficiência Assintótica de Algoritmos
● A notacão Ω (Omega maiúsculo)
● Assim  como  a  notacão O  provê  um  limite  superior  para  o 
número  de  operacões  de  um  algoritmo,  a  notacão  Ω 
representa um número inferior para o número de operacões 
de um algoritmo
   
Eficiência Assintótica de Algoritmos
● Notacão Ω (Omega maiúsculo)
c * g(n)
f(n)
Tamanho de n
#
 O
pe
ra
cõ
es
Temos, assim, uma 
notacão assintótica 
para representar 
um limite inferior 
para o número de 
operacões de um 
algoritmo
n0
   
Eficiência Assintótica de Algoritmos
● Sobre as notacões vistas:
● Há  um  teorema  resume  a  notacão  Θ em  funcão  das 
notacões O e Ω, como segue:
   
Eficiência Assintótica de Algoritmos
● Sobre as notacões vistas:
● Como a notacão Ω representa um limite inferior
– Usamos  ela  para  representar  o  melhor  caso  de  um 
algoritmo
● Como a notacão O representa um limite superior
– Usamos  ela  para  representar  o  pior  caso  de  um 
algoritmo
● Por exemplo, para o Insertion Sort temos:
● Logo o número de operacões desse algoritmo está entre esses 
dois limites
   
Eficiência Assintótica de Algoritmos
● Algumas vezes encontramos equacões na forma:
● A qual  indica que há  uma  funcão anônima  da  ordem de n 
que  não  nos  importamos  em  definir  por  completo,  pois  o 
número de operacões do algoritmo é dominado pelo  termo 
n2
● Esse  tipo  de  “limpeza”  na  equacão  é  comum  quando 
estamos  preocupados  com  características  assintóticas  do 
algoritmo
   
Eficiência Assintótica de Algoritmos
● A notacão o (o minúsculo)
● A notacão O pode ou não definir um limite superior estreito 
ou próximo ao número de operacões de um algoritmo
● Por exemplo:
– No exemplo abaixo a notacão O é próxima
– No exemplo abaixo a notacão O não é próxima
   
Eficiência Assintótica de Algoritmos
● A notacão o (o minúsculo)
● Quando  sabemos  que  o  limite  superior  não  é  próximo,  o 
mais indicado é usar a notacão o (minúsculo)
● Por exemplo:
   
Eficiência Assintótica de Algoritmos
● A notacão ω(omega minúsculo)
● Por analogia, a notacão ω está para a notacão Ω tal como a 
notacão o está para O
● Utiliza­se  a  notacão ω para  representar  um  limite  inferior 
que não está próximo daquele do algoritmo em análise
● Por exemplo:
   
Eficiência Assintótica de Algoritmos
● Algumas propriedades:
● Transitividade:
● Reflexividade:
   
Eficiência Assintótica de Algoritmos● Algumas propriedades:
● Simetria:
● Simetria Transposta:
   
Eficiência Assintótica de Algoritmos
● Devido  à  validade  dessas  propriedades,  podemos  fazer  uma 
analogia entre a comparacão assintótica de duas funcões f e g 
e a comparacão entre dois números reais a e b na forma:
   
Exercícios
● Exercícios:
● Plote as seguintes  funcões e observe quando uma supera a outra em 
termos do número de operacões:
1000 * n
0,1 * n2
5000 * log
2
n
● O  caixeiro  viajante  ou  caminho  Hamiltoniano é  um  problema  em  que 
dado um conjunto de n cidades, o viajante deve  iniciar sua viagem em 
uma delas, passar por  todas as cidades exatamente uma vez, e voltar 
para a mesma cidade que iniciou consumindo o mínimo de recursos:
– Qual o número de operacões necessárias para obtermos uma solucão 
ideal para esse problema?
– Considere  uma  matrix  simétrica  com  as  distâncias  entre  pares  de 
cidades.  Considerando  que  desejamos  obter  o  caminho  mais  curto 
passando  por  todas  cidades  e  retornando  para  onde  iniciamos, 
implemente um algoritmo para resolver o problema do Caixeiro Viajante
   
Exercícios
● Exercícios:
● Como  voce  projetaria  um algoritmo  com menor número  de  operacões 
para  resolver  o  problema  do  Caixeiro  Viajante  visto  no  exercício 
anterior?
● Qual funcão é assintoticamente maior?
● Ordene, pelo número de operacões necessárias, as seguintes funcões:
● Dica: crie um programa e teste para n   → ∞    
Exercícios
● Exercícios:
● Encontre as duas contantes para que possamos criar um limite inferior e 
outro superior (notacão Θ) ao redor de cada uma das funcões a seguir:
   
Heapsort
● Assim como Insertion Sort, o Heapsort ordena “in place”
● Ordenar  “in  place”,  significa  alocar  um  número  limitado  de 
posicões de memória fora da estrutura de dados
● Assim como Merge Sort, o Heapsort tem número de operacões 
da ordem de O(n log
2
 n)
● Dessa  maneira  o  Heapsort  tem  as  vantagens  de  ambos 
algoritmos vistos anteriormente
   
Heapsort
● Heapsort  utiliza­se  de  uma 
estrutura  de  dados  chamada 
Heap
● Essa  estrutura  pode  ser 
vista  tal  como  uma  árvore 
binária completa
● Mesmo tendo essa estrutura 
“virtual” em forma de árvore 
binária, podemos representa 
um heap usando vetores
elemento elemento
elemento
elem elem elem elem
   
Heapsort
● Quando usando vetores:
● A raíz da árvore estaria no primeiro termo do vetor
● O pai de um nó ou elemento na posicão  i do vetor estaria 
em:
floor(i/2)
● O filho à esquerda de um nó ou elemento i estaria em:
2*i
● O filho à direita de um nó ou elemento i estaria em:
2*i+1
   
Heapsort
● Por exemplo:
● Considere o vetor:
● Qual a posicão do filho à esquerda da raíz?
2*1 = 2
● Qual a posicão do filho à direita da raíz?
2*1+1 = 3
16 14 10 8 7 9 3
 1        2        3        4        5       6       7
   
Heapsort
● Por exemplo:
● Considere o vetor:
● Qual a posicão do filho à esquerda da raíz?
2*1 = 2
● Qual a posicão do filho à direita da raíz?
2*1+1 = 3
16 14 10 8 7 9 3
 1        2        3        4        5       6       7
   
Heapsort
● Por exemplo:
● Considere o vetor:
● Qual a posicão do pai do elemento na posicão 3?
floor(3 / 2) = 1
● Qual a posicão do filho à esquerda?
2*3 = 6
● Qual a posicão do filho à direita?
2*3+1 = 7
16 14 10 8 7 9 3
1        2        3        4        5       6        7
   
Heapsort
● Por exemplo:
● Considere o vetor:
● Qual a posicão do pai do elemento na posicão 3?
floor(3 / 2) = 1
● Qual a posicão do filho à esquerda?
2*3 = 6
● Qual a posicão do filho à direita?
2*3+1 = 7
16 14 10 8 7 9 3
1        2        3        4        5       6        7
   
Heapsort
● Há dois tipos de Heaps:
● Max Heaps:
– Satisfaz a propriedade:
vector[parent(i)] ≥ vector[i]
– Neste caso o maior elemento está na raíz
● Min Heaps:
– Satisfaz a propriedade:
vector[parent(i)] ≤ vector[i]
– Neste caso o menor elemento está na raíz
   
Heapsort
● A  altura  de  um  nó  na 
Heap  é  definida  pelo 
número de arestas que o 
conectam até as folhas:
● A  altura  do  heap  é  dada 
pela altura de sua raíz elemento elemento
elemento
elem elem elem elem
Altura
2
1
0
   
Heapsort
● Agora veremos algoritmos que nos permitem:
● Construir o Heap
● Ordená­lo
● E outros complementares...
   
Heapsort
● Mantendo a propriedade do Heap
● O  Heapsort  é  tradicionalmente  construído  como  um  Max 
Heap, ou seja:
– Satisfaz a propriedade:
vector[parent(i)] ≥ vector[i]
– Neste caso o maior elemento está na raíz
● Assim  o  primeiro  procedimento,  chamado  Max_Heapify é 
responsável  por  verificar  se  um  nó  pai  contém  elemento 
menor que seus filhos
– Caso positivo, o pai deve “descer” na árvore
– Pois isso viola a propriedade de um Max Heap
   
Heapsort
● Procedimento Max Heapify
void max_heapify(int *vector, int position, int heapsize) {
 int largest;
 int left = LEFT(position);
 int right = RIGHT(position);
 if (left < heapsize && vector[left] > vector[position])
 largest = left;
 else
 largest = position;
 if (right < heapsize && vector[right] > vector[largest])
 largest = right;
 
 if (largest != position) {
 int aux = vector[position];
 vector[position] = vector[largest];
 vector[largest] = aux;
 max_heapify(vector, largest, heapsize);
 }
}
Heapsize é o 
número de 
elementos 
no Heap
Position 
indica para 
qual posicão 
do vetor 
iremos 
analisar a 
propriedade 
do Heap
   
Heapsort
● Funcionamento do Max Heapify:
● Observe que o elemento 4 na posicão 1 viola a propriedade do 
Max Heap
● Executando o max_heapify(vector, 1, 7) obtemos:
16 4 10 14 7 9 3
 0        1        2       3        4       5        6
   
Heapsort
● Executando o max_heapify(vector, 1, 7) obtemos:
● Primeiramente verifica qual dos filhos é maior
● Depois troca, ficando:
● Agora executa recursivamente sobre a posicão em que o maior 
estava, ou seja, posicão 3
● Mas como não há mais filhos, a execucão termina...
16 4 10 14 7 9 3
 0        1        2       3        4       5        6
16 14 10 4 7 9 3
 0        1        2       3        4       5        6
   
Heapsort
● Vamos analisar o número de operacões do procedimento Max 
Heapify
● Perceba  que  o  número  de  operacões  para  executar  esse 
procedimento sobre apenas um nó ou elemento é constante
– Ele não depende do número de termos na árvore
● No entanto, há uma chamada recursiva que no pior caso é 
invocada até o nó folha
– Isso  tende,  no  pior  caso,  a  percorrer  toda  a  altura  da 
árvore:
O(log
2
 n)
   
Heapsort
● Construindo o Heap:
● Observe o vetor abaixo:
● Ele tem um total de 7 elementos
● Perceba que:
● Da posicão 0 até floor(7/2)­1, ou seja, de 0 até 2 temos os 
nós que não são folhas
● Executamos o procedimento max_heapify sobre esses nós 
e assim teremos construído o heap
16 14 10 4 7 9 3
 0        1        2       3        4       5        6
   
Heapsort
● Procedimento Build Max Heap:
void build_max_heap(int *vector, int heapsize) {
 int i;
 for (i = floor(heapsize / 2.0)-1; i >= 0; i--) {
 max_heapify(vector, i, heapsize);
 }
}
   
Heapsort
● Qual o limite superior para o algoritmo Build Max Heap?
● Essa algoritmo chama o procedimento max_heapify que é 
O(log
2
 n)
● O  algoritmo  Build  Max  Heap  invoca  o  max_heapify  da 
ordem de O(n)
● Sendo assim o limite é dado por:
O(n log
2
 n)
● No entanto, há como computar com maior exatidão esse limite 
superior:
● Ou seja um limite superior mais estreito
   
Heapsort
● Finalmente chegamos ao Algoritmo Heapsort:
● Esse algoritmo primeiramente chama o procedimento Build 
Max Heap para construir o Max Heap
● Depois  retira o primeiro elemento do Heap e coloca como 
último do vetor
● Reorganiza o heap usando max_heapify
– Basta  executaresse  procedimento  sobre  o  primeiro 
elemento do vetor, ou seja, o elemento na posicão 0
   
Heapsort
● Algoritmo Heapsort:
void heapsort(int *vector, int nelements) {
 int i;
 build_max_heap(vector, nelements);
 for (i = nelements-1; i >= 1; i--) {
 int aux = vector[0];
 vector[0] = vector[i];
 vector[i] = aux;
 max_heapify(vector, 0, i);
 }
}
   
Heapsort
● Qual  a  ordem  de  crescimento  do  número  de  operacões 
executadas pelo Algoritmo Heapsort?
● Primeiramente ele executa o Build Max Heap   O(n log→
2
 n)
● Depois há um laco:
– Executa por n vezes
– Cada  operacão  é  constante  em  termos  da  troca  de 
elementos
– Max Heapify é da ordem de O(log
2
 n)
– Como executa por até n vezes, então:
O(n log
2
 n)
● Logo temos:
O(n log
2
 n) + O(n log
2
 n) = O(n log
2
 n)    
Filas de Prioridades
● A  mesma  estrutura  de  Heap  utilizada  pelo  algoritmo  Heapsort 
pode ser utilizada para criar filas de prioridades
● Essas  filas  têm  comumente  os  seguintes  procedimentos 
associados:
● Insert – inserir um elemento no heap
● Maximum/Minimum  –  retorna  o  elemento  com  maior/menor 
chave (caso seja um Max ou um Min Heap)
● Extract­Max/Extract­Min  –  remove  e  retorna  o  elemento  com 
maior/menor chave (caso seja um Max ou um Min Heap)
● Increase­Key/Decrease­Key –  incrementa/decrementa o valor 
de uma chave (caso seja um Max ou um Min Heap)
   
Filas de Prioridades
● Aplicacões:
● Escalonamento de processos
● Gerenciamento  de  Largura  de  Banda  em  Redes  de 
Computadores
● Simulacão orientada a Eventos
   
Filas de Prioridades
● Procedimentos:
void heap_maximum(int *vector) {
return vector[0];
}
int heap_extract_max(int *vector, int heapsize) {
if (heapsize < 1) {
printf(“Erro: heap underflow\n”);
return -1;
}
int max = vector[0];
vector[0] = vector[heapsize-1];
max_heapify(vector, 0, heapsize – 1);
return max;
}
O(1)
O(log2 n)
   
Filas de Prioridades
● Procedimentos:
void heap_increase_key(int *vector,
int position, int key) {
if (key < vector[position]) {
printf(“Key eh menor que a chave atual”);
return;
}
vector[position] = key;
while (position > 0 && 
 vector[PARENT(position)] < vector[position]) {
int aux = vector[PARENT(position)];
vector[PARENT(position)] = vector[position];
vector[position] = aux;
position = PARENT(position);
}
}
O(log2n)
Pois um nó 
folha pode 
subir por 
toda a 
altura da 
árvore até 
virar raíz
   
Filas de Prioridades
● Procedimentos:
void max_heap_insert(int *vector, int *heapsize, int key) 
{
 // deve haver espaco no vetor
vector[*heapsize] = INT_MIN;
*heapsize = *heapsize + 1;
heap_increase_key(vector, *heapsize, key);
}
O(log2n)
Pois utiliza heap_increase_key
   
Exercícios
● Exercícios:
● Formule,  matematicamente,  qual  é  o  número  mínimo  e  máximo  de 
elementos em um Heap cuja altura é h?
● Mostre que um heap com n elementos tem altura igual a  log⌊
2
 n⌋
– Como seria se, ao  invés de dois nós filhos, cada nó  tivesse k nós 
filhos?  Qual  seria  a  altura  de  um  heap  com  n  elementos  nesse 
caso? Demonstre
● Por  que  a  raiz  de  um  Max  Heap  sempre  contém  a  maior  chave? 
Demonstre
● Um vetor ordenado de maneira crescente é um Min Heap? Justifique e 
demonstre a construcão desse Min Heap
● A sequencia 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 é um Max Heap?
   
Exercícios
● Exercícios:
● Ilustre, com figuras, o funcionamento do Heapsort para o seguinte vetor: 27, 
17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0
● O  que  ocorre  com  o  procedimento  max_heapify(vector,  i)  quando  o 
elemento vector[i] é maior que seus filhos?
● Qual o efeito em chamar max_heapify para i > heapsize/2 at é heapsize­1
● Considerando uma funcão de distribuicão de probabilidades Uniforme com 
valor  mínimo  0  e  máximo  MAX­1.  Gere  um  arquivo  com  n  números 
aleatórios, em que n é definido pelo usuário:
– Leia  esse  arquivo  em  memória  dinamicamente  alocada  (Memória 
Heap)
– Ordene o vetor com todas essas chaves usando Heap Sort e compare 
seu  resultado ao  Insertion Sort, Bubblesort  e Merge Sort, conforme o 
número de chaves aumenta
– Varie n e calcule o tempo consumido na carga das chaves em memória 
e na ordenacão em separado (usando as funcões time e gettimeofday)
   
Quicksort
● Quicksort  é  um  algoritmo  de  ordenacão  cujo  pior  caso  é  da 
ordem de O(n2), no entanto:
● Seu caso médio é da ordem de n log
2
 n operações
– Mas as constantes “escondidas” nessa ordem são muito 
pequenas
● Devido ao pequeno valor dessas constantes:
● Quicksort  é  mais  indicado  que  até  mesmo  o  Merge  Sort, 
cujo pior caso é O(n log
2
 n)
   
Quicksort
● Quicksort,  assim  como Merge  Sort, é  baseado  no  paradigma 
de Divisão e Conquista:
void quicksort(int *vector, int left, int right) {
 int r;
 
 if (right > left) {
 r = partition(vector, left, right);
 quicksort(vector, left, r - 1);
 quicksort(vector, r + 1, right);
 }
}
   
Quicksort
● O procedimento partition que contém a maior parte da lógica do 
algoritmo:
int partition(int *vector, int left, int right) {
 int i, j;
 
 i = left;
 for (j = left + 1; j <= right; ++j) {
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
 }
 trocar(&vector[left], &vector[i]);
 
 return i;
}    
Quicksort
● Vamos compreender melhor o que ocorre com o procedimento 
partition
● Considere o sequinte vetor:
3 2 5 4 1
 0 1 2 3 4
left right
   
Quicksort
● Vamos compreender melhor o que ocorre com o procedimento 
partition
● O índice j varia de left + 1 até right 
3 2 5 4 1
 0 1 2 3 4
left, i rightj
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
   
Quicksort
● Vamos compreender melhor o que ocorre com o procedimento 
partition
3 2 5 4 1
 0 1 2 3 4
left righti, j
Incrementando i
Troca não altera vetor...
   
Quicksort
● Vamos compreender melhor o que ocorre com o procedimento 
partition
3 2 5 4 1
 0 1 2 3 4
left rightj
Incrementar j
i
   
Quicksort
● Vamos compreender melhor o que ocorre com o procedimento 
partition
3 2 5 4 1
 0 1 2 3 4
left rightj
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
i
   
Quicksort
● Vamos compreender melhor o que ocorre com o procedimento 
partition
● Em seguinte um índice j varia de left + 1 até right 
3 2 5 4 1
 0 1 2 3 4
left rightj
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
i
   
Quicksort
● Vamos compreender melhor o que ocorre com o procedimento 
partition
● Em seguinte um índice j varia de left + 1 até right 
3 2 5 4 1
 0 1 2 3 4
left right j
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
i
   
Quicksort
● Vamos compreender melhor o que ocorre com o procedimento 
partition
● Em seguinte um índice j varia de left + 1 até right 
3 2 1 4 5
 0 1 2 3 4
left right j
Incrementando i
Trocando...
i
   
Quicksort
● Vamos compreender melhor o que ocorre com o procedimento 
partition
● Em seguinte um índice j varia de left + 1 até right 
1 2 3 4 5
 0 1 2 3 4
left right
trocar(&vector[left], &vector[i]);
Trocando...
Retornar i
i
   
Quicksort
● O procedimento partition:
● Garante apenas a ordem do elemento na posicão i
● Depois retorna essa posicão para o quicksort
– Assim  quicksort  reinicia  procedimento  de  ordenacão  à 
direita e à esquerda do elemento i
1 2 3 4 5
 0 1 2 3 4
i
   
Quicksort
● Lógica do procedimento partition:
● Iniciamos com o vetor:
● Inicializamos o índicei como left, na forma:
3 2 5 4 1
 0 1 2 3 4
3 2 5 4 1
 0 1 2 3 4
left, i right
   
Quicksort
● Lógica do procedimento partition:
● Em seguida há um loop que varia j de left+1 até right:
● Dentro desse laco temos:
3 2 5 4 1
 0 1 2 3 4
left, i rightj
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
Repare que o IF testa 
se o elemento na 
posicão left é maior 
que o da posicão j
Caso positivo, temos 
uma inversão das 
chaves
   
Quicksort
● Lógica do procedimento partition:
● Em seguida há um loop que varia j de left+1 até right:
● Dentro desse laco temos:
3 2 5 4 1
 0 1 2 3 4
left right
i, j
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
Como há inversão, ele 
tenta trocar!
Mas neste caso o vetor 
não é alterado, pois:
i+1 = j
   
Quicksort
● Lógica do procedimento partition:
● Em seguida j é incrementado
● E voltamos para o laco:
3 2 5 4 1
 0 1 2 3 4
left rightj
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
Neste caso o IF retorna 
FALSE
Nenhuma troca é feita
i
   
Quicksort
● Lógica do procedimento partition:
● O índice j é incrementado novamente
● E voltamos para o laco:
3 2 5 4 1
 0 1 2 3 4
left rightj
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
Neste caso o IF retorna 
FALSE
Nenhuma troca é feita
i
   
Quicksort
● Lógica do procedimento partition:
● O índice j é incrementado novamente
● E voltamos para o laco:
3 2 5 4 1
 0 1 2 3 4
left right j
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
Neste caso o IF retorna 
TRUE
E uma troca é feita, 
pois a ordem relativa 
ao left não foi mantida
i
   
Quicksort
● Lógica do procedimento partition:
● O índice j é incrementado novamente
3 2 1 4 5
 0 1 2 3 4
left right j
Por que i é incrementado no momento da troca?
­ Observe que i guardava a posicão do elemento imediatamente 
   anterior à primeira chave que supera o elemento em left
­ Por isso i é incrementado no momento da troca
i
   
Quicksort
● Lógica do procedimento partition:
● O índice j é incrementado novamente
3 2 1 4 5
 0 1 2 3 4
left right j
Quando o laco termina, trocamos o elemento na posicão i com o 
elemento em left, por que?
­ Repare que o laco comparou todos os elementos a left
­ Left funcionou como base comparativa ou pivô
­ Segundo o algoritmo, o índice i para exatamente na posicão do 
        vetor em que o elemento em left deve ser colocado
i
   
Quicksort
● Lógica do procedimento partition:
● O índice j é incrementado novamente
3 2 1 4 5
 0 1 2 3 4
left right j
Após trocar o laco, o índice i fica, então, na posicão exata em que o 
elemento na posicão left deve ser colocado
E, então, o algoritmo retoma a execucão preocupando­se com os 
elementos à esquerda e à direita do pivô
i
   
Quicksort
● Vamos rever mais uma vez a lógica do Partition para o seguinte 
vetor:
5 4 3 2 1
 0 1 2 3 4
left, i rightj
int partition(int *vector, int left, int right) {
 int i, j;
 
 i = left;
 for (j = left + 1; j <= right; ++j) {
 if (vector[j] < vector[left]) {
 ++i;
 trocar(&vector[i], &vector[j]);
 }
 }
 trocar(&vector[left], &vector[i]);
 
 return i;
}
   
Quicksort
● Vamos rever mais uma vez a lógica do Partition para o seguinte 
vetor:
● Nosso pivô está na posicão left = 0
● O índice j varia de 1 até 4
– Repare que o IF SEMPRE é verdadeiro
● Pois a chave 5 é sempre maior que as demais
● Assim  o  índice  i  será  incrementado  junto  com  j  até 
chegar ao valor de i = 4
5 4 3 2 1
 0 1 2 3 4
left, i rightj
   
Quicksort
● Vamos rever mais uma vez a lógica do Partition para o seguinte 
vetor:
● Nesse momento chegamos à posicão correta para o pivô
● Ou seja, como nenhum termo é maior que o pivô, ele ficará 
no final do vetor
● É isso que a troca após o laco FOR realiza!
● Logo, teremos ao término do procedimento Partition...
5 4 3 2 1
 0 1 2 3 4
left right i, j
   
Quicksort
● Nessa execucão do procedimento Partition, teremos:
● Ao final o procedimento partition retorna o valor de i
● E  aí  retomamos  a  ordenacão  à  esquerda  e  à  direita  da 
posicão i
● No entanto, iremos retomar apenas à esquerda, pois não há 
elementos à direita
1 4 3 2 5
 0 1 2 3 4
left right i, j
   
Quicksort
● Nessa execucão do procedimento Partition, teremos:
● Neste  caso  particular  percebemos  que  o  laco  passou  por  n 
elementos
● Como  a  ordenacao  continuará  somente  de  um  dos  lados  do 
vetor, então teremos mais n­1 elementos para inspecionar
1 4 3 2 5
 0 1 2 3 4
left right i, j
   
Quicksort
● Sendo assim, para o pior caso, sempre iremos inspecionar em 
apenas um dos lados do índice i
● Isso faz com que o algoritmo tenha, no pior caso, ordem de 
O(n2) operacões
● No entanto, no caso médio, seu desempenho é melhor que 
o Merge Sort
– Mesmo ambos tendo O(n log
2
 n) operacões
– Mas Quicksort tem constantes menores na ordem
   
Quicksort
● Analisando o algoritmo Quicksort:
● Pior caso:
– Suponha  que  temos  certeza  apenas  sobre  a  ordem  do 
último elemento do vetor:
– Na  etapa  a  seguir,  teremos  que  operar  sobre  8 
elementos:
– E assim, sucessivamente
 1     2    3    4     5    6    7     8    9
 1     2    3    4     5    6    7     8    9
   
Quicksort
● Analisando o algoritmo Quicksort:
● Pior caso:
– Se  temos  n  elementos  no  vetor  inicial,  teremos  a 
seguinte ordem de operacões:
n operacões
n­1 operacões
n­2 operacões
n­3 operacões
…
1 operacão
– Assim temos uma série: n + (n­1) + (n­2) + … + 1
   
Quicksort
● Analisando o algoritmo Quicksort:
● Pior caso:
– A série: n + (n­1) + (n­2) + … + 1
– Pode ser expressa por: n * (n+1) / 2
– Assim  temos  um  funcão  de  ordem  de  crescimento  na 
forma:
   
Quicksort
● Analisando o algoritmo Quicksort:
● Melhor caso:
– No melhor caso o pivô ficaria ao centro do vetor a cada 
etapa
– Assim, a cada etapa teríamos metade dos elementos da 
anterior:
n termos
n/2 n/2
n/4 n/4 n/4 n/4
Assim, teríamos:
n operacões
n/2 + n/2 = n operacões
n/4+…+n/4 = n operacões
   
Quicksort
● Analisando o algoritmo Quicksort:
● Melhor caso:
– Como a altura da árvore é dada por log
2
n
– Então teremos a ordem de O(n log
2
n) operacões
   
Quicksort
● Analisando o algoritmo Quicksort:
● Caso médio:
– Considere um vetor desbalanceado
– Considere que ocorrerá um particionamento de 1­para­9 
a cada etapa
● Ou seja, a cada etapa:
– 10% dos elementos estarão de um lado
– 90% dos elementos do outro lado
   
Quicksort
● Analisando o algoritmo Quicksort:
● Caso médio:
– O lado com 10% formará uma ávore com altura:
– O lado com 90% formará uma árvore com altura:
   
Quicksort
● Analisando o algoritmo Quicksort:
● Caso médio:
– A cada etapa da árvore continuamos com n operacões
– Logo, teremos para o lado com 10%
– E para o lado com 90%
– Mesmo  para  um  caso  tão  desbalanceado,  a  ordem  de 
crescimento continua da ordem de O(n log n)
   
Quicksort
● Analisando o algoritmo Quicksort:
● Caso médio:
– O que ocorre se, em todos os níveis, houver uma quebra 
com 1% e 99% dos elementos para cada um dos lados?
– O lado mais alto da árvore terá:
– Portanto, a ordem de crescimento será:
– O que ainda é muito melhor que o pior caso!
   
Quicksort
● Analisando o algoritmo Quicksort:
● Caso médio:
– Plot para o pior caso versus:
● O caso com 1­para­9
● O caso com 1­para­99
● Etc...
   
Exercícios
● Exercícios
● Ilustre, com figuras, o funcionamento do Quicksort parao vetor: 13, 19, 9, 5, 
12, 8, 7, 4, 11, 2, 6, 21
● Considerando uma funcão de distribuicão de probabilidades Uniforme com 
valor  mínimo  0  e  máximo  MAX­1.  Gere  um  arquivo  com  n  números 
aleatórios, em que n é definido pelo usuário:
– Leia esse arquivo em memória dinamicamente alocada (Memória Heap)
– Ordene o vetor  com todas essas  chaves usando Quicksort e  compare 
seu  resultado  ao  Insertion  Sort,  Bubblesort,  Merge  Sort  e  Heap  Sort, 
conforme o número de chaves aumenta
– Varie n e calcule o tempo consumido na carga das chaves em mem ória 
e na ordenacão em separado (usando as funcões time e gettimeofday)
   
Exercícios
● Exercícios
● Qual valor o procedimento Partition  retorna quando  todos os elementos do 
vetor apresentam o mesmo valor?
● Altere  o  Quicksort  original  para  para  ordenar  vetores  de  maneira 
decrescente. Implemente.
● Ilustre,  com  figuras,  o  número  de  operacões  necessárias  para ordernar  o 
vetor 9,8,7,6,5,4,3,2,1,0 em:
– Ordem crescente usando o Quicksort
– Ordem decrescente usando o Quicksort
   
Ordenacão em Tempo Linear
● Os melhores algoritmos anteriores que vimos apresentam limite 
superior da ordem de O(n log
2
 n) operacões
● Mas como poderíamos reduzir esse número de operacões?
● Há  prova  que  algoritmos  que  realizam  comparacões  entre 
chaves para ordenar estão limitados pela ordem de O(n log
2
 n)
● No  entanto,  há  como  evitar  comparacões  e  obter  um 
algoritmo de ordenacão O(n)
   
Counting Sort
● O primeiro algoritmo que veremos é o Counting Sort
● Ele é da ordem de O(n) operacões
● Para  isso o Counting sort não realiza ordenacão “in­place”, ou 
seja, considerando apenas o próprio vetor
● Ele utiliza dois outros vetores auxiliares
● Portanto utiliza mais memória
   
Counting Sort
● Funcionamento do Counting Sort:
● Considere o vetor a ser ordenado:
● Como  primeira  etapa  criamos  um  vetor  auxiliar  capaz  de 
usar  a  maior  das  chaves  para  indexá­lo  (considerando  a 
menor chave >= 0), na forma:
– Maior chave é 7
– Menor chave é 0
0 7 2 2 1 3 5
 0        1        2       3        4       5        6
 0        1        2       3        4       5        6        7
Vector
Aux    
Counting Sort
● Funcionamento do Counting Sort:
● Agora inicializamos o vetor auxiliar com zeros
● Agora  percorremos  o  vetor  a  ser  ordenado  contando 
quantas  vezes  cada  chave  ocorre  (usamos  o  valor  das 
chaves para indexar o vetor auxiliar):
0 7 2 2 1 3 5
 0        1        2       3        4       5        6
0 0 0 0 0 0 0
 0        1        2       3        4       5        6        7
0
1 1 2 1 0 1 0
 0        1        2       3        4       5        6        7
1Aux
Aux
Vector
   
Counting Sort
● Funcionamento do Counting Sort:
● Agora  o  algoritmo  contabiliza  quantos  elementos  são 
menores que sua própria chave:
– Para isso calculamos a cumulativa do vetor auxiliar:
– Resultando em:
1 1 2 1 0 1 0
 0        1        2       3        4       5        6        7
1
1 2 4 5 5 6 6
 0        1        2       3        4       5        6        7
7
Aux
Aux
   
Counting Sort
● Funcionamento do Counting Sort:
● Finalmente  o  algoritmo  percorre  o  vetor  auxiliar  com  os 
valores acumulados e produz um vetor resultante R:
1 2 4 5 5 6 6
 0        1        2       3        4       5        6        7
7
 0        1        2       3        4       5        6
Para todo j = 0 até 7
R[Aux[Vector[j]]-1] = Vector[j]
Aux[Vector[j]] = Aux[Vector[j]] - 1
Aux
R
0 7 2 2 1 3 5
 0        1        2       3        4       5        6
Vector
   
Counting Sort
● Funcionamento do Counting Sort:
● Finalmente  o  algoritmo  percorre  o  vetor  auxiliar  com  os 
valores acumulados e produz um vetor resultante R:
0 2 4 5 5 6 6
 0        1        2       3        4       5        6        7
7
0
 0        1        2       3        4       5        6
Para todo j = 0 até 7
R[Aux[Vector[j]]-1] = Vector[j]
Aux[Vector[j]] = Aux[Vector[j]] - 1
Aux
R
0 7 2 2 1 3 5
 0        1        2       3        4       5        6
Vector
   
Counting Sort
● Funcionamento do Counting Sort:
● Finalmente  o  algoritmo  percorre  o  vetor  auxiliar  com  os 
valores acumulados e produz um vetor resultante R:
0 2 3 5 5 6 6
 0        1        2       3        4       5        6        7
6
0 2 7
 0        1        2       3        4       5        6
Para todo j = 0 até 7
R[Aux[Vector[j]]-1] = Vector[j]
Aux[Vector[j]] = Aux[Vector[j]] - 1
Aux
R
0 7 2 2 1 3 5
 0        1        2       3        4       5        6
Vector
   
Counting Sort
● Funcionamento do Counting Sort:
● Finalmente  o  algoritmo  percorre  o  vetor  auxiliar  com  os 
valores acumulados e produz um vetor resultante R:
0 2 2 5 5 6 6
 0        1        2       3        4       5        6        7
6
0 2 2 7
 0        1        2       3        4       5        6
Para todo j = 0 até 7
R[Aux[Vector[j]]-1] = Vector[j]
Aux[Vector[j]] = Aux[Vector[j]] - 1
Aux
R
0 7 2 2 1 3 5
 0        1        2       3        4       5        6
Vector
   
Counting Sort
● Funcionamento do Counting Sort:
● Finalmente  o  algoritmo  percorre  o  vetor  auxiliar  com  os 
valores acumulados e produz um vetor resultante R:
0 1 2 5 5 6 6
 0        1        2       3        4       5        6        7
6
0 1 2 2 7
 0        1        2       3        4       5        6
Para todo j = 0 até 7
R[Aux[Vector[j]]-1] = Vector[j]
Aux[Vector[j]] = Aux[Vector[j]] - 1
Aux
R
0 7 2 2 1 3 5
 0        1        2       3        4       5        6
Vector
   
Counting Sort
● Funcionamento do Counting Sort:
● Finalmente  o  algoritmo  percorre  o  vetor  auxiliar  com  os 
valores acumulados e produz um vetor resultante R:
0 1 2 4 5 6 6
 0        1        2       3        4       5        6        7
6
0 1 2 2 3 7
 0        1        2       3        4       5        6
Para todo j = 0 até 7
R[Aux[Vector[j]]-1] = Vector[j]
Aux[Vector[j]] = Aux[Vector[j]] - 1
Aux
R
0 7 2 2 1 3 5
 0        1        2       3        4       5        6
Vector
   
Counting Sort
● Funcionamento do Counting Sort:
● Finalmente  o  algoritmo  percorre  o  vetor  auxiliar  com  os 
valores acumulados e produz um vetor resultante R:
0 1 2 4 5 5 6
 0        1        2       3        4       5        6        7
6
0 1 2 2 3 5 7
 0        1        2       3        4       5        6
Para todo j = 0 até 7
R[Aux[Vector[j]]-1] = Vector[j]
Aux[Vector[j]] = Aux[Vector[j]] - 1
Aux
R
0 7 2 2 1 3 5
 0        1        2       3        4       5        6
Vector
   
Counting Sort
● Algoritmo Counting Sort:
int* counting_sort(int *vector, int size, int k) {
 int j;
 int *Aux = (int *) calloc(k, sizeof(int));
 int *R = (int *) malloc(sizeof(int) * size);
 // contagem
 for (j = 0; j < size; j++)
 Aux[vector[j]]++;
 // cumulativa
 for (j = 1; j < k; j++)
 Aux[j] += Aux[j-1];
 for (j = size-1; j >= 0; j--) {
 R[Aux[vector[j]]-1] = vector[j];
 Aux[vector[j]]--;
 }
 free(Aux);
 return R;
}
# Operacões
n
k
n
O(n)+O(k)+O(n)=O(n)
   
Exercícios
● Exercícios:
● Considerando  uma  funcão  de  distribuicão  de  probabilidades  Uniforme 
com valor mínimo 0 e máximo MAX­1. Gere um arquivo com n números 
aleatórios, em que n é definido pelo usuário:
– Leia  esse  arquivo  em  memória  dinamicamente  alocada  (Memória 
Heap)
– Ordene  o  vetor  com  todas  essas  chaves  usando  Counting  Sort  e 
compare  seu  resultado  ao  Insertion  Sort,  Bubblesort,  Merge  Sort, 
Heap Sort e Quicksort, conforme o número de chaves aumenta
– Varie  n  e  calcule  o  tempo  consumido  na  carga  das  chaves  em 
memória e na ordenacão em separado  (usando as  funcões  time e 
gettimeofday)
– Compare  a  quantidade  de  memória  que  os  demais  algoritmos 
necessitam versus a que o Counting Sort necessita
   
Exercícios● Exercícios:
● Ilustre, com figuras, o  funcionamento do Counting Sort para o vetor: 6, 
0, 2, 0, 1, 3, 4, 6, 1, 3, 2
   
Radix Sort
● Radix  Sort  aborda  o  problema  de  ordenacão  em  funcão  dos 
dígitos das chaves:
● Primeiramente ordena pelo dígito menos significativo
● Depois pelo segundo menos significativo
● Até o dígito mais significativo
Obtida de Cormen et al. Introduction to Algorithms
   
Radix Sort
● Radix Sort:
● É  de uso comum para ordenacão de chaves  formadas por 
múltiplos campos
– Por exemplo: ordenar por data (dia, mês, ano)
Pseudocódigo:
RADIX-SORT(vector, d) {
for i = digito_menos_signiticativo até digito_mais_significativo
do COUNTING-SORT(vector para o dígito i)
}
Sendo k constante, a ordem de crescimento no número 
de operacões: O(k*n) = O(n)
   
Exercícios
● Exercícios:
● Considerando  uma  funcão  de  distribuicão  de  probabilidades  Uniforme 
com valor mínimo 0 e máximo MAX­1. Gere um arquivo com n números 
aleatórios, em que n é definido pelo usuário:
– Leia  esse  arquivo  em  memória  dinamicamente  alocada  (Memória 
Heap)
– Ordene  o  vetor  com  todas  essas  chaves  usando  Radix  Sort  e 
compare  seu  resultado  ao  Insertion  Sort,  Bubblesort,  Merge  Sort, 
Heap  Sort,  Quicksort  e  Counting  Sort,  conforme  o  número  de 
chaves aumenta
– Varie  n  e  calcule  o  tempo  consumido  na  carga  das  chaves  em 
memória e na ordenacão em separado  (usando as  funcões  time e 
gettimeofday)
● Ilustre, com figuras, o  funcionamento do Radix Sort para o vetor: 1024, 
64, 32, 8, 2048, 4096, 16
   
Bucket Sort
● Bucket Sort  assume que as chaves  foram geradas a partir de 
uma distribuicão uniforme
● Há  outros  algoritmo  que  também  assumem  determinadas 
condicões:
– O  algoritmo  Counting  Sort  assume  que  chaves  estão 
distribuídas dentro de um pequeno intervalo
● Já que chaves foram geradas por uma distribuicão uniforme, se 
criamos um conjunto de buckets no intervalo das chaves:
● Cada  bucket  terá  probabilidade  de  assumir  o  mesmo 
número de chaves
   
Bucket Sort
● Funcionamento do Bucket Sort:
Obtida de Cormen et al. Introduction to Algorithms
   
Bucket Sort
● Ordem de Crescimento do número de operacões do Bucket Sort:
● O algoritmo é O(n)
– Exceto devido à execucão do Insertion Sort que no pior caso é 
O(n2)
● No entanto, temos n chaves que assumimos terem sido geradas por 
uma distribuicão Uniforme:
● Caso  criemos  k  buckets,  teremos  aproximadamente  n/k  chaves 
por bucket
– Por  exemplo,  se  k  =  n,  então  teremos  aproximadamente  1 
chave por bucket
● Na prática  o  número  de  chaves  por  bucket  tende  a  um número 
pequeno,  que  se  assumimos  como  constante  o  número  de 
operacões do Insertion Sort torna­se O(n)    
Bucket Sort
● Portanto  a  Ordem  de  Crescimento  do  número  de  operacões  do 
Bucket Sort é de O(n)
● Isso para uma distribuicão Uniforme das chaves
   
Exercícios
● Exercícios:
● Considerando  uma  funcão  de  distribuicão  de  probabilidades  Uniforme 
com valor mínimo 0 e máximo MAX­1. Gere um arquivo com n números 
aleatórios, em que n é definido pelo usuário:
– Leia  esse  arquivo  em  memória  dinamicamente  alocada  (Memória 
Heap)
– Ordene  o  vetor  com  todas  essas  chaves  usando  Bucket  Sort  e 
compare  seu  resultado  ao  Insertion  Sort,  Bubblesort,  Merge  Sort, 
Heap  Sort,  Quicksort,  Counting  Sort  e  Radix  Sort,  conforme  o 
número de chaves aumenta
– Varie  n  e  calcule  o  tempo  consumido  na  carga  das  chaves  em 
memória e na ordenacão em separado  (usando as  funcões  time e 
gettimeofday)
● Ilustre, com figuras, o funcionamento do Bucket Sort para o vetor: 0.79, 
0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42
   
Análise de Recorrência
● Quando um algoritmo contém uma chamada recursiva, ou seja, para 
si mesmo, ou um laço de repetição:
● Podemos geralmente descrever sua complexidade de  tempo por 
meio  de  uma  equação  de  recorrência  ou  função  de 
recorrência ou simplesmente recorrência
Algoritmo
Equação
de
Recorrência
Resolver recorrência
(retirar recorrência
e obter forma fechada)
Método de substituição
Método da árvore
Encontrar
constantes
Indução 
matemática
   
Análise de Recorrência
● Exemplo Mergesort
5 2 4 7 1 3 2 6
25 4 7 1 3 2 6
45 2 7 1 23 6
5 2 4 7 1 3 2 6
5 2 4 7 1 3 2 6
52 4 7 1 3 2 6
52 4 7 1 32 6
5 2 4 7 1 3 2 6
Etapa de Divisão Etapa de Merge
   
Análise de Recorrência
● Para o Mergesort:
● Mergesort  divide  o  vetor  enquanto  o  número  de  elementos  for 
maior que 1
● Mergesort continua divisão até haver somente 1 elemento
● Retorna e começa a etapa de merge ou intercalação
● Podemos representar a complexidade de tempo desse algoritmo pela 
seguinte equação de recorrência:
   
Análise de Recorrência
● Para o Mergesort:
● Observe que a equação de recorrência abaixo é genérica:
● Na verdade ela pode ser utilizada para computar a complexidade 
de  tempo  de  qualquer  algoritmo  baseado  no  paradigma  de 
Divisão e Conquista (exemplo Mergesort), em que:
– c é uma constante
– A função T é chamada recursivamente
– A  função  D  conta  o  número  de  operações  para  a  divisão  do 
problema
– A função C conta o número de operações para cada procedimento 
de Combinação ou Intercalação    
Análise de Recorrência
● Para o Mergesort:
● Assim a equação de recorrência:
● Pode ser reescrita para o Mergesort na forma:
– Divisão: O Mergesort apenas calcula o elemento central para 
dividir o vetor, assim D(n) = Θ(1)
– Conquista:  Recursivamente  resolvemos  dois  subproblemas, 
cada um de tamanho n/2, assim temos: 2 * T(n/2)
– Combinar: O procedimento de merge ou intercalação trabalha 
sobre  um  subvetor  dos  n  elementos  originais,  mas  ainda 
assim é da ordem de Θ(n), ou seja, C(n) = Θ(n)
   
Análise de Recorrência
● Para o Mergesort:
● Assim a equação de recorrência:
● Torna­se:
● Ou simplificando:
   
Análise de Recorrência
● Para o Mergesort:
● Encontramos a equação de recorrência:
● Mas poderíamos ser mais exatos e obter:
● Pois  devemos  tratar  somente  para  o  caso  de  n  ser  inteiro  e 
podemos ser mais exatos com os arredondamentos
● Bem,  isso  não é  necessário,  costuma­se  usar  a  primeira  forma, 
pois  ela aproxima bem o problema, apesar de n não ser  inteiro, 
mas sim um número real
   
Análise de Recorrência: Método da Substituição
● Resolvendo  a  equação  de  recorrência  a  seguir  pelo  método  da 
substituição:
● Devemos:
● “Chutar”  uma  possível  função  que  defina  a  ordem  de 
complexidade de tempo do algoritmo
● Avaliar se essa função é válida
● Problema:
● Esse “chute” nem sempre é tão simples!
   
Análise de Recorrência: Método da Substituição
● Resolvendo  a  equação  de  recorrência  a  seguir  pelo  método  da 
substituição:
● Chutemos:
● T(n) = O(n log
2
 n)
● Para verificarmos, substituímos em T(n), a fim de provar que:
T(n) <= c n log
2
 n, para alguma constante c > 0
   
Análise de Recorrência: Método da Substituição
● Resolvendo  a  equação  de  recorrência  a  seguir  pelo  método  da 
substituição:
● Qual o valor da constante c para que a prova feita seja válida?
● Podemos provar por indução:
● Isso significa provar para n e para n+1
● Por exemplo, façamos para n=2 e n+1=3
   
Análise de Recorrência: Método da Substituição
● Resolvendo  a  equação  de  recorrência  a  seguir  pelo  método  da 
substituição:
● Prova por indução:
● Para n=2 temos:
T(2) = 2 * T(1) + 2 = 2 * 1 + 2 = 4
● Para  n+1=3  temos  (observe  que  para  a  indução  abordamos 
usando somente inteiros):
T(3) = 2 * T(⌊3/2⌋) + 3 = 2 * T(1) + 3 = 5
   
Análise de Recorrência: Método da Substituição
● Resolvendo  a  equação  de  recorrência  a  seguir  pelo  método  da 
substituição:
● Prova por indução:
● Sabendo que T(2) = 4 e T(3) = 5
● Precisamos  encontrar  uma  constante  c  para  que  as 
desigualdades sejam válidas:
● Resolvendo,  podemos  observar  que  O(n  log
2