Aula_008 - Busca pela Moda

Prévia do material em texto

1
Aula 8
Professores:
Dante Corbucci Filho
Alexandre Plastino
Conteúdo:
- Busca pela Moda
- Algoritmos de Ordenação
 - Método da Seleção
 - Método da Bolha
 - Método da Partição ("Quicksort")
- Noções de Complexidade de Algoritmos
2
Busca pela Moda de um Vetor
 A moda de um vetor é o elemento que aparece 
com mais freqüência neste vetor.
 O problema da busca pela moda consiste em 
encontrar este elemento no vetor.
 Sem perda de generalidade, o problema será 
atacado considerando-se que:
 - os elementos do vetor são numéricos;
 - mais de um elemento pode aparecer o mesmo número
 de vezes e ser moda; nesse caso, o que aparecer
 primeiro no vetor será apresentado como resposta.
3
Busca pela Moda de um Vetor
Vetor: contém um grupo de inteiros 
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
Elementosposição dos elementos(índices) 
Qual é a Moda deste Vetor?
4
Busca pela Moda de um Vetor
Vetor: contém um grupo de inteiros 
Elementosposição dos elementos(índices) 
Moda deste Vetor: elemento 7 (que ocorre 3 vezes).
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
5
Program Procura_Moda (input{teclado}, output{vídeo});
Const 
 N = 100;
Type
 T_Dominio = 1 . . N;
 T_Vetor = array[T_Dominio] of integer;
Var
 Numeros: T_Vetor;
 Moda: integer; {moda do vetor}
Begin 
End. 
6
Program Procura_Moda (input{teclado}, output{vídeo});
Const 
 N = 100;
Type
 T_Dominio = 1 . . N;
 T_Vetor = array[T_Dominio] of integer;
Var
 Numeros: T_Vetor;
 Moda: integer; {moda do vetor}
Begin 
 Ler(Numeros);
 Moda:= BuscaModa(Numeros);
 Escrever(Moda);
End. 
7
Program Procura_Moda (input{teclado}, output{vídeo});
. . .
Procedure Ler(Var V{s}: T_Vetor); 
 begin 
 end;
Function Busca_Moda(V{e}: T_Vetor): integer; 
 begin 
 end;
Procedure Escrever(Mais_Frequente{e}: integer); 
 begin 
 end;
Begin 
 Ler(Numeros);
 Moda := Busca_Moda(Numeros);
 Escrever(Moda);
End. 
8
Program Procura_Moda (input{teclado}, output{vídeo});
. . .
Procedure Ler(Var V{s}: T_Vetor); 
 var ind: T_Dominio;
 begin 
 for ind:= 1 to N do
 begin
 write(output, ’Elemento[’, Ind, ’]= ’);
 readln(input, V[Ind]); 
 end;
 end;
. . .
Begin 
 Ler(Numeros);
 Moda := Busca_Moda(Numeros);
 Escrever(Moda);
End. 
9
Program Procura_Moda (input{teclado}, output{vídeo});
. . .
Procedure Escrever(Mais_Frequente{e}: integer); 
 begin 
 writeln(output, ’A moda do vetor é ’, Mais_Frequente)
 end;
. . .
Begin 
 Ler(Numeros);
 Moda:= Busca_Moda(Numeros);
 Escrever(Moda);
End. 
10
Busca Simples pela Moda
Vetor 
Auxiliar (contém a freqüência de cada elemento do Vetor) 
 Todas as N posições do vetor são comparadas 
com os elementos seguintes do vetor.
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
0 0 0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10
11
Busca Simples pela Moda
Vetor 
Auxiliar (contém a freqüência de cada elemento do Vetor) 
 Todas as N posições do vetor são comparadas 
com os elementos seguintes do vetor. 
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
2 0 0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10
12
Busca Simples pela Moda
Vetor 
Auxiliar (contém a freqüência de cada elemento do Vetor) 
 Todas as N posições do vetor são comparadas 
