Algoritmos de Ordenação

Prévia do material em texto

Ordenação 
 
Prof. Túlio A. M. Toffolo 
Prof. Marco Antonio M. Carvalho 
http://www.toffolo.com.br 
BCC402 – Aula 04 
 
Algoritmos e Programação Avançada 
Aplicações 
•  Como testar se todos os elementos de um 
conjunto S são únicos? 
1.  Ordene o conjunto – O(n log n) 
2.  Percorra o conjunto uma única vez buscando por 
repetições entre os elementos adjancentes O(n) 
2 
Aplicações 
•  Remover duplicações de um elemento 
1.  Ordene o conjunto – O(n log n) 
2.  Encontre o elemento no vetor – O(log n) 
3.  Para cada repetição adjacente, troque o elemento 
com o último do vetor (utilize um índice para indicar 
o final) 
3 
Aplicações 
•  Remover todas as duplicações de um vetor 
1.  Ordene o conjunto – O(n log n) 
2.  Teste cada item i com i+1. Em caso de repetição, 
remova-o. – O(n) 
3.  Uma estrutura auxiliar pode facilitar as operações. 
4 
Aplicações 
•  Priorizar elementos 
•  Suponha que seja dado um conjunto de tarefas, cada 
uma com um deadline específico. 
•  Ordenamos as tarefas de acordo com sua prioridade. 
•  Ordenar é uma forma de implementar uma fila de 
prioridade. 
5 
Aplicações 
•  Encontrar o k-ésimo maior item de um conjunto. 
1.  Ordene o conjunto – O(n log n) 
2.  Retorne o k-ésimo elemento vetor – O(1) 
•  Encontrar a mediana de um conjuntos 
1.  Se o tamanho n for ímpar, basta encontrar o 
(n/2)-ésimo maior elemento do vetor. 
2.  Se n for par, basta retorna a média do (n/2)-ésimo e 
do (n/2+1)-ésimo maiores elementos do vetor. 
6 
Aplicações 
•  Contar frequências 
•  Por exemplo: qual o item que mais ocorre em um vetor? 
•  Ordenamos o vetor – O(n log n). 
•  Em seguida, basta percorrer o vetor e contar as 
ocorrências adjacentes – O(n). 
7 
Aplicações 
•  Reconstruir a ordem original de um vetor 
•  Como restaurar a ordem original de um vetor após uma 
série de permutação. 
1.  Adicione um item extra no registro (indicando a 
posição original) – O(n). 
2.  Ordene de acordo com este item – O(n log n) 
8 
Aplicações 
•  Interseção e união de conjuntos 
•  Se ambos conjuntos estiverem ordenados, podemos 
fazer em O(n). 
•  Basta percorrer os vetores pegando sempre o menor 
item de cada vetor e colocá-lo no conjunto. 
9 
Aplicações 
•  Busca eficiente 
•  Vetores ordenados podem ser pesquisados em tempo 
O(log n) através de busca binária. 
•  Para um dado número z, encontrar dois elementos x 
e y em que x + y = z. 
•  Se os vetores estiverem ordenados, basta testar 
extremos (dois índices i e j), incrementando i e 
reduzindo j de acordo com os resultados. 
•  Custo: O(n) 
10 
Complexidade assintótica 
•  Algoritmos de ordenação por comparação 
•  Quicksort – O(n2); O(n log n) no caso médio 
•  Heapsort – O(n log n) 
•  MergeSort – O(n log n) 
•  Shellsort – O(n2) limite forte desconhecido :) 
•  InsertSort – O(n2) 
•  SelectSort – O(n2) 
•  Bubblesort – O(n2) 
11 
Ordenação estável e não-estável 
•  Ordenação estável: 
•  A ordem dos elementos em que há empate é 
preservada. 
•  Ordenação não-estável: 
•  Não há garantia de que a ordem os elementos de 
empate será preservada. 
12 
Ordenação estável e não-estável 
•  Algoritmos de ordenação estáveis: 
•  MergeSort – O(n log n) 
•  InsertSort – O(n2) 
•  Bubblesort – O(n2) 
•  Algoritmos ordenação não-estáveis: 
•  Quicksort – O(n2); O(n log n) no caso médio 
•  Heapsort – O(n log n) 
•  Shellsort – O(n2) limite forte desconhecido :) 
•  SelectSort – O(n2) 
 13 
 
Maratona de Programação: 
Quais algoritmos utilizar? 
MergeSort 
•  Método estável. 
•  Custo O(n log n). 
•  Disponível na STL: função stable_sort 
•  Exemplos: 
15 
MergeSort (STL) 
16 
#include <iostream>	
#include <algorithm>	
#include <vector>	
	
