Classificação
Métodos de Classificação
Os métodos de classificação podem ser dos tipos:
 Classificação interna – quando toda a coleção de
itens a classificar pode ficar armazenada em um
“array” em memória
 Classificação externa – quando as coleções de
itens são muito grandes para poder permanecer
armazenadas em memória
2
Regiões classificada e não
classificada
Os métodos são iterativos e nos “arrays” de registros
aparecem duas regiões: a região já classificada e a
região de registros ainda não classificados. Em cada
iteração vai crescendo a região classificada. O
processo se encerra quando a região classificada
abrange todo o “array”.
3
Métodos mais conhecidos
Os métodos mais conhecidos são:
 Classificação por troca
 Classificação por seleção
 Classificação por inserção
4
Classificação por troca
Na classificação por troca comparam-se dois
elementos do “array” verificando se a posição
relativa do antecessor e do sucessor
obedecem ao critério de classificação
especificado. Caso haja obediência ao critério
de classificação nada é feito. Em caso
contrário trocam-se as posições destes
registros.
Exemplos:
 Bubble Sort
 Shake Sort
 Quick Sort
5
Classificação por Inserção
Na classificação por inserção em cada
instante toma-se um elemento, o elemento
corrente, do trecho ainda não classificado do
“array” e faz-se a inserção deste elemento na
posição correta do trecho já classificado. Em
conseqüência reduz-se o trecho ainda não
classificado e amplia-se o trecho já
classificado.
Exemplos:
 Inserção Simples
 Shell Sort
6
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
7
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
8
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
9
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
10
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
11
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
12
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
13
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
14
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
15
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
16
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
17
Exemplo de Inserção Simples
Posição no “array”
Vai para
A inserir
0
0
1
1
0
2
3
3
0
4
5
5
2
6
3
7
7
8
2
9
-
0
30
30
30
30
8
8
7
7
7
7
7
7
1
42
42
42
42
30
30
8
8
8
8
8
8
2
8
8
8
8
42
42
30
30
13
13
13
11
3
55
55
55
55
55
55
42
42
30
20
20
13
4
7
7
7
7
7
7
55
55
42
30
30
20
5
90
90
90
90
90
90
90
90
55
42
42
30
6
13
13
13
13
13
13
13
13
90
55
55
42
7
20
20
20
20
20
20
20
20
20
90
71
55
8
71
71
71
71
71
71
71
71
71
71
90
71
9
11
11
11
11
11
11
11
11
11
11
11
90
18
Classificação por Seleção
Na classificação por seleção, em cada
instante seleciona-se do trecho ainda não
classificado o elemento mais apropriado para
ser acrescentado ao trecho já classificado. Em
conseqüência reduz-se o trecho ainda não
classificado e amplia-se o trecho já
classificado.
Exemplos:
 Seleção Direta
 Heap Sort