com os elementos seguintes do vetor. 
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
2 2 0 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10
13
Busca Simples pela Moda
Vetor 
Auxiliar (contém a freqüência de cada elemento do Vetor) 
 Todas as N posições do vetor são comparadas 
com os elementos seguintes do vetor. 
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
2 2 3 0 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10
14
Busca Simples pela Moda
Vetor 
Auxiliar (contém a freqüência de cada elemento do Vetor) 
 Todas as N posições do vetor são comparadas 
com os elementos seguintes do vetor. 
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
2 2 3 1 0 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10
15
Busca Simples pela Moda
Vetor 
Auxiliar (contém a freqüência de cada elemento do Vetor) 
 Todas as N posições do vetor são comparadas 
com os elementos seguintes do vetor. 
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
2 2 3 1 1 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10
16
Busca Simples pela Moda
Vetor 
Auxiliar 
 Todas as N posições do vetor são comparadas 
com os elementos seguintes do vetor. 
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
2 2 3 1 1 2 1 1 1 0
1 2 3 4 5 6 7 8 9 10
17
Busca Simples pela Moda
Vetor 
Auxiliar 
 Todas as N posições do vetor são comparadas 
com os elementos seguintes do vetor. 
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
2 2 3 1 1 2 1 1 1 1
1 2 3 4 5 6 7 8 9 10
18
Busca Simples pela Moda
Vetor 
Auxiliar 
 Todas as N posições do vetor são comparadas 
com os elementos seguintes do vetor. 
Moda = 7
1 2 3 4 5 6 7 8 9 10
10 19 7 6 19 7 8 10 7 12
2 2 3 1 1 2 1 1 1 1
1 2 3 4 5 6 7 8 9 10
19
Function BuscaModa(V{e}: T_Vetor): integer;
 var ind1, ind2, conta, max: integer; 
 Freq: T_Vetor;
 begin
 for ind1:= 1 to N do {calcula freqüência de cada elemento}
 begin
 conta:=1;
 for ind2:=ind1+1 to N do
 if V[ind1] = V[ind2] then
 conta:=conta+1;
 Freq[ind1]:=conta;
 end;
 max:=1;
 for ind1:= 2 to N do {calcula maior freqüência} 
 if Freq[ind1] > Freq[max] then
 max:=max+1;
 BuscaModa := V[max]; {moda = V[max]} 
 end;
20
Busca Simples pela Moda
 No algoritmo anterior, há basicamente dois comandos for-do 
em seqüência. Neste caso, o primeiro for-do, que possui o maior custo 
computacional, determina a complexidade do algoritmo.
 O primeiro for-do executa, para cada elemento do vetor, 
comparações com os elementos seguintes. Desta forma, 
aproximadamente N*(N-1)/2 elementos são acessados. Ou seja, 
o número de elementos avaliados é da ordem de N2. Portanto 
sua complexidade é O(N2).
21
Busca pela Moda de um Vetor Ordenado
 Neste caso, considera-se que os elementos 
encontra-se ordenados de forma crescente no vetor.
Vetor ordenado
Moda deste Vetor: elemento 7 (que ocorre 3 vezes).
6 7 7 7 8 10 10 12 19 19
1 2 3 4 5 6 7 8 9 10
22
Function Busca_Moda(V{e}: T_Vetor): integer;
 var ind, conta, moda: integer; 
 begin
 moda:=V[1]
 ind:=1; 
 conta:=1;
 while ind < N do
 begin
 ind:=ind+1;
 if V[ind] = V[ind-conta] then
 begin
 moda:=V[ind];
 conta:=conta+1
 end
 end;
 Busca_Moda := moda;
 end;
23
Busca pela Moda de um Vetor Ordenado
 No algoritmo anterior, o vetor é percorrido 
apenas uma vez. Desta forma, o número de 
elementos avaliados é da ordem de N. Portanto a 
complexidade do algoritmo é O(N).
24
Algoritmos de Ordenação
 O problema da ordenação é caracterizado pelaorganização de um conjunto de elemento do mesmo 