using namespace std;	
	
int main () {	
 double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73};	
	
 vector<double> myvector(mydoubles,mydoubles+5);	
 stable_sort (myvector.begin(), myvector.end());	
	
 for (it=myvector.begin(); it!=myvector.end(); ++it)	
 cout << " " << *it;	
 cout << endl;	
	
 return 0;	
}	
	
QuickSort 
•  Algoritmo mais rápido para entradas maiores. 
•  Método não é estável. 
•  Método qsort da stdlib: 
17 
#include <stdlib.h>	
	
int main() {	
 ...	
 qsort(vetor, n, sizeof(int), &comparador);	
}	
	
int comparador(const void *a, const void *b) {	
 if (*(int*)a < *(int*)b) return -1;	
 if (*(int*)a > *(int*)b) return 1;	
 return 0;	
}	
QuickSort (STL) 
18 
#include <iostream>	
#include <algorithm>	
#include <vector>	
	
using namespace std;	
	
int main () {	
 double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73};	
	
 vector<double> myvector(mydoubles,mydoubles+5);	
 sort (myvector.begin(), myvector.end());	
	
 for (it=myvector.begin(); it!=myvector.end(); ++it)	
 cout << " " << *it;	
 cout << endl;	
	
 return 0;	
}	
QuickSort (ordenação personalizada) 
19 
#include <iostream>	
#include <algorithm>	
#include <vector>	
	
using namespace std;	
	
bool compare_as_ints (double i, double j) {	
 return (int(i)<int(j));	
}	
	
int main () {	
 double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73};	
	
 vector<double> myvector(mydoubles,mydoubles+5);	
 sort (myvector.begin(), myvector.end(), compare_as_ints);	
	
 for (it=myvector.begin(); it!=myvector.end(); ++it)	
 cout << " " << *it;	
 cout << endl;	
	
 return 0;	
}	
QuickSort (ordenação multi-critério) 
20 
typedef struct {	
 int nro_problemas;	
 int penalty;	
 char[50] equipe;	
} Equipe;	
	
bool equipe_compare(Equipe &a, Equipe &b) {	
 if (a.nro_problemas < b.nro_problemas)	
 return true;	
 else if (b.nro_problemas < a.nro_problemas)	
 return false;	
 else if (a.penalty < b.penalty)	
 return true;	
 return false;	
}	
Busca em vetores ordenados 
•  Método bsearch da stdlib: 
21 
#include <stdlib.h>	
	
int comparador(const void *a, const void *b) {	
 if (*(int*)a < *(int*)b) return -1;	
 if (*(int*)a > *(int*)b) return 1;	
 return 0;	
}	
	
int main() {	
 int vetor[] = { 1,3,15,50 };	
 int n = 4;	
 int k = 15;	
 int *p = bsearch(&k, vetor, n, sizeof(int), &comparador);	
 // (*p) será igual ao elemento	
}	
Busca em vetores ordenados 
•  Método binary_search da STL: 
•  Retorna true ou false… Pouco útil em alguns casos… 
22 
int main() {	
 int vetor[] = { 1, 3, 15, 50 };	
 vector<int> v(vetor, vetor+4);	
	
 if (binary_search (v.begin(), v.end(), 3))	
 cout << "found!\n"; 	
 else 	
 cout << "not found.\n";	
}	
	
Busca em vetores ordenados 
•  STL: lower_bound, upper_bound e equal_range 
•  Fazem busca binária e retornam iteradores. Uso varia em 
caso de haver mais de um elemento com a mesma 
chave: 
•  lower_bound: retorna o primeiro elemento 
•  equal_range: retorna um pair contendo a primeira e a 
última ocorrência do elemento 
•  upper_bound: retorna o última elemento 
23 
Busca em vetores ordenados 
24 
#include <iostream>	
#include <algorithm>	
#include <vector>	
using namespace std;	
	