19
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
20
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
21
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
22
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
23
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
24
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
25
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
26
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
27
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
28
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
29
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
30
Exemplo de Seleção Direta
Posição no “array”
Selecionado
Vai para
4
0
2
1
9
2
6
3
7
4
7
5
9
6
9
7
8
8
9
9
8
8
0
30
30
7
7
7
7
7
7
7
7
7
7
1
42
42
42
8
8
8
8
8
8
8
8
8
2
8
8
8
42
11
11
11
11
11
11
11
11
3
55
55
55
55
55
13
13
13
13
12
12
12
4
7
7
30
30
30
30
20
20
20
20
20
20
5
90
90
90
90
90
90
90
30
30
30
30
30
6
13
13
13
13
13
55
55
55
42
42
42
42
7
20
20
20
20
20
20
30
90
90
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
11
11
11
11
42
42
42
42
55
90
90
90
31
Exemplo de Quick Sort (1)
Ponto de separação
Posição no “array”
Posição no novo“array”
A trocar no novo "array"
0
4
1
2
Ponto de separação
Posição no “array”
Posição no novo“array”
A trocar no novo "array"
Ponto de separação
Posição no “array”
Posição no novo“array”
A trocar no novo "array"
0
2
Ponto de separação
Posição no “array”
Posição no novo“array”
A trocar no novo "array"
Ponto de separação
Posição no “array”
Posição no novo“array”
A trocar no novo "array"
0
0
11
11
7
7
1
1
20
20
20
8
(7+8)/2=7,5
0
1
0
1
7
8
7
8
0
1
0
1
2
2
8
8
8
20
2
3
3
13
13
13
13
3
( 11 + 7) / 2 = 9
4
5
6
4
7
7
11
11
4
( 20 + 11 )/2=15,5
2
3
4
0
1
2
20
13
11
20
13
11
11
13
20
11
2
0
11
11
3
4
7
8
9
5
6
7
8
9
5
6
7
8
9
5
6
7
8
9
5
6
7
8
9
(13+20)/2=16,5
0
1
2
3
0
13
13
4
1
20
20
32
Ponto de separação
Posição no “array”
Posição no
novo“array”
A trocar no novo
"array"
0
4
1
2
Ponto de separação
Posição no “array”
Posição no
novo“array”
A trocar no novo
"array"
0
1
2
3
4
5
0
( 90 + 30 ) / 2 = 60
6
7
8
9
1
2
3
4
90
55
42
71
30
90
30
30
55
55
42
42
42
55
71
71
71
30
90
90
7
8
9
( 55 + 90
)/2=72,5
7
8
0
1
9
2
(30+42)/2=36
0
1
2
3
4
5
0
6
1
30
42
30
42
Ponto de separação
Posição no “array”
Posição no
novo“array”
A trocar no novo
"array"
Ponto de separação
Posição no “array”
Posição no
novo“array”
A trocar no novo
"array"
Exemplo de
Quick Sort (2)
0
0
1
1
2
2
3
3
4
4
5
5
6
6
55
71
90
55
71
90
55
7
0
8
9
55
55
Ponto de separação
Posição no “array”
Posição no
novo“array”
A trocar no novo
"array"
"array"classificado
(71+90)/2=80,5
0
7
1
2
3
4
Resultado obtido
8
11
13
20
5
30
6
42
7
55
8
0
9
1
71
90
71
90
71
90
33
Exemplo de “Shell Sort” (1)
Posição no “array”
0
30
1
42
2
8
3
55
4
7
5
90
6
13
7
20
8
71
9
11
3
20
4
30
5
42
6
13
7
55
8
71
9
90
Intervalo 4 - Classificar por inserção
Posição no “array”
Posição no novo“array”
A inserir
Vai para
0
0
1
0
2
2
Posição no “array”
Posição no novo“array”
A inserir
Vai para
0
0
1
1
2
0
Posição no “array”
Posição no novo“array”
A inserir
Vai para
0
0
1
1
Posição no “array”
Posição no novo“array”
A inserir
Vai para
0
0
1
0
0
0
30
30
7
7
1
0
42
42
42
11
2
0
8
8
8
3
0
55
55
20
4
1
7
7
30
30
5
1
90
90
90
42
6
1
13
13
13
7
1
20
20
55
8
2
71
71
71
71
9
2
11
11
11
90
0
1
11
2
Classificação obtida
Posição no “array”
7
8
34
Exemplo de “Shell Sort” (2)
Intervalo 2 - Classificar por inserção
Posição no “array”
Posição no novo“array”
A inserir
Vai para
0
0
1
1
2
2
3
2
4
4
Posição no “array”
Posição no novo“array”
A inserir
Vai para
0
0
1
1
2
2
3
3
4
4
Classificação obtida
Posição no “array”
7
0
0
7
7
7
7
7
7
1
0
11
11
11
11
11
11
2
1
8
8
8
8
8
8
3
1
20
20
20
20
20
20
4
2
30
30
30
30
13
13
5
2
42
42
42
42
42
42
6
3
13
13
13
13
30
30
7
3
55
55
55
55
55
55
8
4
71
71
71
71
71
71
9
4
90
90
90
90
90
90
0
1
11
2
3
20
4
13
8
5
42
6
30
7
55
8
71
9
90
35
Exemplo de “Shell Sort” (3)
Intervalo 1 - Classificar por inserção
Posição no “array”
A inserir
Vai para
0
0
1
1
2
1
3
3
4
3
5
5
6
5
7
7
8
8
9
9
-
0
7
7
7
7
7
7
7
7
7
7
7
7
1
11
11
11
11
8
8
8
8
8
8
8
8
2
8
8
8
8
11
11
11
11
11
11
11
11
3
20
20
20
20
20
20
13
13
13
13
13
13
4
13
13
13
13
13
13
20
20
20
20
20
20
5
42
42
42
42
42
42
42
42
30
30
30
30
6
30
30
30
30
30
30
30
30
42
42
42
42
7
55
55
55
55
55
55
55
55
55
55
55
55
8
71
71
71
71
71
71
71
71
71
71
71
71
9
90
90
90
90
90
90
90
90
90
90
90
90
2
11
3
13
4
20
5
30
6
42
7
55
8
71
9
90
Classificação obtida
Posição no “array”
0
7
1
8
36
Critérios de Opção
Sugestão
Método de
Classificação
“quick sort”
“heap sort”
“shell sort”
Número mínimo recomendável de
registros
30
70
400
Uma regra simples, que deve ser reavaliada em casos
mais sensíveis, consiste em se utilizar:
 Inserção simples para “arrays” com até 30