tipo segundo um critério de ordenação.
 Sem perda de generalidade, o problema será 
atacado considerando-se que:
 - os elementos a serem ordenados são numéricos
 e estão armazenados em um vetor,
 - deseja-se ordenar os elementos crescentemente:
 se i < j, então Vetor[i] < Vetor[j]
 
25
Algoritmos de Ordenação
Entrada: Vetor que contém um conjunto de elementos. 
Saída: Vetor com o conjunto de elementos ordenados. 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
1 2 3 4 5 6 7 8 9 10
1 3 4 6 7 8 10 12 18 19
26
Program Ordena (input{teclado}, output{vídeo});
Const 
 N = 100;
Type
 T_Dominio = 1 . . N;
 T_Vetor = array[T_Dominio] of integer;
Var
 Numeros: T_Vetor;
Begin 
End.
27
Program Ordena (input{teclado}, output{vídeo});
Const 
 N = 100;
Type
 T_Dominio = 1 . . N;
 T_Vetor = array[T_Dominio] of integer;
Var
 Numeros: T_Vetor;
Begin 
 Ler(Numeros);
 Ordenar(Numeros);
 Escrever(Numeros);
End. 
28
Program Ordena (input{teclado}, output{vídeo});
. . .
Procedure Ler(Var V{s}: T_Vetor); 
 begin 
 end;
Procedure Ordenar(Var V{e/s}: T_Vetor); 
 begin 
 end;
Procedure Escrever(V{e}: T_Vetor); 
 begin 
 end;
Begin 
 Ler(Numeros);
 Ordenar(Numeros);
 Escrever(Numeros);
End. 
29
Program Ordena (input{teclado}, output{vídeo});
. . .
Procedure Ler(Var V{s}: T_Vetor); 
 var ind: T_Dominio;
 begin 
 for ind:= 1 to N do
 begin
 write(output, ’Elemento[’, Ind, ’]= ’);
 readln(input, V[Ind]); 
 end;
 end;
. . .
Begin 
 Ler(Numeros);
 Ordenar(Numeros);
 Escrever(Numeros);
End. 
30
Program Ordena (input{teclado}, output{vídeo});
. . .
Procedure Escrever(V{e}: T_Vetor); 
 var ind: T_Dominio;
 begin 
 for ind:= 1 to N do
 writeln(output, ’Elemento[’, Ind, ’]= ’, V[ind])
 end;
. . .
Begin 
 Ler(Numeros);
 Ordenar(Numeros);
 Escrever(Numeros);
End. 
31
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Vetor:
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
32
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Posição
Vetor:
Menor
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
33
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Posição
Vetor:
Menor
1 2 3 4 5 6 7 8 9 10
1 19 4 10 18 6 8 7 3 12
34
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Vetor:
Posição
Menor
1 2 3 4 5 6 7 8 9 10
1 19 4 10 18 6 8 7 3 12
35
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Vetor:
Posição
Menor
1 2 3 4 5 6 7 8 9 10
1 3 4 10 18 6 8 7 19 12
36
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Vetor:
Posição
Menor
1 2 3 4 5 6 7 8 9 10
1 3 4 10 18 6 8 7 19 12
37
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Vetor:
Posição
1 2 3 4 5 6 7 8 9 10
1 3 4 10 18 6 8 7 19 12
Menor
38
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Vetor:
Posição
1 2 3 4 5 6 7 8 9 10
Menor
1 3 4 6 18 10 8 7 19 12
39
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Vetor:
Posição
1 2 3 4 5 6 7 8 9 10
Menor
1 3 4 6 7 8 10 12 19 18
40
Ordenação pelo Método da Seleção
 Para cada posição i do vetor, o algoritmo procura 
