Informática na Educaçã
[email protected]
[email protected]
Ordenação
Arranjo de uma série de itens similares em ordem crescente ou
decrescente
Seja uma lista ordenada L de n itens
Cada item é denominado registro (em linguagem C, struct)
Possibilidade de associação de uma chave (c[k]) a cada registro
(r[k])
rangel}@dsc.ufcg.edu.br
Condição de ordenação da lista pela chave
Se j precedendo k implicar c[j] < c[k] (ou c[j] > c[k]) em
alguma ordenação nas chaves
rangel}@dsc.ufcg.edu.br
Ordenação em C III
Categorias Genéricas de Algoritmos
Algoritmos para a ordenação de matrizes (Memória/ Arquivos de
acesso direto em discos)
Algoritmos para a ordenação de arquivos seqüenciais (Disco/
Fita)
rangel}@dsc.ufcg.edu.br
Troca (e.g. bubblesort, quicksort)
Avaliação de Algoritmos de Ordenação - Critérios Gerais
Velocidade de ordenação das informações no melhor caso, no caso
médio e no pior caso
Comportamento do algoritmo (natural ou não natural )
Capacidade de rearranjo de elementos com chaves iguais
rangel}@dsc.ufcg.edu.br
Ordenação por troca
Repetição de comparações e, caso necessária, troca de itens
adjacentes
Método mais conhecido (e difamado)
Idéia Básica
Permuta de itens entre posições consecutivas
“Borbulhamento” de valores mais elevados (ou mais baixos) para o
final (ou para o início) do arranjo
rangel}@dsc.ufcg.edu.br
Ordenação Borbulhante (Bubble Sort) II
Considere-se i um vetor de inteiros do qual os n primeiros itens
devam ser ordenados de modo que i[j] ≤ i[k] para 0 ≤ i < j <
n
Fundamentação do método
Percurso seqüencial da lista de itens sucessivas vezes
Comparação de cada item com seu sucessor (i[k] com i[k+1])
Troca dos itens, caso não estejam na ordem correta
rangel}@dsc.ufcg.edu.br
13, 5, 1, 0, 3, 2, 8, 1
1ª I T E R A Ç Ã O
Comparação
Antes
Depois
Troca
13 e 5
5 e 13
13 e 1
1 e 13
13 e 0
1 e 13
13 e 3
3 e 13
13 e 2
3 e 13
13 e 8
8 e 13
13 e 1
1 e 13
5, 1, 0, 3, 2, 8, 1, 13
2ª I T E R A Ç Ã O
Comparação
Antes
Depois
Troca
5 e 1
1 e 5
5 e 0
0 e 5
5 e 3
3 e 5
5 e 2
2 e 5
5 e 8
5 e 8
8 e 1
1 e 8
8 e 13
8 e 13
Exercício 01
Construir o quadro com todas as iterações necessárias à ordenação
de todo a seqüência de inteiros do Exemplo 01
rangel}@dsc.ufcg.edu.br
Ordenação Borbulhante (Bubble Sort) VI
Constatação Após a 1ª iteração, o maior elemento assume a posição
correta
Em geral, i[n-k] assumirá a posição correta após a iteração k
Simplicidade algorítmica x Velocidade de processamento
Uma das piores formas de ordenação
rangel}@dsc.ufcg.edu.br
Algoritmo 01
if (i [k-1] > i[k]){
auxi = i[k-1];
Algoritmo 02
if (item [k-1] > item[k]){
auxi = item[k-1];
Exercício 02
Comparar as funções apresentadas nos slides 13 e 14 e
responder:
Ambas podem ser empregadas indistintamente? Justificar a
resposta.
Empregar cada uma das funções comparadas em uma aplicação
prática.
rangel}@dsc.ufcg.edu.br
Exercício 03
Analisar o código apresentado no slide 17 se a string de caracteres
digitada for
Este eh apenas um teste de Borbulhante02
rangel}@dsc.ufcg.edu.br
rangel}@dsc.ufcg.edu.br
Considerações Finais
Número de trocas no melhor caso 0
Número de trocas no caso médio ¾ (n2 – n)
Número de trocas no pior caso 3/2 (n2 – n)
rangel}@dsc.ufcg.edu.br
Exercício 04
Analisar o código apresentado no slide 20 e compará-lo com o código
do slide 14
rangel}@dsc.ufcg.edu.br
Exercício 05
Analisar o processo de ordenação do Exemplo 01 empregando o
algoritmo apresentado no slide 20
rangel}@dsc.ufcg.edu.br
Primeira iteração
Identificação do maior valor e permuta com o último item da
seqüência
Posicionamento correto do maior item
rangel}@dsc.ufcg.edu.br
Segunda iteração
Varredura apenas dos n-1 itens da seqüência e permuta do maior
deles com o item ocupante da posição n-1
Posicionamento correto dos dois maiores itens
rangel}@dsc.ufcg.edu.br
Ordenação da seqüência inteira após n iterações
Variante simples Identificação do menor item a cada iteração e seu
reposicionamento na porção inicial da seqüência de itens
rangel}@dsc.ufcg.edu.br
int k, j;
int min, auxi;
min = i;
if (i[j] < i[min])
min = j;
Exercício 06
Analisar o processo de ordenação do Exemplo 01 empregando o
algoritmo apresentado no slide 25
rangel}@dsc.ufcg.edu.br
Número de trocas no melhor caso 3(n-1)
Número de trocas no caso médio n(ln n + y)
y 0,577216 Constante de Euler
Número de trocas no pior caso ¼n2 + 3(n - 1)
rangel}@dsc.ufcg.edu.br
Ordenação dos 2 primeiros itens da seqüência
Inserção do 3º item na sua posição ordenada com relação aos 2
primeiros
Inserção do 4º item na lista dos 3 elementos
Prosseguimento até a ordenação de todos os elementos
rangel}@dsc.ufcg.edu.br
int k, j, chave;
chave = i[k];
i[j] = i[j-1];
Exercício 07
Analisar o processo de ordenação do Exemplo 01 empregando o
algoritmo apresentado no slide 29
rangel}@dsc.ufcg.edu.br
Comportamento natural
Menor carga de trabalho quando os itens já se encontram
ordenados
Máxima carga de trabalho quando a lista está ordenada no sentido
inverso
Não rearranjo de itens de mesma chave
Uma lista ordenada por duas chaves permanecerá ordenada para ambas
as chaves após a ordenação
rangel}@dsc.ufcg.edu.br
Lista em ordem ½(n2 – n ) - 1
Número de trocas no melhor caso 2(n – 1)
Número de trocas no caso médio ¼(n2 + 9n -10)
Número de trocas no pior caso ½(n2 +3n - 4)
rangel}@dsc.ufcg.edu.br
Ordenação em C XXXII
Métodos Melhores de Ordenação
Ineficiência de todos os algoritmos estudados até este ponto Tempo
de processamento da ordem de n2
Ordenações lentas para grandes listas (n > 100)
Solução
rangel}@dsc.ufcg.edu.br
Método de operação freqüentemente associado ao mecanismo de
empilhamento de conchas do mar
Derivação
rangel}@dsc.ufcg.edu.br
Procedimento I
Consideração Inicial
Composição do vetor por vários segmentos, cada um dos quais reúne
os itens que se encontram a uma distância d entre si
Ordenação de cada segmento
Procedimento II
Redução de d e repetição do processo para segmentos nos quais o
intervalo entre itens é menor do que na primeira iteração do
processo
Repetições sucessivas do processo, até que d = 1 (valor obrigatório
para o intervalo na última iteração)
rangel}@dsc.ufcg.edu.br
Definição do valor inicial de d – Exemplo
Ordenação de todos os itens afastados entre si de 3 posições
Ordenação de todos os itens afastados entre si de 2 posições
Finalmente, ordenação de todos os itens adjacentes
rangel}@dsc.ufcg.edu.br
45, 23, 4, 9, 6, 7, 91, 8, 12, 25
45
23
4
9
6
7
91
8
12
25
9
25
45
91
6
8
23
4
7
12
9
6
4
25
8
7
45
23
12
91
4
8
9
12
45
6
7
23
25
91
4
6
8
7
9
23
12
25
45
91
4
6
7
8
9
12
23
25
45
91
f, d, a, h, j, b, g, c, e, i
f
d
a
h
j
b
g
c
e
i
f
g
h
i
d
c
j
a
b
e
f
d
a
g
c
b
h
j
e
i
a
c
e
f
h
b
d
g
i
j
a
b
c
d
e
g
f
i
h
j
a
b
c
d
e
f
g
h
i
j
f, d, a, h, j, b, g, c, e, i
rangel}@dsc.ufcg.edu.br
for(d= n/2; d > 0; d = d/2)
for(i = d; i < n; i++)
for(j = i - d; j >= 0 && i[j] > i[j+d]; j = j -
d){
auxi = i[j];
i[j+d] = auxi;
rangel}@dsc.ufcg.edu.br
Considerações Iniciais I
Superior aos demais métodos de ordenação Algoritmo de ordenação
mais rápido conhecido na prática (métodos de ordenação baseados em
endereços podem ser mais rápidas)
Concepção C. A. R. Hoare, em 1962
Idéia Básica Divisão para conquista
rangel}@dsc.ufcg.edu.br
Considerações Iniciais II
Fundamentação Método de ordenação por trocas e na idéia de
partições
Seleção de um valor (comparador) e partição da seqüência em duas
seções, com todos os elementos maiores ou iguais ao valor da
partição de um lado e os menores do outro
Repetição do processo para cada seção restante até a ordenação
completa da matriz
rangel}@dsc.ufcg.edu.br
Procedimento Básico
Se o número de itens a ser ordenado for 0 ou 1, retorno da
informação
Caso contrário, consideração de qualquer item da seqüência i[n]
como elemento particionador ou pivô (ip)
Partição da seqüência de itens em 2 conjuntos disjuntos, S1 (i[n] ≤
ip) e S1 (i[n] > ip)
Retorno de QuickSort (S1) seguido de ip e de QuickSort (S2)
rangel}@dsc.ufcg.edu.br
Ordenação em C XLV
Considerando o item central (10) como pivô e particionando a
seqüência conforme o procedimento do slide 45
Ordenando os subconjuntos
5, 1, 4, 2, 10, 3, 9, 15, 12
Recombinando os subconjuntos com o pivô
5
1
4
2
3
9
15
12
1
2
3
4
5
9
10
12
15
1
2
3
4
5
9
10
12
15
5, 1, 4, 2, 10, 3, 9, 15, 12
Partição 1
Partição 2
Partição 3
Partição 4
Lista Ordenada
Exercício 08
Ordenar a seqüência de caracteres do Exemplo 03 (slide 39)
empregando o método Quicksort
rangel}@dsc.ufcg.edu.br
Considerações Finais I
O valor central pode ser escolhido aleatoriamente ou selecionado
através da média de um pequeno conjunto de valores retirado da
matriz
Ordenação ótima Necessidade de seleção de um valor precisamente no
centro da faixa de valores (tarefa difícil)
rangel}@dsc.ufcg.edu.br
Considerações Finais II
Ordenação péssima Posicionamento do valor escolhido em uma
extremidade e, mesmo assim, o quicksort seleciona o elemento
central da matriz
Número médio de comparações nlog(n)
Número médio de trocas (aproximado) n/6 log(n)
rangel}@dsc.ufcg.edu.br
Velocidade de processamento dos dados
Ordenação de listas de dados muito pequenas (n < 100)
Comprometimento da eficiência do método Tempo extra das chamadas
recursivas
Sugestão Ordenação borbulhante
Fornecimento da função qsort() pela maioria dos compiladores (parte
da biblioteca padrão)
Impossibilidade de aplicação de uma função generalizada a todas as
situações
Parametrização de qsort() para operação sobre uma variedade de
dados
Execução mais lenta do que a de um algoritmo de ordenação
semelhante operando apenas sobre um tipo de dados
rangel}@dsc.ufcg.edu.br
Ordenação de Strings I
Estratégia Vantajosa
Criação de uma matriz de apontadores e caracteres para as
strings
Possibilidade de indexação fácil
rangel}@dsc.ufcg.edu.br
Ordenação de Strings II
Exercício 09
Analisar e descrever o código apresentado nos slides 56 e 57
rangel}@dsc.ufcg.edu.br
void qs_string(char i[][TAM], int esq, int dir);
void main(void)
printf(“Digite uma string [%d]:", k+1);
gets(s[k]);
for(k = 0; k < N; k++) printf("\n%s", s[k]);
getche();
qs_string(i, 0, cont-1);
register int j, k;
if(k <= j){
}
Ordenação de Arquivos em Disco I
Modos de Acesso a Arquivos em Disco
Seqüencial
Ordenação de Arquivos em Disco II
Arquivos pequenos
Leitura na memória
Ordenação eficiente a partir de algoritmos de ordenação de vetores
(apresentados em slides anteriores)
rangel}@dsc.ufcg.edu.br
Ordenação de Arquivos em Disco III
Arquivos grandes
Adoção de técnicas especiais
Ordenação de Arquivos em Disco IV
Vantagens (acesso aleatório – seqüencial)
Facilidade de manutenção e atualização de informações sem
necessidade de cópia de toda a lista de dados
Possibilidade de tratamento como um grandes vetores (matrizes) no
disco
Simplificação do processo de ordenação
Nota: O tratamento de um arquivo de acesso aleatório como uma
matriz implica a possibilidade de uso do método quicksort com
modificações relativamente simples
rangel}@dsc.ufcg.edu.br
Classes de Algoritmos em função de sua Complexidade I
Constatação de correlação direta entre a complexidade algorítmica e
eficiência relativa do algoritmo
Complexidade Algorítmica
O Complexidade do algoritmo
rangel}@dsc.ufcg.edu.br
Classes de Algoritmos em função de sua Complexidade II
Complexidade Quadrática O(n2)
Complexidade Logarítmica O(nlogn)
Complexidade Quadrática O(n2)
Complexidade Logarítmica O(nlogn)
O qualificativo melhor é função do contexto de uso
Quicksort pode parecer o método mais rápido
Usá-lo em uma lista de 15 itens é como matar um mosquito com uma
bazuca
Necessidade de conhecimento dos diferentes métodos de
ordenação
Escolha do algoritmo mais adequado à resolução do problema de
interesse
rangel}@dsc.ufcg.edu.br
Considerações Finais sobre Algoritmos de Ordenação VI
Os algoritmos da 2ª categoria são indiscutivelmente mais rápidos do
que os da 1ª categoria
Desvantagens
#
#
\
\
\
\
if(item[a-1]>item[a]) {
if(item[a-1]>item[a]) {
}
if(item[a-1]>item[a]) {
if(item[a-1]>item[a]) {
}