Embed Size (px)
Citation preview
Algoritmos de Ordenação
Introdução à Ciência da Computação
Prof. Edison Ishikawa
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Objetivo
• Apresentar diferentes algoritmos
de ordenação de dados
• Mostrar como analisar os
algoritmos em termos de tempo de
execução
• Apresentar as diferentes
abordagens para projetar
algoritmos
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Introdução
• Computadores são muitas vezes usados para
colocar listas em algum tipo de ordem:
• Nomes em ordem alfabética
• E-mails pela data
• Itens em ordem numérica
• Classificar listas permite:
• Encontrar coisas rapidamente
• Facilita identificar os extremos
• Exemplo: Classificar notas de uma prova
• Nota mais baixa e alta se tornam evidentes
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Introdução
•Se você usar o algoritmo
errado, pode demorar muito
tempo para ordenar uma lista
grande, mesmo em um
computador rápido
•Para nossa sorte, vários
algoritmos de ordenação são
conhecidos
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Restrição do Computador
• O computador só consegue comparar
coisas dois a dois
• Para facilitar o nosso entendimento
dos algoritmos vamos ordenar uma
lista pelo peso de seus itens
• E para saber qual é o mais leve ou
mais pesado . . .
• Usaremos uma balança
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Vamos utilizar a seguinte
instância de entrada
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
• Cada bola tem um peso diferente
• Só pegando para saber a diferença
• Para ordenar pelo peso usaremos uma balança
Vamos utilizar a seguinte
instância de entrada
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Como não temos uma balança real,
os pesos das bolas estão pintadas na bola,
mas para todos os efeitos,
não sabemos quanto pesa cada bola . . .
Algoritmo da Bolha
•Vamos começar com um
algoritmo intuitivo
• Imagine que os itens são
bolhas com diferentes pesos
•Os mais leves vão para cima
•No final a lista fica ordenada
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Algoritmo BubleSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
F
A
Ç
O
O
M
A
I
S
L
E
V
E
S
U
B
I
R
Pego os dois primeiros
Já estão relativamente ordenados
Movo a janela uma posição para cima
Algoritmo BubleSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
F
A
Ç
O
O
M
A
I
S
L
E
V
E
S
U
B
I
R
3 é mais leve que seis
Troco a ordem
Algoritmo BubleSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Movo a janela
Troco
Algoritmo BubleSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Movo a janela
Como estão relativamente
ordenados, mantenho!
Algoritmo BubleSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Movo a janela
e troco
Algoritmo BubleSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Subo a janela
e troco
Algoritmo BubleSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Subo a janela
e troco
Algoritmo BubleSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Ainda não está ordenado!
Começo tudo de novo
Algoritmo BubleSort
• Na primeira
passada fiz n
comparações
• Para estar
ordenado terei
que fazer n
passadas
• Ou seja, no total
farei n2
comparações
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Mas como projetar algoritmos
melhores?
• Vamos ver algumas estratégias . . .
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Dado o problema de ordenação,
como projetar o algoritmo? • Estratégia - Definição
• Passos intermediários que se pretende dar para atingir um
objetivo em determinado período de tempo
• Entrada: sequência de números qualquer
• passos intermediários
• Saída: Objetivo = sequência de números ordenada de
forma crescente
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Estratégia da Força Bruta
• Não sei ordenar o vetor
• Testo todas as permutações
possíveis até chegar a uma que
satisfaça:
a’1 ≤ a’2 ≤ ... ≤ a’n
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Estratégia da Força Bruta
• Passo 1 - Enumero as permutações
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Estratégia da Força Bruta
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Passo 2 –
Testo as permutações até que,
pegando cada bola em sequência,
dois a dois,
o anterior seja sempre mais leve
Estratégia da Força Bruta
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Anterior mais pesado que posterior?
Permutação não ordenada
SIM
Passo 2 - Testo as permutações até que,
pegando cada bola em sequência, dois a dois,
o anterior seja sempre mais leve
Estratégia da Força Bruta
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Passo 2 - Testo as permutações até que,
pegando cada bola em sequência, dois a dois,
o anterior seja sempre mais leve
Anterior mais pesado que posterior?
Permutação não ordenada
SIM
Estratégia da Força Bruta
• Tenho que testar todas as permutações
• São Pn = n! permutações
• Cada permutação tem n elementos
• Logo o algoritmo terá que executar n. n!
passos
• Tem como melhorar este algoritmo?
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Estratégia Branch and Bound
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Estratégia Branch and Bound
• Aparentemente melhorou
• Mas existem instâncias, denominadas de
pior caso, em que o número de passos do
algoritmo de ordenação branch-and-bound é
da mesma ordem de grandeza do algoritmo
de força bruta...
• Definitivamente, para este tipo de problema,
este caminho não está levando a bons
resultados
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Estratégia Incremental
• Começo com um vetor de tamanho 1
• como já está ordenado, posso começar pelo
próximo passo
• Aumento o tamanho para 2
• O segundo elemento não necessariamente
está ordenado, então percorro o vetor e insiro
este elemento na sua posição
• Aumento o tamanho para 3
• O terceiro elemento não necessariamente
está ordenado, então percorro o vetor e insiro
este elemento na sua posição
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Ordenação por Inserção
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Algoritmo insertionSort
def insertionSort(lista):
for i in range(1, len(lista)):
daVez = lista[i]
k = i
while k>0 and daVez < lista[k-1]:
lista[k] = lista[k-1]
k = k - 1
lista[k] = daVez
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Algoritmo insertionSort
• Note que neste algoritmo temos dois loops
aninhados
• para i = 2 ... n faça
• enquanto j ≥ 1 e valor < v[j] faça
• Cada um dá n passos
• Logo no total teremos aproximadamente
• n.n = n2 passos
• Melhorou,
• mas o BubbleSort também é da ordem de n2
passos
• Será que estamos indo na direção correta... ?
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Estratégia Dividir para Conquistar
• Esta estratégia envolve 3 passos a cada
nível da recursão:
• Divida o problema em um número de
subproblemas.
• Conquiste os subproblemas resolvendo-os
recursivamente. Se, entretanto, o tamanho
do subproblema é suficientemente
pequeno, resolva o problema de maneira
direta.
• Combine as soluções dos subproblemas
na solução do problema original
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
[Cormen89]
Estratégia Dividir para Conquistar
• Algoritmo MergeSort
• Divida a sequência de n elementos a
serem ordenados em duas
subsequências de n/2 elementos.
• Conquiste ordenando as
subsequências recursivamente usando
MergeSort
• Combine intercalando (merge) as duas
subsequências para produzir o vetor
ordenado
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
MergeSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
D
I
V
I
D
I
R
MergeSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
C
O
N
Q
U
I
S
T
A
R
Algoritmo MergeSort
def intercala(esquerda, direita):
final = [ ]
while esquerda or direita:
if len(esquerda) and len(direita):
if esquerda[0] < direita[0]:
final.append(esquerda.pop(0))
else:
final.append(direita.pop(0))
if not len(esquerda):
if len(direita):
final.append(direita.pop(0))
if not len(direita):
if len(esquerda):
final.append(esquerda.pop(0))
return final
def mergeSort(lista):
if len(lista) < 2:
return lista
meio = len(lista) // 2
return intercala(mergeSort(lista[:meio]),
mergeSort(lista[meio:]))
l = [7,4,2,1,5,6,3,8]
l=mergeSort(l)
print(l)
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Algoritmo MergeSort
• O tempo de execução T(n) do MergeSort é o resultado da soma dos tempos de execução das duas chamadas recursivas, cada uma delas com tempo de execução T(n/2).
• Como condição inicial, para n=1, T(1)=1, e assumindo que n é uma potência de 2, a fórmula básica que expressa o número de iterações é:
• T(n) = 2T(n/2) + n
• Dividindo por n
• T(n)/n = T(n/2)/(n/2) + 1
• Como a equação é válida para qualquer potência de 2..
• T(n/2) /(n/2)= T(n/4)/(n/4) +1
• T(n/4)/(n/4) = T(n/8)/(n/8) +1
• .
• .
• .
• T(n/n)/(n/n) = T(1) /1 + 1
• Somando tudo, conclui-se que
• T(n) = n + n log2 n
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Estratégia Dividir para Conquistar
•Uma mesma estratégia
pode ser usada de formas
diferentes
•Vamos ver como o algoritmo
QuickSort usa esta mesma
estratégia
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Algoritmo QuickSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Escolho um objeto de forma aleatória.
Algoritmo QuickSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Escolho um objeto de forma aleatória.
Coloco os mais leves na direita e os mais pesados a esquerda.
Repito o procedimento para o grupo da esquerda e da direita
Algoritmo QuickSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Repita até que nenhum grupo tenha mais do que um objeto
Algoritmo QuickSort
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
E a lista está ordenada!!!
Algoritmo QuickSort
• Você achou que o quicksort é eficiente?
• Depende, se o pivot for escolhido
adequadamente (o peso médio do grupo). . .
• No entanto, se o quickSort escolher sempre
o peso mais leve...
• A quantidade de comparações têm a mesma
ordem de grandeza do que o algoritmo
insertionSort (n2)
• No melhor caso e no caso médio a
complexidade é n.log2n
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Considerações Finais
• Existe uma melhor estratégia?
• Depende do problema
• Depende da estrutura de dados utilizada
• Existem algoritmos que foram projetados
sem a utilização de estratégias e que são
muito bons
• É ciência, envolve pesquisa e técnica, mas
também é arte, envolve imaginação e
criatividade
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
O que é um bom algoritmo?
• Um bom algoritmo é como uma faca afiada:
faz exatamente o que ela tem que fazer com
o mínimo de esforço.
• Usar o algoritmo errado para resolver um
problema é como tentar fatiar um filé de
peixe com uma chave de fenda.
• Eventualmente se consegue algo digerível,
mas o esforço gasto será maior que o
necessário, e o resultado não será
esteticamente agradável. . .
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
[Cormen89]
O que é um bom algoritmo?
• Algoritmos projetados para resolver o
mesmo problema frequentemente são muito
diferentes em se tratando de eficiência.
• Esta diferenças podem ser mais
significativas do que a diferença entre um
PC e um supercomputador.
• Exemplo: vamos comparar um
supercomputador usando insertionSort e um
PC usando mergeSort. A tarefa é a mesma
para os dois. Ordenar um vetor com 1
milhão de números.
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
[Cormen89]
O que é um bom algoritmo?
• O supercomputador executa 100
milhões de instruções por segundo
• O PC executa 1 milhão de instruções
por segundo
• O insertionSort para ordenar n
números tem que executar 2n2
instruções.
• O mergeSort para ordenar n números
tem que executar 50n log n instruções.
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
[Cormen89]
O que é um bom algoritmo?
• Calculando o tempo de execução...
• O supercomputador com insertionSort
leva: 2.(106)2 instruções = 20.000 segundos = 5,56 horas
108 instruções/segundo
• O PC com mergeSort leva: 50 x 106 log 106 instruções = 1.000 segundos = 16,67 min
106 instruções/segundo Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
[Cormen89]
Resumindo • A comparação do exemplo entre
InsertionSort/Supercomputador e
MergeSort/PC mostra que os algoritmos,
como o hardware do computador, são
tecnologia!
• O desempenho total do sistema depende de
um algoritmo bem projetado tanto quanto da
escolha do hardware mais rápido.
• Assim como o hardware avança
rapidamente na tecnologia, os avanços nos
algoritmos não ficam para trás.
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
[Cormen89]
De que se trata tudo isso?
• É muito mais fácil encontrar uma informação
em uma lista ordenada
• Lista telefônica, dicionários e índices de
livros utilizam ordem alfabética
• Em uma lista de números ordenada, os
pontos extremos são fáceis de ver porque
eles estão no começo e no fim da lista
• Também é fácil de encontrar itens repetidos,
eles ficam juntos
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
De que se trata tudo isso?
• Computadores gastam muito tempo ordenando as
coisas
• Portanto os cientistas da computação devem
descobrir algoritmos rápidos e eficientes para fazer
isto
• Alguns algoritmos mais lentos podem ser úteis em
situações especiais, porém os métodos mais
rápidos, como o quicksort, são geralmente
utilizados
• Existem várias estratégias para fazer algoritmos. No
caso da ordenação, a estratégia dividir para
conquistar, quicksort, deu um dos melhores
resultado
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Dúvidas
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Curiosidade 1
• Existe algum algoritmo de
ordenação pior que o Força Bruta?
• Lema:
• para o pior não há limites ;-(
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
BOGOSORT
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
BOGOSORT
• Quantos passo será que ele leva para
chegar ao resultado final?
• O que é mais fácil, ordenar um vetor
grande com BOGOSORT ou ganhar na
megasena?
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Curiosidade 2
• Existe um algoritmo que ordena um vetor em O(n)
• É o BucketSort
• No entanto o espaço usado pode ser proibitivo
• Exemplo:
• Inteiros de 32 bits, vou precisar de 2n
baldes, não importa
de se são 10 ou um milhão de números
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
Referências
• Thomas M. Cormen et all. Introduction to algorithms. The
Mit Press, 1990.
• Jayme L. Szwarcfiter e Lilian Markenzon. Estrutura de
Dados e seus Algortimos. LTC editora, 2012.
Dep
art
am
en
to d
e C
iên
cia
da C
om
pu
tação