pelo i-ésimo menor elemento e o coloca na posição i.
Vetor:
Posição
1 2 3 4 5 6 7 8 9 10
Menor
1 3 4 6 7 8 10 12 18 19
41
Procedure Ordenar(Var V{e/s}: T_Vetor);
 Procedure Trocar(Var A{e/s}, B{e/s}: integer)
 begin
 end; 
 Procedure SelecionarMenor(V{e}: T_Vetor; 
 Inicio{e}: T_Dominio;
 Var Local{s}: T_Dominio)
 begin
 end; 
var ind: T_Dominio;
 begin {Método da Seleção}
 for ind:= 1 to N-1 do
 begin
 SelecionarMenor(V, Ind, Posicao);
 Trocar(V[ind],V[Posicao]); 
 end;
end;
42
Procedure Ordenar(Var V{e/s}: T_Vetor);
 Procedure Trocar(Var A{e/s}, B{e/s}: integer)
 var temp: integer;
 begin
 temp := A;
 A := B;
 B := temp;
 end; 
 Procedure SelecionarMenor(V{e}: T_Vetor; Inicio{e}: T_Dominio;
 Var Local{s}: T_Dominio)
 var ind: T_Dominio;
 begin 
 Local := Inicio;
 for Ind := Inicio+1 to N do
 if V[ind] < V[Local] then
 Local := Ind 
 end; 
. . . 
begin {Método da Seleção}
end;
43
Ordenação pelo Método da Seleção
 No algoritmo anterior, há basicamente dois 
comandos for-do aninhados. 
 O mais externo executa, para cada elemento do 
vetor, comparações com os elementos seguintes e em 
seguida uma troca. Desta forma, aproximadamente 
N*(N-1)/2 elementos são acessados. 
 Ou seja, o número de elementos avaliados é da 
ordem de N2. Portanto sua complexidade é O(N2 ).
44
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
45
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
7 < 19
Primeira Iteração
46
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
19 > 4
Primeira Iteração
47
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
19 > 4
Primeira Iteração
7 4 19 10 18 6 8 1 3 12
48
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Primeira Iteração
7 4 19 10 18 6 81 3 12
19 > 10
49
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Primeira Iteração
7 4 10 19 18 6 8 1 3 12
19 > 10
50
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Primeira Iteração
19 > 12
7 4 10 18 6 8 1 3 19 12
51
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Primeira Iteração
19 > 12
7 4 10 18 6 8 1 3 12 19
52
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Segunda Iteração
7 4 10 18 6 8 1 3 12 19
7 > 4
53
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Segunda Iteração
4 7 10 18 6 8 1 3 12 19
7 > 4
54
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Segunda Iteração
4 7 10 18 6 8 1 3 12 19
7 < 10
55
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Segunda Iteração
4 7 10 18 6 8 1 3 12 19
10 < 18
56
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Segunda Iteração
4 7 10 18 6 8 1 3 12 19
18 > 6
57
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Segunda Iteração
18 > 6
4 7 10 6 18 8 1 3 12 19
58
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Segunda Iteração
4 7 10 6 8 1 3 18 12 19
18 > 12
59
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Segunda Iteração
4 7 10 6 8 1 3 12 18 19
18 > 12
60
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Oitava Iteração
4 1 3 6 7 8 10 12 18 19
4 > 1
61
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Oitava Iteração
1 4 3 6 7 8 10 12 18 19
4 > 1
62
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Oitava Iteração
1 4 3 6 7 8 10 12 18 19
4 > 3
63
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor:
1 2 3 4 5 6 7 8 9 10
Oitava Iteração
1 3 4 6 7 8 10 12 18 19
4 > 3
64
Ordenação pelo Método da Bolha
 Esta estratégia executa N-1 iterações. Em cada 
uma delas, percorre todo o vetor comparando cada par 
de elementos V[i] e V[i+1] e trocando-os de posição 
caso V[i] > V[i+1].
Vetor: Nona (última) Iteração
1 < 3
1 2 3 4 5 6 7 8 9 10
1 3 4 6 7 8 10 12 18 19
65
Procedure Ordenar(Var V{e/s}: T_Vetor);
 Procedure Trocar(Var A{e/s}, B{e/s}: integer)
 var temp: integer;
 begin
 temp := A;
 A := B;
 B := temp;
 end; 
 
