5COP096 – Teoria da Computação
Aula 7 – Ordenação
5COP096
Teoria da Computação
Aula 7
Prof. Dr. Sylvio Barbon Junior
Sylvio Barbon Jr – [email protected]
1
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Sumário
1) Ordenação
2) Ordenação Interna
3) Ordenação Externa
Sylvio Barbon Jr – [email protected]
2
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação
-
A ordenação é um dos bons exemplos da resolução de problemas
utilizando computador.
A maioria dos métodos de ordenação é baseada em:
- Distribuição (Ordenação Digital, Radixsort ou Bucketsort): Não existe
comparação entre chaves, sendo o principal problema associado a
memória, uma vez que cada grupo exige memória extra.
Exemplos: ordenar Cartas de Baralho, classificar cartões perfurados,
distribuição de correspondências por bairro/rua etc.
O custo para ordenar elementos é da ordem de O(n), pois cada
elemento é manipulado algumas vezes.
-
Comparação (maioria dos métodos): Utilizam normalmente uma
chave e serão estudados detalhadamente.
Sylvio Barbon Jr – [email protected]
3
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação
Exemplo de Ordenação por Distribuição
Sylvio Barbon Jr – [email protected]
4
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação
Exemplo de Ordenação por Distribuição
Sylvio Barbon Jr – [email protected]
5
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação
-
Um método de ordenação é dito estável, se a ordem relativa dos itens com chaves
iguais mantém-se inalterada pelo processo de ordenação.
Exemplo: Se uma lista alfabética de nomes de funcionários de uma empresa é
ordenada pelo campo salário, então um método estável produz uma lista em que
os funcionários com mesmo salário aparecem em ordem alfabética
Sylvio Barbon Jr – [email protected]
6
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação
-
-
Os métodos de ordenação são classificados em dois grupos:
-
Ordenação Interna:
Quando o arquivo a ser ordenado cabe todo na memória principal.
Exemplo: Quando o número de registros a ser ordenado é pequeno o
bastante para caber em um array de Java.
-
Ordenação Externa:
Quando o arquivo não cabe na memória principal, e por isso deve ser
armazenado em outros dispositivos, por exemplos fitas ou discos.
A principal diferença seria a necessidade de lidar com os
registros de forma sequencial para o caso de Ordenação
Externa.
Sylvio Barbon Jr – [email protected]
7
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
-
Trata principalmente o tempo gasto comparando as chaves e
movimentações de itens avaliados, assim vamos utilizar a
seguinte notação:
C(n) – Comparações entre as chaves;
M(n) – Movimentações entre os itens;
n – Quantidade de itens.
-
Algoritmos is situ (in place) são métodos que utilizam
permutações entre os itens do próprio vetor, não precisando
de memória extra.
Sylvio Barbon Jr – [email protected]
8
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Distribuição
Ordenação
Comparação
Interna
Método Simples
Externa
Método Eficientes
Sylvio Barbon Jr – [email protected]
9
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Os métodos internos são classificados em:
- Métodos Simples, são adequados para pequenos arquivos e requerem O(n²)
comparações, são programas pequenos, fáceis de entender com simplicidade
nos seus princípios.
- Métodos Eficientes, são aqueles para arquivos maiores e requerem O(n log n)
comparações, comparações complexas como a implementação.
Considerando Ordenação Interna, serão estudados:
1) Ordenação por Seleção (Selectionsort);
2) Ordenação por Inserção (Insertionsort);
3) Shellsort;
4) Quicksort;
5) Heapsort;
Sylvio Barbon Jr – [email protected]
10
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Selectionsort (Ordenação por Seleção)
- É um dos métodos mais simples;
C(n) = n²/2 – n/2
M(n) = 3(n-1)
Aspectos negativos:
- O fato do arquivo estar ordenado não
auxilia em nada;
- O algoritmo não é estável, pois ele nem
sempre mantém os registros com chaves iguais na
mesma posição relativa.
Sylvio Barbon Jr – [email protected]
11
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Insertionsort (Ordenação por Inserção)
- A partir de i=2, o i-ésimo item da sequência é
transferido para a sequência de destino, sendo inserido no
local correto. Os itens maiores são movidos para a direita e
inserido o item na posição vazia deixada.
- O método é estável.
- Registro sentinela marca o registro avaliado.
Melhor Caso
C(n) = n-1
M(n) = 3(n-1)
Caso Médio
C(n) = n²/4+3n/4-1
M(n) = n²/4+11n/4-3
Pior Caso
C(n) = n²/2+n/2-1
M(n) = n²/2+5n/2-3
-O número mínimo ocorre quando os itens já estão organizados;
-O número máximo de comparações ocorrem quando o arquivo
está na ordem inversa.
Sylvio Barbon Jr – [email protected]
12
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Shellsort
- Foi proposto em 1959 como uma extensão do algoritmo de ordenação
por inserção, contornando as trocas separados por h posições.
- O método não é estável.
- A sua análise contém problemas matemáticos complexos, e uma analise
formalizada ainda não foi realizada.
C(n) = O(n(ln n)²)
- O tempo de execução é sensível à ordem inicial.
Sylvio Barbon Jr – [email protected]
13
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Shellsort vs Insertionsort
Insertionsort: Eficiente quando os itens estão quase ordenados
Shellsort: Opção com separações h
Sylvio Barbon Jr – [email protected]
14
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Quicksort
- Foi publicado em 1962 e é o algoritmo mais rápido e mais utilizado
para ordenação.
- Utiliza um pivô para particionamento e comparação.
- Sua ineficiência aparece quando o arquivo já está ordenado e o pivô
escolhido não é adequado. Porém isso pode ser evitado com pequenos ajustes no
código.
- Os aspectos negativos são: a versão recursiva tem pior caso quadrático
de operações, a implementação é muito delicada e o método não é estável.
Sylvio Barbon Jr – [email protected]
15
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Quicksort
Melhor Caso
C(n) = O(n log n)
Caso Médio
C(n) = O(n log n)
Pior Caso
C(n) = O(n²)
Para evitar o pior caso do algoritmo, recomenda-se utilizar como o item divisor
com valor mais próximo da mediana de três valores quaisquer do arquivo.
Sylvio Barbon Jr – [email protected]
16
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Heapsort
- É semelhante ao Selectionsort, onde são feitas trocas com o primeiro
item da lista.
- O custo n para encontrar o menor item da fila pode ser reduzido
utilizando estruturas de dados como a fila por prioridade.
- Não é estável.
- Não é recomendado para arquivos com poucos registros, devido ao
tempo para construir o heap.
- Em média o Quicksort é duas vezes mais rápido do que o Heapsort.
- Heapsort é melhor que o Shellsort para grandes arquivos.
Melhor Caso
C(n) = O(n log n)
Caso Médio
C(n) = O(n log n)
Pior Caso
C(n) = O(n log n)
17
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Heapsort
- É semelhante ao Selectionsort, onde são feitas trocas com o primeiro
item da lista.
- O custo n para encontrar o menor item da fila pode ser reduzido
utilizando estruturas de dados como a fila por prioridade.
- Não é estável.
- Não é recomendado para arquivos com poucos registros, devido ao
tempo para construir o heap.
- Em média o Quicksort é duas vezes mais rápido do que o Heapsort.
- Heapsort é melhor que o Shellsort para grandes arquivos.
Melhor Caso
C(n) = O(n log n)
Caso Médio
C(n) = O(n log n)
Pior Caso
C(n) = O(n log n)
18
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Heapsort
19
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Comparação entre os métodos
É melhor em diversos
Pior caso para elementos decrescentes tamanhos, comparando os
métodos simples
e mais rápido para elementos
ordenados (O(n))
Métodos Simples
O (n2)
Selectiosort
Mais simples
Mais rápido
Métodos Eficientes
O( n log n)
Shellsort
Analiticamente sem
formalização, mas
considerado eficiente
Insertionsort
São constantes para todos os
tamanhos (heapsort, maislento)
Quicksort
Heapsort
Shellsort é mais rápido que o
Heapsort para listas pequenas.
20
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Interna
Comparação entre os métodos e sua ordem inicial
A vantagem é o número de
movimentos, assim adequado para
arquivos grandes.
Métodos Simples
O (n2)
Selectiosort
Método interessante para
arquivos com menos de 20
elementos
Insertionsort
Sensível à ordenação, mais rápido
quando ordenado.
Métodos Eficientes
O( n log n)
Shellsort
Sensível à ordenação,
executa mais rápido para
elementos ordenados
Quicksort
Heapsort
Não é sensível a ordenação,
porém 10% mais lento quando
estiver ordenado
21
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
-A ordenação externa envolve arquivos compostos por um número de registros
que é maior do que a memória interna do computador pode armazenar.
- Restrição: O registro pode ser acessado somente em um dado momento.
- Diferenças com Ordenação Interna:
1) O custo para acessar o dado é maior do que o custo para processá-lo.
2) Restrições Severas de acesso aos dados, por exemplo, os dados em uma
fita magnética só podem ser acessados sequencialmente. Em um disco
magnético o acesso direto é mais custoso do que o acesso sequêncial.
3) Alta dependência da tecnologia.
22
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
- A grande ênfase deve ser na minimização do número de vezes que cada item é
transferido entre as memórias.
- A maioria dos métodos de Ordenação Externa utilizam a estratégia de:
1) É realizada uma varredura na memória externa, “quebrando-a” em
blocos compatíveis com a memória interna.
2) Os blocos são intercalados, fazendo várias leituras sobre o arquivo,
criando blocos ordenados cada vez maiores.
-
Os métodos que serão estudados são:
- Intercalação Balanceada de Vários Caminhos;
- Seleção por Substituição;
- Intercalação Polifásica;
- Quicksort Externo;
23
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
1- Intercalação Balanceada de Vários Caminhos
-Considerando o seguinte arquivo com 22 registros:
I
N T
E
R
C
A
L
A
C
A
O B
A
L
A
N C
E
A
D
A
- Considerando que a memória externa tem apenas espaço para 3 registros.
I
N T
E
R
C
A
L
A
C
A
O B
A
L
A
N C
E
A
D
A
- Os registros são escritos nas fitas 1, 2 e 3.
Fita 1
I
N T
A
C
O
A
Fita 2
C
E
R
A
B
L
A
Fita 3
A
A
L
A
C
N
D
E
24
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
1- Intercalação Balanceada de Vários Caminhos
- O processo é repetido até formar novos conjuntos inseridos em novas fitas.
Fita 2
Fita 1
I
N T
Fita 4
Fita 3
C
E
R
I
C
A
A
A
L
A
Memória Interna
25
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
1- Intercalação Balanceada de Vários Caminhos
Intercalação 2
Intercalação 1
- Os registros serão intercalados, o primeiro registro de cada fita é transferido
para M.I. e o menor é retirado da fita, dando lugar ao próximo elemento da
mesma.
Fita 1
I
N T
A
C
O
A
Fita 2
C
E
R
A
B
L
A
Fita 3
A
A
L
A
C
N
Fita 4
A A C
E
I
L
N R T
Fita 5
A A A B
C
C
L
Fita 6
A A D E
N O
D
E
A
A
A
Memória Interna
Fita 7
26
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
1- Intercalação Balanceada de Vários Caminhos
- Considere um arquivo contendo n registros, f fitas e uma memória interna de m
palavras. Dessa forma é possível encontrar a Função de Complexidade P, sendo
P(n) o número de intercalações.
P(n) = logf n/m
-No exemplo anterior P(n) = log3 22/3 = 2
- Um arquivo com 1 bilhão de palavras e com uma memória de 2 milhões de
palavras, utilizando quatro fita, obtemos P(n) = 5.
27
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
2- Seleção por Substituição
- É uma implementação semelhante à intercalação balanceada com o acréscimo
de uma abordagem de filas por prioridade, implementadas por um heap.
- Exemplo:
R
A
P
A
Z
E
1
2
3
A
A
R
P
Z
A
R
P
P
R
Z
R
Z
A
A
R
P
Z
Z
28
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
3- Intercalação Polifásica
- Um dos problemas com a Intercalação Balanceada pode ser a necessidade de
utilizar um grande número de fitas para garantir a sua operação.
- O método Intercalação Polifásica elimina a necessidade de cópias adicionais pois
distribui os blocos ordenados por meio de uma seleção desigual.
-Exemplo. Passo 1
I
N T
R
E
C
A
Fita 1
I
N R
T
Fita 2
A A C E N
L
A
C
A
A
C
E
A
A
D
O B
L
L
A
A
N C
E
A
D
A
A A B C L O
29
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
3- Intercalação Polifásica
Passo 2 - Intercala-se para a Fita 3, deixando a Fita 2 livre.
Fita 1
A A B C L
O
A A C E I
N N R T
Fita 2
Fita 3
A A A C
D E
L
Passo 3 - Intercala-se a Fita 1 e Fita 3 na Fita 2, deixando a Fita 1 livre.
Fita 1
Fita 2
A
Fita 3
A A A C
A
A
A
B
C
D E
C
L
E
I
L
N N O R
T
30
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
3- Intercalação Polifásica
Passo 4 - Intercala-se para a Fita 3, deixando a Fita 2 livre.
Fita 1
A
A
A
A
A
A
A
Fita 2
B
C
C
C
D
E
E
I
L
L
N N O R
T
Fita 3
A intercalação polifásica é ligeiramente melhor do que a intercalação balanceada
para valores pequenos de fitas (f), para f > 8 a intercalação balanceada pode ser
mais rápida.
31
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Ordenação Externa
4- Quicksort Externo
-Proposto em 1980, utiliza o paradigma divisão e conquista, sendo a versão in situ
para ordenação de registros.
-O algoritmo utiliza memória interna em O(log n), não sendo necessário memória
externa (além da que armazena os registros).
-A complexidade de melhor caso é O(n/b), sendo b é o tamanho do bloco de
leitura e gravação sistema operacional.
-A complexidade de pior caso é O(n²/tamArea), sendo tamArea o número de
registros que podem ser armazenados na memória interna.
-A complexidade de médio caso é O(n/b log(n/tamArea)), segundo o trabalho de
Monard(1980) este é o caso com maior probabilidade de ocorrer.
32
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Exercícios
1 – Monte uma tabela com as características de melhor caso, pior caso, caso
médio, sensibilidade de ordenação, influência de n e estabilidade para os
algoritmos: Selectionsort, Insertionsort, Shellsort, Heapsort, Quicksort,
Intercalação Balanceada, Seleção por Substituição, Intercalação Polifásica e
Quicksort Externo.
2- Entregue um resumo do artigo “Quicksort Externo”, de Fabiano Cupertino
Botelho e Ligiane Alves de Souza.
33
5COP096 – Teoria da Computação
Aula 7 – Ordenação
Referências
Ziviani, Nivio. Projeto de algoritmos: com implementações em Java e C.
Thomson Learning, 2007.
Leiserson, Charles E., Ronald L. Rivest, and Clifford Stein. Introduction to
algorithms. Ed. Thomas H. Cormen. The MIT press, 2001.