Programação II
Laboratório II
Prof. Mateus Raeder
Transparências baseadas nos originais
da Prof. Patrícia Jaques
Universidade do Vale do Rio dos Sinos
- São Leopoldo -
Classificação de Dados
Programação II – Prof. Mateus Raeder
Classificação
• Processo de organizar itens em ordem
(de)crescente, segundo algum critério
• Também chamado de ordenação
• Aplicações de Sorting
– Preparação de dados para facilitar pesquisas futuras
• Exemplo: dicionários e listas telefônicas
– Agrupar itens que apresentam mesmos valores
• Para eliminação de elementos repetidos
– Batimento entre itens presentes em mais de um arquivo
• Para combinação de dados presentes nos vários arquivos
• Para consolidação dos vários arquivos em um único
Programação II – Prof. Mateus Raeder
Definições
•
Sejam R1, R2, …, RN , N ítens (chamados registros)
• Cada registro Ri, é formado por uma chave Ci e por
informações ditas satélites
• A ordenação dos registros é feita definindo-se uma
relação de ordem “<“ sobre os valores das chaves
• O objetivo da ordenação é determinar uma permutação
dos índices 1  i1, i2, …, iN  N das chaves, tal que Ci1  Ci2 
…  CiN.
• Um conjunto de registros é chamado de arquivo
Programação II – Prof. Mateus Raeder
Relação de Ordem
• Uma relação de ordem “<“ (leia-se precede) deve
satisfazer as seguintes condições para quaisquer
valores a, b e c:
(i) Uma e somente uma das seguintes possibilidades é
verdadeira: a < b, a = b ou b < a (lei da tricotomia)
(ii) Se a < b e b < c, então a < c (transitividade)
• As propriedades (i) e (ii) definem o conceito de
ordem linear ou ordem total
Programação II – Prof. Mateus Raeder
Exercício
• Escreva um algoritmo para classificar um conjunto de 5
números em ordem crescente.
Programação II – Prof. Mateus Raeder
Formas de Representação do Resultado
– Reorganização Física
– Encadeamento
– Vetor Indireto de Ordenação (VIO)
Programação II – Prof. Mateus Raeder
Reorganização Física
chave
chave
1
10
1
7
2
19
2
10
3
13
3
12
4
12
4
13
5
7
5
19
(a) antes da classificação
(b) após a classificação
Programação II – Prof. Mateus Raeder
Encadeamento
cabeça da lista
5
chave
chave
1
10
1
10
4
2
19
2
19
0
3
13
3
13
2
4
12
4
12
3
5
7
5
7
1
(a) antes da classificação
(b) após a classificação
Programação II – Prof. Mateus Raeder
Vetor Indireto de Ordenação
Chave VIO
Chave
1
10
1
7
5
2
19
2
10
1
3
13
3
12
4
4
12
4
13
3
5
7
5
19
2
Programação II – Prof. Mateus Raeder
Métodos de Classificação
– Classificação por Inserção
• Inserção Direta
• ShellSort
– Classificação por Trocas (permutação)
• BubbleSort
• QuickSort
– Classificação por Seleção
• Seleção Direta
• HeapSort
Programação II – Prof. Mateus Raeder
Classificação por Inserção
• A classificação é obtida porque os elementos são
inseridos na sua posição correta.
• Algoritmos:
– Inserção Direta
– ShellSort
Programação II – Prof. Mateus Raeder
Inserção Direta
• Mais simples
• Normalmente utilizado para um conjunto pequeno de dados,
pois apresenta baixa eficiência
• Divide o vetor em 2 segmentos:
– o primeiro contendo os elementos já ordenados
– o segundo contendo os elementos ainda não ordenados
• Funcionamento: Pega o primeiro elemento do segmento não
ordenado e procura seu lugar no segmento ordenado.
• No início: o 1º segmento terá apenas 1 elemento
Programação II – Prof. Mateus Raeder
Inserção Direta
18
15
7
9
23
16
14
18
15
7
9
23
16
14
Vetor original
Divisão inicial
Não ordenado
Ordenado
Primeira iteração
Segunda iteração
15
7
18
15
7
9
23
16
14
18
9
23
16
14
...
Programação II – Prof. Mateus Raeder
Inserção Direta
0
1
2
3
4
5
6
18
15
7
9
23
16
14
public static void insertionSort (int a[]) {
for (int i = 1; i < a.length; i++) {
int j = i; // pos do 1º elemento no seg. não ord.
int B = a[i]; // 1º elemento no seg. não ord.
while ((j > 0) && (a[j-1] > B)) {
buscando a
a[j] = a[j-1];
posição
j--;
do 1º elemento
do segmento não
}
ordenado no
a[j] = B;
}
} // do método
segmento
ordenado
Programação II – Prof. Mateus Raeder
ShellSort
• Proposto por Ronald Shell em 1959.
• Explora as seguintes características do método de
inserção direta:
– desempenho aceitável quando o número de chaves é
pequeno;
– desempenho aceitável quando as chaves já possuem uma
ordenação parcial.
• É considerado uma extensão do método de inserção
direta, pois se diferencia deste apenas no nro. de
segmentos considerados.
• Realiza classificações parciais do vetor a cada iteração,
favorecendo o desempenho dos passos seguintes.
Programação II – Prof. Mateus Raeder
ShellSort
• Método de classificação:
– No primeiro passo, o vetor C [ n ] é dividido em h
segmentos, de tal forma que cada um possua n / h chaves
– Cada um dos segmentos é classificado por inserção direta,
separadamente
– No passo seguinte, o incremento h é diminuído (a metade
do valor anterior, se este era potência inteira de 2)
incrementos decrescente
– No último passo, h = 1
h=22=4
h=21=2
h=20=1
3 passos
Programação II – Prof. Mateus Raeder
ShellSort
• Testes empíricos sugerem que a melhor escolha
para os valores de h é a sequência
• <(3t-1)/2, ..., 13, 4, 1> onde
• ht = 3ht-1+1
–
–
–
–
3*0+1 = 1
3*1+1 = 4
3*4+1 = 13
3*13+1 = 40
Programação II – Prof. Mateus Raeder
ShellSort
0
1
2
3
4
17
25
49
12
0
1
2
3
11
23
27
12
17
1
2
3
4
0
1
2
11
12
13
5
6
7
8
9
10
11
45
38
53
42
27
13 11
6
7
8
9
10
11
25
45
13
18
42
49
45 53
1
2
3
4
1
2
3
4
1
3
4
5
6
7
8
9
10
11
12
17
18
23
25
27
38
42
18
4
23
5
45
49
12
Original
12
53
Primeiro passo:
h=4
Último passo:
h=1
Programação II – Prof. Mateus Raeder
ShellSort
public static void shellSort(int a[]) {
int h = 1;
// acha o maior valor possível para h
while ((h * 3 + 1) < a.length)
h = 3 * h + 1; // h=4
while( h > 0 ) { // para cada segmento de elem. (há h segm.)
for (int i = h; i < a.length; i++) {
int B = a[i];
int j = i;
// compara B com o elemento antes dele no conjunto
//e assim por diante até achar o lugar de B
while ((j >= h) && (a[j - h] > B)) {
a[j] = a[j - h];
j -= h;
}
a[j] = B;
}
h = h / 3;
0
1
2
3
4
5
6
7
8
9
}
11 23 27
12
17 25 45 13 18 42
}
1
2
3
4
10
49
Programação II – Prof. Mateus Raeder
1
2
3
4
1
2
3
11
12
45 53
4
1
Classificação por Trocas
• Caracterizam-se por efetuarem a classificação por
comparação entre pares de chaves, trocando-as
de posição caso estejam fora de ordem no par.
• Algoritmos:
– BubbleSort
– QuickSort
Programação II – Prof. Mateus Raeder
Método da Bolha (BubbleSort)
Exemplo: Suponha que se deseja classificar em ordem
crescente o seguinte vetor de chaves:
Primeira Varredura
28
26
28
26
30
24
25
compara par (28, 26) : troca
26
28
30
24
25
compara par (28, 30) : não troca
26
28
30
24
25
compara par (30, 24) : troca
26
28
24
30
25
compara par (30, 25) : troca
26
28
24
25
30
fim da primeira varredura
30
Programação II – Prof. Mateus Raeder
24
25
Método da Bolha (BubbleSort)
Segunda Varredura
26
28
24
25
30
compara par (26, 28) : não troca
26
28
24
25
30
compara par (28, 24) : troca
26
24
28
25
30
compara par (28, 25) : troca
26
24
25
28
30
fim da segunda varredura
Terceira Varredura
26
24
25
28
30
compara par (26, 24) : troca
24
26
25
28
30
compara par (26, 25) : troca
24
25
26
28
30
fim da terceira varredura
Programação II – Prof. Mateus Raeder
Método da Bolha (BubbleSort)
public static void bubbleSort(int a[]) {
for (int i = a.length-1; i>0; i--) { // nro de varreduras
for (int j = 0; j<i; j++) { // percorre vetor
if (a[j] > a[j+1]) { // troca par de posição
int T = a[j];
a[j] = a[j+1];
a[j+1] = T;
}
}
}
}
Programação II – Prof. Mateus Raeder
Método da Bolha (BubbleSort)
Considerando o seguinte vetor :
13 11 25 10 18
21 23
1)
Em quantas varreduras o vetor é classificado ?
2)
Como identificar, a partir da última varredura, quantas chaves
já estão classificadas?
Programação II – Prof. Mateus Raeder
Método da Bolha (BubbleSort)
Considerando o seguinte vetor :
13 11 25 10 18
21 23
1)
Em quantas varreduras o vetor é classificado ?
2)
Como identificar, a partir da última varredura, quantas chaves
já estão classificadas?
Observe que a quantidade de chaves, a partir da última,
que pode ser ignorada de uma varredura para a outra é
conhecida pela posição na qual ocorreu a última troca.
A partir daquele ponto o vetor já se encontra classificado!
Programação II – Prof. Mateus Raeder
Método da Bolha (BubbleSort)
Uma melhoria no algoritmo, para parar caso já esteja ordenado:
public static void bubbleSort(int a[]) {
for (int i = a.length-1; i>0; i--) { // nro. de varreduras
boolean flipped = false;
for (int j = 0; j<i; j++) {
if (a[j] > a[j+1]) { // troca par de posição
int T = a[j];
a[j] = a[j+1];
a[j+1] = T;
flipped = true;
}
}
if (!flipped) return;
}
}
Programação II – Prof. Mateus Raeder
Método da Bolha (BubbleSort)
•
Análise do Desempenho do melhor caso
– aquele no qual as chaves já se encontram na ordem desejada
– na primeira varredura o método já terá descoberto que o vetor já se
encontra ordenado
– número de comparações efetuadas ?
• n-1
•
Análise do desempenho do pior caso
– chaves do vetor se encontram na ordem inversa a desejada
– a cada varredura apenas uma chave será colocada no seu lugar definitivo;
as demais se deslocarão uma posição para a esquerda (em ordenação
crescente)
Programação II – Prof. Mateus Raeder
Método QuickSort
A idéia básica é a de dividir o problema, de ordenar
um conjunto de n itens em dois problemas menores.
A seguir, os problemas menores são ordenados
independentemente e depois os resultados são combinados
para produzir a solução do problema maior!
(Ziviani, 1996)
Programação II – Prof. Mateus Raeder
QuickSort
• 1) Dividir
– Escolher um elemento da array como pivô (x);
– Particionar:
• elementos < pivô  primeira parte
• elementos > pivô  segunda parte
Programação II – Prof. Mateus Raeder
QuickSort
• Princípio de classificação
– inicialmente, o vetor de chaves C é particionado em três
segmentos S1, S2 e S3
– S2 terá comprimento 1 e conterá uma chave denominada
particionadora ou pivô
– S1 terá comprimento  0 e conterá todas as chaves cujos
valores são menores ou iguais ao da chave particionadora.
Esse segmento está posicionado à esquerda de S2
– S3 terá comprimento  0 e conterá todas as chaves cujos
valores são maiores do que o da chave particionadora. Esse
segmento está posicionado à direita de S2
Programação II – Prof. Mateus Raeder
QuickSort
Vetor Inicial :
1
C [ 1 .. n ]
n
Vetor Particionado
1
K-1
S1
Onde:
k
S2
n
K+1
S3
C [ i ]  C [ k ] , para i = 1, … , k - 1
C [ i ] > C [ k ] , para i = k + 1 , … , n
Programação II – Prof. Mateus Raeder
QuickSort
• Princípio de classificação (continuação … )
– o processo de particionamento é reaplicado aos
segmentos S1 e S2 e a todos os segmentos
correspondentes daí resultantes, que tiverem
comprimento  1
– quando não restarem segmentos a serem
particionados, o vetor estará ordenado
– qual é a chave particionadora ideal ? Como escolher
essa chave ?
Programação II – Prof. Mateus Raeder
QuickSort
• Escolhendo a chave particionadora ...
– para simplificar o algoritmo de particionamento, podese arbitrar que a chave que se encontra na posição
inicial do vetor a ser particionado será a
particionadora
– se existe conhecimento prévio sobre a distribuição dos
valores das chaves e o vetor já se encontra
parcialmente ordenado, a chave que se encontra na
posição central do vetor pode ser a eleita
Programação II – Prof. Mateus Raeder
QuickSort
public static void quickSort (int[] a, int lo, int hi){
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];
// partition
do
{
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
// recursion
if (lo<j) quickSort(a, lo, j);
if (i<hi) quickSort(a, i, hi);
}
Programação II – Prof. Mateus Raeder
Quick Sort
void quicksort (int[] a, int lo, int hi)
{
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];
//
do
{
partition
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
// recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}
quicksort(a, 0, a.length-1)
lo
0
1
i
i
0
0
0
hi
x=a[4]
1
1
1
2
3
2
3
i
i
2
3
2
3
j
4
4
5
5
6
j
7
6
7
8
8
9
j
9
j
4
5
6
7
i4 j
5
6
7
i
quicksort(a, 0, 3)
quicksort(a, 5, 9)
Programação II – Prof. Mateus Raeder
8
8
9
9
Quick Sort
void quicksort (int[] a, int lo, int hi)
{
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];
//
do
{
}
partition
lo
0
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
i
// recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
j
0
0
x=a[1]
1
1
2
2
i j 2j
1
lo
hi
3
j
3
4
4
5
6
i
i
5
6
7
8
i
7
3
i
hi
x=a[7]
9
j
8
9
ji
i
quicksort(a, 5, 8)
quicksort(a, 0, 0)
quicksort(a, 2, 3)
Programação II – Prof. Mateus Raeder
Quick Sort
x=a[2]
void quicksort (int[] a, int lo, int hi)
{
int i=lo, j=hi, h;
int x=a[(lo+hi)/2];
//
do
{
partition
while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
// recursion
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}
lo hi
0
1
2
3
4
ij j
0
1
2
j
3
i
4
lo
x=a[6]
hi
5
6
8
i
5
7
i
6
9
j
7
8
9
j ji i
quicksort(a, 5, 6)
Programação II – Prof. Mateus Raeder
Quick Sort
Exercício:
Suponha que se deseja classificar o seguinte vetor:
G
R
E
M
I
S
T
A
Suponha que a chave particionadora está na posição
no meio do vetor.
Simule as iterações necessárias para a classificação,
segundo o algoritmo apresentado.
Programação II – Prof. Mateus Raeder
Classificação por Seleção
• Caracterizam-se por procurarem, a cada iteração, a
chave de menor (ou maior) valor do vetor e colocá-la na
sua posição definitiva correta, qual seja, no início (ou no
final) do vetor, por permutação com a que ocupa aquela
posição!
• Algoritmos:
– Seleção Direta
– HeapSort
Programação II – Prof. Mateus Raeder
Classificação por Seleção Direta
• Princípio de classificação
– a seleção da menor chave é feita por pesquisa
seqüencial
– a menor chave encontrada é permutada com a
que ocupa a posição inicial do vetor, que fica
reduzido de um elemento
– o processo de seleção é repetido para a parte
restante do vetor, até que todas as chaves
tenham sido selecionadas e colocadas em suas
posições definitivas
Programação II – Prof. Mateus Raeder
Classificação por Seleção Direta
Suponha que se deseja classificar o seguinte vetor:
9
25
10
18
5
7
15
3
Simule as iterações necessárias para a classificação.
Programação II – Prof. Mateus Raeder
Classificação por Seleção Direta
Iteração
1
2
3
4
5
6
7
8
Vetor
9
3
3
3
3
3
3
3
25
25
5
5
5
5
5
5
10
10
10
7
7
7
7
7
18 5
18 5
18 25
18 25
9 25
9 10
9 10
9 10
Chave
Selecionada
7
7
7
10
10
25
15
15
15
15
15
15
15
15
25
18
3
9
9
9
18
18
18
25
3
5
7
9
10
15
18
Permutação
Vetor ordenado até a
posição
9e3
25 e 5
10 e 7
18 e 9
25 e 10
25 e 15
25 e 18
Programação II – Prof. Mateus Raeder
1
2
3
4
5
6
8
Classificação por Seleção Direta
public static void selectionSort (int a[]) {
int min=0, ch;
for (int i=0; i<a.length-1; i++) {
min = i;
// mínimo inicial
for (int j = i + 1; j<a.length; j++)
if (a [ j ] < a [ min ]) min = j; // acha o novo mínimo
ch = a [ i ];
a [ i ] = a [ min ] ;
// coloca o novo mínimo
a [ min ] = ch;
// na posição correta
}
}
Programação II – Prof. Mateus Raeder