var ind1, ind2: T_Dominio;
 begin {Método da Bolha}
 for ind1 := N-1 downto 1 do
 for ind2 := 1 to ind1 do 
 if V[ind2] > V[ind2+1] then 
 Trocar(V[ind2],V[ind2+1]); 
end;
66
Ordenação pelo Método da Bolha
 Novamente, neste algoritmo, há basicamente dois 
comandos for-do aninhados. 
 O mais externo, executado N-1 vezes, representa as 
iterações. Na i-ésima iteração, N-i comparações são feitas. 
Como no algoritmo anterior, aproximadamente N*(N-1)/2 
comparações são realizadas. 
 Desta forma, o custo computacional do método da 
bolha também é da ordem de N2. Portanto sua 
complexidade é O(N2).
67
Outra Implementação do Método da Bolha
 Nesta implementação, o algoritmo pára 
na primeira iteração em que não houver 
nenhuma troca.
 
 No pior caso, N iterações serão 
realizadas, o que não muda a complexidade
de pior caso do algoritmo.
68
Executável
Código Fonte
Procedure Ordenar(Var V{e/s}: T_Vetor);
 Procedure Trocar(Var A{e/s}, B{e/s}: integer)
 begin ... end;
var ind1, ind2: integer;
 troquei: boolean; 
begin {Outra implementação - Método da Bolha}
 ind1 := N;
 repeat
 troquei := false;
 for ind2 := 1 to ind1-1 do 
 if V[ind2] > V[ind2+1] then
 begin 
 Trocar(V[ind2],V[ind2+1]); 
 troquei := true;
 end;
 ind1 := ind1 - 1
 until not troquei
end;
69
Ordenação pelo Método da Partição ("Quicksort")
 Trata-se de um método de ordenação eficiente e 
de natureza recursiva.
 Em cada ativação do algoritmo, o vetor V [p..r] 
(recebido como parâmetro) é particionado em dois 
subvetores não vazios V[p..q] e V[q+1..r], tais que todo 
elemento de V[p..q] é menor ou igual a todo elemento de 
V[q+1..r]. O índice q é identificado em cada ativação.
 Os subvetores V[p..q] e V[q+1..r] são ordenados 
por ativações recursivas do algoritmo.
 Quando todos os subvetores tiverem tamanho 1,