registros;
 “Quick Sort” para “arrays” com mais de 30
registros.
37
Hierarquia de classes para a
classificação interna
38
Interface Sorter
//
pgm15_01.java
public interface Sorter
{
void sort (Comparable[]array);
}
39
A Classe Abstrata AbstractSorter (1)
// pgm15_02.java
public abstract class AbstractSorter
implements Sorter
{
protected Comparable[] array;
protected int n;
protected abstract void sort();
40
A Classe Abstrata AbstractSorter (2)
public final void sort (Comparable[] array)
{
n = array.length;
this.array = array;
if(n > 0)
sort();
this.array = null;
}
protected final
{
Comparable
array[i] =
array[j] =
}
void swap(int i, int j)
tmp = array[i];
array[j];
tmp;
}
41
Insertion Sorting
42
A Classe StraightInsertionSorter
//
pgm15_03.java
public class StraightInsertionSorter
extends AbstractSorter
{
protected void sort()
{
for(int i = 1; i < n; ++i)
for(int j = i; j > 0 && array[j - 1].isGT
(array [j]); --j)
{
swap(j, j - 1);
}
}
}
43
A Classe BinaryInsertionSorter (1)
//
pgm15_04.java
public class BinaryInsertionSorter
extends AbstractSorter
{
protected void sort()
{
for(int i = 1; i < n; ++i)
{
Comparable tmp = array[i];
int left = 0;
int right = i;
44
A Classe BinaryInsertionSorter (2)
while(left < right)
{
int middle = (left + right) / 2;
if(tmp.isGE(array[middle]))
left = middle + 1;
else
right = middle;
}
for(int j = i; j > left; --j)
swap (j - 1, j);
}
}
}
45
Bublesort
46
A Classe BubbleSorter
//
pgm15_05.java
public class BubbleSorter
extends AbstractSorter
{
protected void sort()
{
for(int i = n; i > 1; --i)
for(int j = 0; j < i - 1; ++j)
if(array[j].isGT(array[j + 1]))
swap(j, j + 1);
}
}
47
QuickSort
48
A Classe Abstrata
AbstractQuickSorter (1)
//
pgm15_06.java
public abstract class AbstractQuickSorter
extends AbstractSorter
{
protected static final int cutOff = 2; // minimum cut-off
protected abstract int selectPivot(int left, int right);
// ...
}
49
A Classe Abstrata
AbstractQuickSorter (2)
//
pgm15_07.java
public abstract class AbstractQuickSorter
extends AbstractSorter
{
protected void sort(int left, int right)
{
if(right - left + 1 > cutOff)
{
int p = selectPivot(left, right);
swap(p, right);
Comparable pivot = array[right];
int i = left;
int j = right - 1;
50
A Classe Abstrata
AbstractQuickSorter (3)
for(;;)
{
while(i < j && array[i].isLT(pivot))
while(i < j && array[j].isGT(pivot))
if(i >= j)
break;
++i;
--j;
swap(i++, j--);
}
if(array[i].isGT(pivot))
swap(i, right);
if(left < i)
sort(left, i - 1);
if(right > i)
sort(i + 1, right);
}
}
// ...
}
51
A Classe Abstrata
AbstractQuickSorter (4)
//
pgm15_08.java
public abstract class AbstractQuickSorter
extends AbstractSorter
{
protected void sort()
{
sort(0, n - 1);
Sorter sorter = new StraightInsertionSorter();
sorter.sort(array);
}
// ...
}
52
A Classe MedianOfThreeQuickSorter
//
pgm15_09.java
public class MedianOfThreeQuickSorter
extends AbstractQuickSorter
{
protected int selectPivot(int left, int right)
{
int middle = (left + right) / 2;
if (array[left].isGT(array[middle]))
swap(left, middle);
if(array[left].isGT(array[right]))
swap(left, right);
if(array[middle].isGT(array[right]))
swap(middle, right);
return middle;
}
}
53
StraightSelectionSort
54
A Classe StraightSelectionSorter
//
pgm15_10.java
public class StraightSelectionSorter
extends AbstractSorter
{
protected void sort()
{
for(int i = n; i > 1; --i)
{
int max = 0;
for(int j = 1; j < i; ++j)
if(array[j].isGT(array[max]))
max = j;
swap(i - 1, max);
}
}
}
55
HeapSort
56
Construção de um Heap
57
Heap Sorting
58
A classe HeapSorter (1)
//
pgm15_11.java
public class HeapSorter
extends AbstractSorter
{
protected static final int base = 1;
protected void percolateDown(int i, int length)
{
while(2 * i <= length)
{
int j = 2 * i;
if( j < length &&
array[j + 1 - base].isGT(array[j - base]) )
59
A classe HeapSorter (2)
j = j + 1;
if(array[i - base].isGE(array[j - base]))
break;
swap(i - base, j - base);
i = j;
}
}
// ...
}
60
A classe HeapSorter (3)
//
pgm15_12.java
public class HeapSorter
extends AbstractSorter
{
protected static final int base = 1;
protected void buildHeap()
{
for(int i = n / 2; i > 0; --i)
percolateDown (i, n);
}
// ...
}
61
A classe HeapSorter (4)
//
pgm15_13.java
public class HeapSorter
extends AbstractSorter
{
protected static final int base = 1;
protected void sort()
{
buildHeap();
for(int i = n; i >= 2; --i)
{
swap(i - base, 1 - base);
percolateDown(1, i - 1);
}
}
// ...
}
62
Two Way Merging
63
Two Way Merge Sorting
64
A classe TwoWayMergeSorter (1)
//
pgm15_14.java
public class TwoWayMergeSorter
extends AbstractSorter
{
Comparable[] tempArray;
// ...
}
65
A classe TwoWayMergeSorter (2)
//
pgm15_15.java
public class TwoWayMergeSorter
extends AbstractSorter
{
Comparable[] tempArray;
protected void merge(int left, int middle, int right)
{
int i = left;
int j = left;
int k = middle + 1;
66
A classe TwoWayMergeSorter (3)
while(j <= middle && k <= right)
{
if(array[j].isLT(array[k]))
tempArray[i++] = array[j++];
else
tempArray[i++] = array[k++];
}
while(j <= middle)
tempArray[i++] = array[j++];
for(i = left; i < k; ++i)
array[i] = tempArray[i];
}
// ...
}
67
A classe TwoWayMergeSorter (4)
//
pgm15_16.java
public class TwoWayMergeSorter
extends AbstractSorter
{
Comparable[] tempArray;
protected void
{
tempArray
sort(0, n
tempArray
}
sort()
= new Comparable[n];
- 1);
= null;
68
A classe TwoWayMergeSorter (5)
protected void sort (int left, int right)
{
if(left < right)
{
int middle = (left + right) / 2;
sort(left, middle);
sort(middle + 1, right);
merge(left, middle, right);
}
}
// ...
}
69
Bucket Sorting
70
A classe BucketSorter (1)
//
pgm15_17.java
public class BucketSorter
extends AbstractSorter
{
protected int m;
protected int[] count;
public BucketSorter(int m)
{
this.m = m;
count = new int [m];
}
protected void sort()
{ sort((Int[]) array); }
// ...
}
71
A classe BucketSorter (2)
//
pgm15_18.java
public class BucketSorter
extends AbstractSorter
{
protected int m;
protected int[] count;
protected void sort(Int[] array)
{
for(int i = 0; i < m; ++i)
count[i] = 0;
for(int j = 0; j < n; ++j)
++count[array[j].intValue()];
for(int i = 0, j = 0; i < m; ++i)
for( ; count[i] > 0; --count[i])
array[j++] = new Int(i);
}
// ...
}
72
Radix Sorting
73
A classe RadixSorter (1)
//
pgm15_19.java
public class RadixSorter
extends AbstractSorter
{
protected static final int r = 8; // bits da raiz
protected static final int R = 1 << r; // Raiz
protected static final int p = (32 + r - 1) / r;
// Int com 32 bits
// p número de passagens para varrer um Int
protected int[] count = new int [R];
protected void sort()
{ sort ((Int[]) array); }
// ...
}
74
A classe RadixSorter (2)
//
pgm15_20.java
public class RadixSorter
extends AbstractSorter
{
protected void sort (Int[] array)
{
Int[] tempArray = new Int[n];
75
A classe RadixSorter (3)
for(int i = 0; i < p; ++i)
{
for(int j = 0; j < R; ++j)
count[j] = 0;
for(int k = 0; k < n; ++k)
{
// r * i é o número de dígitos argumento do right shift
// R – 1 é a máscara para R = 10000, R - 1 = 1111
++count[( array[k].intValue() >>> (r*i) ) & (R-1)];
tempArray[k] = array[k];
}
int pos = 0;
for(int j = 0; j < R; ++j)
{
int tmp = pos;
pos += count[j];
count[j] = tmp;
}
76
A classe RadixSorter (4)
for(int k = 0; k < n; ++k)
{
int j = ( tempArray[k].intValue() >>>
(r*i) ) & (R-1);
array[count[j]++] = tempArray[k];
}
}
}
// ...
}
77