int main () {	
 int myints[] = {10,20,30,30,20,10,10,20};	
 vector<int> v(myints,myints+8); // 10 20 30 30 20 10 10 20	
 vector<int>::iterator low,up;	
	
 sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30	
	
 low=lower_bound (v.begin(), v.end(), 20);	
 up= upper_bound (v.begin(), v.end(), 20);	
	
 cout << "lower_bound at position " << int(low - v.begin()) << endl;	
 cout << "upper_bound at position " << int(up - v.begin()) << endl;	
	
 return 0;	
}	
 
 
Ordenação em tempo linear 
Ordenação em tempo linear 
•  Algoritmos de ordenação por comparação: 
•  Insertion Sort (Método de Inserção); 
•  Quicksort; 
•  Merge Sort (Ordenação por Intercalação); 
•  Heapsort... 
•  Possuem limite assintótico superior: O(n lg n); 
•  Devem efetuar pelo menos Ω(n lg n) comparações no 
pior caso; 
•  Podem existir algoritmos melhores? 
26 
Ordenação em tempo linear 
•  A resposta é SIM, desde que: 
•  A entrada possua características especiais;•  Algumas restrições sejam respeitadas; 
•  O algoritmo não seja puramente baseado em comparações; 
•  A implementação seja feita da maneira adequada. 
•  Tempo linear: Θ(n); 
•  Algoritmos: 
•  Ordenação por contagem (Counting sort); 
•  Radix sort; 
•  Bucket sort. 
27 
Ordenação por contagem 
•  Pressupõe que cada elemento da entrada é um inteiro 
na faixa de 0 a k, para algum inteiro k; 
•  Idéia básica: 
•  Determinar para cada elemento da entrada x o 
número de elementos maiores que x; 
•  Com esta informação, determinar a posição de cada 
elemento 
•  Ex.: Se 17 elementos forem menores que x então x ocupa a 
posição de saída 18. 
28 
Ordenação por contagem 
•  Algoritmo: 
•  Assumimos que o vetor de entrada é A[1,...,n]; 
•  Outros dois vetores são utilizados: 
•  B[1,...,n] – armazena a saída ordenada; 
•  C[1,...,k] – é utilizado para armazenamento 
temporário. 
29 
Ordenação por contagem 
1 for i ← 0 to k 
2 do C[i] ← 0 
3 for j ← 1 to length[A] 
4 do C[A[j]] ← C[A[j]] + 1 
5 for i ← 1 to k 
6 do C[i] ← C[i] + C[i −1] 
7 for j ← length[A] down to 1 
8 do B[C[A[j]]] ← A[j] 
9 C[A[j]] ← C[A[j]] −1 
30 
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
A	
   2	
   5	
   3	
   0	
   2	
   3	
   0	
   3	
  
k	
  =	
  5	
  
0	
   1	
   2	
   3	
   4	
   5	
  
C	
  
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
B	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
  
Ordenação por contagem 
1 for i ← 0 to k 
2 do C[i] ← 0 
3 for j ← 1 to length[A] 
4 do C[A[j]] ← C[A[j]] + 1 
5 for i ← 1 to k 
6 do C[i] ← C[i] + C[i −1] 
7 for j ← length[A] down to 1 
8 do B[C[A[j]]] ← A[j] 
9 C[A[j]] ← C[A[j]] −1 
31 
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
A	
   2	
   5	
   3	
   0	
   2	
   3	
   0	
   3	
  
k	
  =	
  5	
  
0	
   1	
   2	
   3	
   4	
   5	
  
C	
   0	
   0	
   0	
   0	
   0	
   0	
  
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
B	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
  
Ordenação por contagem 
1 for i ← 0 to k 
2 do C[i] ← 0 
3 for j ← 1 to length[A] 
4 do C[A[j]] ← C[A[j]] + 1 
5 for i ← 2 to k 
6 do C[i] ← C[i] + C[i −1] 
7 for j ← length[A] down to 1 
8 do B[C[A[j]]] ← A[j] 
9 C[A[j]] ← C[A[j]] −1 
32 
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
A	
   2	
   5	
   3	
   0	
   2	
   3	
   0	
   3	
  
k	
  =	
  5	
  
0	
   1	
   2	
   3	
   4	
   5	
  
C	
   2	
   0	
   2	
   3	
   0	
   1	
  
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
B	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
  
Ordenação por contagem 
1 for i ← 0 to k 
2 do C[i] ← 0 
3 for j ← 1 to length[A] 
4 do C[A[j]] ← C[A[j]] + 1 
5 for i ← 1 to k 
6 do C[i] ← C[i] + C[i −1] 
7 for j ← length[A] downto 1 
8 do B[C[A[j]]] ← A[j] 
9 C[A[j]] ← C[A[j]] −1 
33 
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
A	
   2	
   5	
   3	
   0	
   2	
   3	
   0	
   3	
  
k	
  =	
  5	
  
0	
   1	
   2	
   3	
   4	
   5	
  