o vetor original estará ordenado.
70
Ordenação pelo Método Quicksort
Vetor:
7 19 4 10 18 6 8 1 3 12
Início Fim
i j
Mediana = V[Início] = 7
1 2 3 4 5 6 7 8 9 100 11
71
Ordenação pelo Método Quicksort
Início Fim
Até que V[i]>=mediana
Vetor:
7 19 4 10 18 6 8 1 312
Mediana = V[Início] = 7
Até que V[j]<=mediana
ji
1 2 3 4 5 6 7 8 9 100 11
72
Ordenação pelo Método Quicksort
Início Fim
Vetor:
7 19 4 10 18 6 8 1 3 12
Mediana = V[Início] = 7
ji
1 2 3 4 5 6 7 8 9 100 11
73
Ordenação pelo Método Quicksort
Início Fim
Vetor:
3 19 4 10 18 6 8 1 7 12
Mediana = V[Início] = 7
ji
1 2 3 4 5 6 7 8 9 100 11
74
Ordenação pelo Método Quicksort
Início Fim
Vetor:
3 19 4 10 18 6 8 1 7 12
Mediana = V[Início] = 7
Até que V[i]>=mediana Até que V[j]<=mediana
i j
1 2 3 4 5 6 7 8 9 100 11
75
Ordenação pelo Método Quicksort
Início Fim
Vetor:
3 19 4 10 18 6 8 1 7 12
Mediana = V[Início] = 7
ji
1 2 3 4 5 6 7 8 9 100 11
76
Ordenação pelo Método Quicksort
Início Fim
ji
Vetor: Mediana = V[Início] = 7
3 1 4 10 18 6 8 19 7 12
1 2 3 4 5 6 7 8 9 100 11
77
Ordenação pelo Método Quicksort
Início Fim
Vetor: Mediana = V[Início] = 7
3 1 4 10 18 6 8 19 7 12
Até que V[j]<=mediana
j
Até que V[i]>=mediana
i
1 2 3 4 5 6 7 8 9 100 11
78
Ordenação pelo Método Quicksort
Início Fim
ji
Vetor: Mediana = V[Início] = 7
3 1 4 10 18 6 8 19 7 12
1 2 3 4 5 6 7 8 9 100 11
79
Ordenação pelo Método Quicksort
Início Fim
ji
Vetor: Mediana = V[Início] = 7
3 1 4 6 18 10 8 19 7 12
1 2 3 4 5 6 7 8 9 100 11
80
Ordenação pelo Método Quicksort
Início Fim
ji
Vetor: Mediana = V[Início] = 7
3 1 4 6 18 10 8 19 7 12
Até que V[i]>=mediana Até que V[j]<=mediana
1 2 3 4 5 6 7 8 9 100 11
81
Ordenação pelo Método Quicksort
Início Fim
ij
Vetor: Mediana = V[Início] = 7
3 1 4 6 18 10 8 19 7 12
Dado que j < i, encerra-se esta
ativação. Em seguida ativa-se 
recursivamente o algoritmo para
os vetores V[1,j] e V[j+1,10].
1 2 3 4 5 6 7 8 9 100 11
82
Ordenação pelo Método Quicksort
Início Fim
ij
Vetor: Mediana = V[Início] = 7
3 1 4 6 18 10 8 19 7 12
Observe que todos os elementos 
em V[1,j] são menores do que 
todos os elementos em V[j+1,10].
1 2 3 4 5 6 7 8 9 100 11
83
Program Ordena (input{teclado}, output{vídeo});
. . .
Procedure QuickSort(Var V{e/s}: T_Vetor; Inicio, Fim {e}: integer);
 Function Particiona(Var V{e/s}: T_Vetor; Inicio, Fim{e}: integer): integer;
 begin
 end;
begin
 if Inicio < Fim then
 begin
 Meio := Particiona(V,Inicio,Fim);
 QuickSort(V,Inicio,Meio);
 QuickSort(V,Meio+1,Fim)
 end
end;
. . .
Begin 
 Ler(Numeros);
 QuickSort(Numeros, 1, N);
 Escrever(Numeros);
End. 
84
Function Particiona(Var V{e/s}: T_Vetor; Inicio, Fim: integer): integer;
 Procedure Trocar(Var A{e/s}, B{e/s}: integer)
 begin ... end;
 var Mediana, i, j: integer;
begin
 Mediana := V[Inicio];
 i := Inicio - 1;
 j := Fim + 1;
 while i < j do
 begin
 repeat j := j - 1 until V[j] <= Mediana;
 repeat i := i + 1 until V[i] >= Mediana;
 if i < j then 
 Trocar(V[i],V[j])
 else
 Particiona := j 
 end
end;
85
Ordenação pelo Método Quicksort
 No pior caso, este algoritmo executará aproximadamente 
N*(N-1)/2 comparações. Isto acontecerá quando a escolha da mediana 
gerar sempre dois subvetores, sendo um deles com apenas um 
elemento (a mediana) e o outro subvetor com os demais elementos
Portanto, também se trata de um algoritmo O(N2).
 Porém, o Quicksort é um algoritmo mais eficiente do que os demais 
apresentados, pois, na média, executará N*log2(N), onde o fator log2(N) 
se deve a divisão recursiva do vetor original.
86
Aula 8
Professores:
Dante Corbucci Filho
Alexandre Plastino
Conteúdo:
- Busca pela Moda
- Algoritmos de Ordenação
 - Método da Seleção
 - Método da Bolha
 - Método da Partição ("Quicksort")
- Noções de Complexidade de Algoritmos