C	
   2	
   2	
   4	
   7	
   7	
   8	
  
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
B	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
   	
  	
  
Ordenação por contagem 
1 for i ← 0 to k 
2 do C[i] ← 0 
3 for j ← 1 to length[A] 
4 do C[A[j]] ← C[A[j]] + 1 
5 for i ← 1 to k 
6 do C[i] ← C[i] + C[i −1] 
7 for j ← length[A] down to 1 
8 do B[C[A[j]]] ← A[j] 
9 C[A[j]] ← C[A[j]] −1 
34 
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
A	
   2	
   5	
   3	
   0	
   2	
   3	
   0	
   3	
  
k	
  =	
  5	
  
0	
   1	
   2	
   3	
   4	
   5	
  
C	
   0	
   2	
   2	
   4	
   7	
   7	
  
1	
   2	
   3	
   4	
   5	
   6	
   7	
   8	
  
B	
   0	
   0	
   2	
   2	
   3	
   3	
   3	
   5	
  
Ordenação por contagem 
•  O tempo de execução é dado em função do valor de k; 
•  Roda em tempo Θ(n + k); 
•  Se tivermos k = O(n), então o algoritmo executa em 
tempo Θ(n); 
•  Exemplo prático de uso: vídeo locadora 
35 
36 
Radix Sort 
•  Pressupõe que as chaves de entrada possuem limite no 
valor e no tamanho (quantidade de dígitos); 
•  Ordena em função dos dígitos (um de cada vez): 
•  A partir do mais significativo; 
•  Ou a partir do menos significativo? 
•  É essencial utilizar um segundo algoritmo estável para 
realizar a ordenação de cada dígito. 
37 
•  A partir dos dígitos menos significativos: 
3 2 9
4 5 7
6 5 7
8 3 9
4 3 6
7 2 0
3 5 5
Radix Sort – Funcionamento 
38 
•  A partir dos dígitos menos significativos: 
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
Radix Sort – Funcionamento 
39 
•  A partir dos dígitos menos significativos: 
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
Radix Sort – Funcionamento 
40 
•  A partir dos dígitos menos significativos: 
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
Radix Sort – Funcionamento 
41 
•  A partir dos dígitos menos significativos: 
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
Radix Sort – Funcionamento 
42 
•  A partir dos dígitos menos significativos: 
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
Radix Sort – Funcionamento 
43 
•  A partir dos dígitos menos significativos: 
Como ficaria a partir o dígito mais significativo? 
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
Radix Sort – Funcionamento 
44 
•  A partir dos dígitos menos significativos: 
E se a ordenação não fosse estável? 
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
Radix Sort – Funcionamento 
45 
Radix Sort – Pseudo Código 
•  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; 
•  O código, portanto, é muito simples: 
1 for i ← 1 to d 
2 do utilize um algoritmo estável para ordenar o 
 array A pelo i-ésimo dígito 
 
•  Onde: 
•  d é número de dígitos; 
•  A é o array de entrada. 
46 
Bucket Sort 
•  Assume que a entrada é gerada por um processo 
aleatório que distribui os elementos de forma uniforme 
sobre o intervalo [0,1); 
•  A idéia do Bucket Sort é dividir o intervalo [0,1) em n 
subintervalos de mesmo tamanho (baldes), e então 
distribuir os n números nos baldes; 
•  Uma vez que as entradas são uniformemente distribuídas 
não se espera que muitos números caiam em cada balde; 
47 
Bucket Sort 
•  Para produzir a saída ordenada, basta ordenar os 
números em cada balde, e depois examinar os baldes 
em ordem, listando seus elementos; 
•  A função para determinação do índice do balde correto 
é ; 
•  Vamos a um exemplo com 10 números 
•  A é o array de entrada; 
•  B é o array com os baldes. 
⎣ ⎦][iAn×
48 
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 
49 
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 / 
50 
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 / 
51 
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 / 
52 
Bucket Sort – Funcionamento 
0,78 0,17 0,39 0,260,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 / 
53 
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 / 
54 
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 / 
55 
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 / 
56 
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 / 
57 
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 
58 
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 / 
59 
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 / 
Ordenação em tempo linear 
•  Foram vistos três algoritmos de ordenação linear (tempo 
Θ(n)). Que são então melhores que os algoritmos de 
ordenação por comparação (tempo O(n lg n)); 
 ????? 
•  Entretanto, nem sempre é interessante utilizar um 
destes três algoritmos: 
•  Todos eles pressupõem algo sobre os dados de 
entrada a serem ordenados. 
60 
 
 
 
Perguntas?