Análise de Algoritmos de Ordenação

Prévia do material em texto

Análise de Algoritmos
ANÁLISE DE ALGORITMOS DE ANÁLISE DE ALGORITMOS DE 
ORDENAÇÃOORDENAÇÃO
Bacharelado em Ciência da Computação
Flávia Coelho
flaviacoelho@ufersa.edu.br
Atualizado em Agosto de 2016
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Distribuição e Coleta
 
Motivação
● Ordenar é rearranjar um conjunto de 
objetos em ordem crescente ou 
decrescente
● Facilita posterior recuperação
● Técnicas de ordenação são aplicáveis em 
dicionários, índices, tabelas, arquivos, 
etc...
 
Aspectos de Algoritmos de 
Ordenação
● Algoritmo é in­place 
quando não há 
necessidade de memória 
adicional
● Algoritmo é estável se 
elementos iguais 
ocorrem no vetor 
ordenado na mesma 
ordem em que são 
passados na entrada
ES
TÁ
VE
L
NÃ
O-
ES
TÁ
VE
L
 
Ordenação baseada em 
Distribuição e Coleta
● Vamos ordenar um baralho com 52 cartas 
não ordenadas, considerando a ordem
● A < 2 < 3 < … < 10 < J < Q < K
● ♣ < ♦ < ♥ < ♠ 
● Passo­a­passo
● Distribuir as cartas em 13 montes, por categoria
● Colete os montes na ordem citada
● Distribuir novamente em 4 montes, por categoria
● Coletar os montes na ordem citada
EX
EM
PL
O
A principal dificuldade é lidar 
com cada monte! Para cada 
um, é preciso reservar uma 
área → demanda por 
memória extra pode ser 
tornar proibitiva!
 
Ordenação Baseada em 
Comparações e Trocas
 
Ordenação Interna e Externa
● Interna
● Se o arquivo a ser ordenado couber na 
memória principal
● Externa
● Se o arquivo precisa ser armazenado em 
memória secundária
Principal diferença é que qualquer 
registro pode ser imediatamente 
acessado na memória interna 
enquanto na externa, o acesso é 
sequencial ou em blocos!
 
Aspectos da Ordenação Interna
● Medidas de complexidade
● Quantidade de comparações e de trocas
● Quantidade extra de memória auxiliar 
utilizada
● Classificação
● Simples   O(n→ 2) comparações
● Eficientes   O(nlgn) comparações→
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Ordenação por Bolha
● Ordenação por Seleção
● Ordenação por Inserção
● Ordenação Shell
● Ordenação Heap
● Ordenação por Intercalação
● Ordenação Rápida
● Distribuição e Coleta
 
Algoritmo de Ordenação por Bolha
BubbleSort
bolha(v [], n){
  para (i = 0; i < n; i++)
    para (j = 0; j < n­1; j++)
      se (v[j] > v[j+1]){
        aux = v[j]
        v[j] = v[j+1]
        v[j+1] = aux
      }
}
 
Algoritmo de Ordenação por Bolha
BubbleSort
bolha(v [], n){
  para (i = 0; i < n; i++)
    para (j = 0; j < n­1; j++)
      se (v[j] > v[j+1]){
        aux = v[j]
        v[j] = v[j+1]
        v[j+1] = aux
      }
}
Ω(n²)
Θ(n²)
O(n²)
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Ordenação por Bolha
● Ordenação por Seleção
● Ordenação por Inserção
● Ordenação Shell
● Ordenação Heap
● Ordenação por Intercalação
● Ordenação Rápida
● Distribuição e Coleta
 
Algoritmo de Ordenação por Seleção
SelectionSort
selecao(v [], n){
  para (i = 0; i < n­1; i++){
    menor = i
    para (j = i+1; j < n; j++)
      se (v[j] < v[menor])
        menor = j
    aux = v[i]
    v[i] = v[menor]
    v[menor] = aux
  }
}
 
Algoritmo de Ordenação por Seleção
SelectionSort
selecao(v [], n){
  para (i = 0; i < n­1; i++){
    menor = i
    para (j = i+1; j < n; j++)
      se (v[j] < v[menor])
        menor = j
    aux = v[i]
    v[i] = v[menor]
    v[menor] = aux
  }
}
Ω(n²)
Θ(n²)
O(n²)
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Ordenação por Bolha
● Ordenação por Seleção
● Ordenação por Inserção
● Ordenação Shell
● Ordenação Heap
● Ordenação por Intercalação
● Ordenação Rápida
● Distribuição e Coleta
 
Algoritmo de Ordenação por Inserção
InsertionSort
insercao(v [], n){
  para(i = 1; i < n; i++){
    aux = v[i]
    para (j = i­1; j >= 0 e v[j] > aux; j­­){
      v[j+1] = v[j]
      v[j] = aux
    }
  }
}
 
Algoritmo de Ordenação por Inserção
InsertionSort
insercao(v [], n){
  para(i = 1; i < n; i++){
    aux = v[i]
    para (j = i­1; j >= 0 e v[j] > aux; j­­){
      v[j+1] = v[j]
      v[j] = aux
    }
  }
}
Ω(n)
Θ(n²)
O(n²)
ENTRADA NA 
ORDEM DESEJADA
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Ordenação por Bolha
● Ordenação por Seleção
● Ordenação por Inserção
● Ordenação Shell
● Ordenação Heap
● Ordenação por Intercalação
● Ordenação Rápida
● Distribuição e Coleta
 
Algoritmo de Ordenação Shell
ShellSort
● Efetua a troca de elementos que estão 
distantes um do outro até h posições
Proposta [EXEMPLO]
h(n) = 3h(n – 1) + 1, para n > 1
h(n) = 1, para n = 1
A sequência para h é 1, 4, 13, 40, ...
 
Algoritmo de Ordenação Shell
ShellSort
shell(v [], n){
  para (h = 1; h < n; h = 3*h + 1) //calcula h inicial
  enquanto(h > 0){
    h = (h ­ 1)/3 //atualiza o valor de h
    para(i = h; i < n; i++){
      aux = v[i]; j = i
      enquanto (b[j ­ h] > aux){
        v[j] = v[j – h]; j = j ­ h
        se (j < h)
          sai
      }
      v[j] = aux
    }  }  }
NINGUÉM FOI CAPAZ DE 
ANALISAR AINDA!
Conjectura 1: O(n1,25)
Conjectura 2: O(n(lnn)²)
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Ordenação por Bolha
● Ordenação por Seleção
● Ordenação por Inserção
● Ordenação Shell
● Ordenação Heap
● Ordenação por Intercalação
● Ordenação Rápida
● Distribuição e Coleta
 
Algoritmo de Ordenação Heap
HeapSort
● Baseado na estrutura de dados Heap
● Um vetor V pode ser visto como uma árvore 
binária, na qual cada nó possui no máximo 2 
filhos
● Cada nó da árvore corresponde a um 
elemento do vetor
● Cada nível é preenchido da direita para a 
esquerda
 
Fundamentos da Heap
● V = {C1, C2, …, Cn} disposto em uma 
árvore binária
● C1 é a raiz da árvore
● C2i   subárvore da esquerda de C→ i
● C2i+1   subárvore da direita de C→ i
● Esquema para o vetor C1...C7, n = 7
C1
C2 C3
C4 C5 C6 C7
 
Heap Máxima
● Trocam­se as chaves de posição dentro 
do vetor, para que formem uma 
hierarquia, na qual todas as raízes das 
subárvores sejam maiores ou iguais a 
qualquer uma das suas sucessoras, ou 
seja, cada raiz deve satisfazer as 
seguintes condições
● Ci  C2i
● Ci  C2i+1
Atenção
HEAP MÍNIMA OMITIDA 
(também pode ser 
considerada!)
 
Construção e Manutenção da Heap
● A primeira subárvore a ser testada é aquela cuja 
raiz é C3, seguindo­se o teste pela subárvore de raiz 
C2 e finalizando com a de raiz C1
● E, sempre que for encontrada uma subárvore que 
não forme um heap, seus componentes devem ser 
rearranjados
C1
C2 C3
C4 C5 C6 C7
n div 2
(7 div 2)
 
heap(v[], n){
  constroiHeap(v[], n)
  ordenacaoHeap(v[], n)
}
Algoritmo de Ordenação Heap
HeapSort
constroiHeap(v[], n){
  para (i = n/2; i >= 1; i­­)
  heapficando(i, n)
}
 
heap(v[], n){
  constroiHeap(v[], n)
  ordenacaoHeap(v[], n)
}
Algoritmo de Ordenação Heap
HeapSort
constroiHeap(v[], n){
  para (i = n/2; i >= 1; i­­)
  heapficando(i, n)
}
EXECUTADO NO 
MÁXIMO h = lgn
Ω(1)
O(lgn)
 
heap(v[], n){
  constroiHeap(v[], n)
  ordenacaoHeap(v[], n)
}
Algoritmo de Ordenação Heap
HeapSort
constroiHeap(v[], n){
  para (i = n/2; i >= 1; i­­)
  heapficando(i, n)
}
Ω(n)
O(nlgn)
 
heap(v[], n){
  constroiHeap(v[], n)
  ordenacaoHeap(v[], n)
}
Algoritmo de Ordenação Heap
HeapSort
ordenacaoHeap(v[], n){
  para(i = n; i >= 2; i­­){aux = v[1]
    v[1] = v[i]
    v[i] = aux
    ultPosicao = i ­ 1
    heapficando(1,ultPosicao)
  }
}
 
heap(v[], n){
  constroiHeap(v[], n)
  ordenacaoHeap(v[], n)
}
Algoritmo de Ordenação Heap
HeapSort
ordenacaoHeap(v[], n){
  para(i = n; i >= 2; i­­){
    aux = v[1]
    v[1] = v[i]
    v[i] = aux
    ultPosicao = i ­ 1
    heapficando(1,ultPosicao)
  }
}
EXECUTADO NO 
MÁXIMO h = lgn
Ω(n)
O(nlgn)
 
heap(v[], n){
  constroiHeap(v[], n)
  ordenacaoHeap(v[], n)
}
Algoritmo de Ordenação Heap
HeapSort
Ω(n)
Θ(nlgn)
O(nlgn)
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Ordenação por Bolha
● Ordenação por Seleção
● Ordenação por Inserção
● Ordenação Shell
● Ordenação Heap
● Ordenação por Intercalação
● Ordenação Rápida
● Distribuição e Coleta
 
Algoritmo de Ordenação por Intercalação
MergeSort
intercalacao(v[], i, f){
  se (i < f){
    m = parteInteira((i+f)/2)
    intercalacao(v, i, m)
    intercalacao(v, m+1, f)
    intercala(v, inicio, fim, meio)
  }    
}
 
Algoritmo de Ordenação por Intercalação
MergeSort
intercalacao(v[], i, f){
  se (i < f){
    m = parteInteira((i+f)/2)
    intercalacao(v, i, m)
    intercalacao(v, m+1, f)
    intercala(v, inicio, fim, meio)
  }    
}
Ω(nlgn)
Θ(nlgn)
O(nlgn)T(n) = 2T(n/2) + O(n)
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Ordenação por Bolha
● Ordenação por Seleção
● Ordenação por Inserção
● Ordenação Shell
● Ordenação Heap
● Ordenação por Intercalação
● Ordenação Rápida
● Distribuição e Coleta
 
Algoritmo de Ordenação Rápida
QuickSort
ordenacaoRapida(v [], p, f){
  se (p < f){ 
    q = particiona(v, p, f)
    ordenacaoRapida(v, p, q)
    ordenacaoRapida(v, q+1, f)
  }
}
 
QuickSort utiliza um Pivô
1. Divisão usando o pivô (p)
2. Recursão2. Recursão
3. Concatenação
(=p)
(>p)(<p)
Fonte: M. T. Goodrich, R. Tamassia. Estrutura de Dados e Algoritmos em Java. Quarta edição, Bookman, 2006
 
Algoritmo de Ordenação Rápida
QuickSort
ordenacaoRapida(v [], p, f){
  se (p < f){ 
    q = particiona(v, p, f)
    ordenacaoRapida(v, p, q)
    ordenacaoRapida(v, q+1, f)
  }
}
particiona(v, p, r)
   pivo = v[(p+r)/2]
   i = p­1; j = r+1
   enquanto (i < j) faça
       repita j = j – 1 
       até (v[j] <= pivo)
       repita i = i + 1
       até (v[i] >= pivo)
       se (i < j) então
          troca(v, i, j)
   retorne j
 
Algoritmo de Ordenação Rápida
QuickSort
ordenacaoRapida(v [], p, f){
  se (p < f){ 
    q = particiona(v, p, f)
    ordenacaoRapida(v, p, q)
    ordenacaoRapida(v, q+1, f)
  }
} T(n) = 2T(n/2) + O(n)
Ω(nlgn)
PIVÔ DIVIDE O TAMANHO DO VETOR 
EXATAMENTE EM DUAS METADES
 
Algoritmo de Ordenação Rápida
QuickSort
ordenacaoRapida(v [], p, f){
  se (p < f){ 
    q = particiona(v, p, f)
    ordenacaoRapida(v, p, q)
    ordenacaoRapida(v, q+1, f)
  }
} T(n) = T(n-1) + O(n)
O(n²)
VETOR JÁ ESTÁ ORDENADO OU NA ORDEM INVERSA À DESEJA 
E O PIVÔ ESCOLHIDO É O MENOR (OU MAIOR) VALOR
 
Algoritmo de Ordenação Rápida
QuickSort
ordenacaoRapida(v [], p, f){
  se (p < f){ 
    q = particiona(v, p, f)
    ordenacaoRapida(v, p, q)
    ordenacaoRapida(v, q+1, f)
  }
} Ω(nlgn)
Θ(nlgn)
O(n²)
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Distribuição e Coleta
● Ordenação por Contagem
● Ordenação Radix
● Ordenação por ’Balde’
 
Algoritmo de Ordenação por Contagem
CoutingSort
contagem(v[], n, m){
  //elementos de v são valores entre 0 e m­1
  para (i = 0; i < m; i++){  //Inicializa vetor auxiliar
    vetorAuxiliar[i] = 0;
  para (i = 0; i < n; i++)   //Contagem das ocorrências
    vetorAuxiliar[v[i]]++;
  sum = 0;   
  para (i = 1; i < m; i++){ //Ordenação dos índices do vetor auxiliar
    dum = vetorAuxiliar[i];
    vetorAuxiliar[i] = sum;
    sum += dum;        
  }
  para(i = 0; i < n; i++){
    vetorOrdenado[vetorAuxiliar[v[i]]] = v[i];
    vetorAuxiliar[v[i]]++;
  }
  para (i = 0; i < v.length; i++)  //copiando os valores ordenados
    v[i] = vetorOrdenado[i]; 
}
Não funciona 
para números 
negativos!
 
Algoritmo de Ordenação por Contagem
CoutingSort
contagem(v[], n, m){
  //elementos de v são valores entre 0 e m­1
  para (i = 0; i < m; i++){  //Inicializa vetor auxiliar
    vetorAuxiliar[i] = 0;
  para (i = 0; i < n; i++)   //Contagem das ocorrências
    vetorAuxiliar[v[i]]++;
  sum = 0;   
  para (i = 1; i < m; i++){ //Ordenação dos índices do vetor auxiliar
    dum = vetorAuxiliar[i];
    vetorAuxiliar[i] = sum;
    sum += dum;            
  }
  para(i = 0; i < n; i++){
    vetorOrdenado[vetorAuxiliar[v[i]]] = v[i];
    vetorAuxiliar[v[i]]++;
  }
  para (i = 0; i < v.length; i++)  //copiando os valores ordenados
    v[i] = vetorOrdenado[i]; 
}
Ω(n + m)
Θ(n + m)
O(n + m)
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Distribuição e Coleta
● Ordenação por Contagem
● Ordenação Radix
● Ordenação por ’Balde’
 
Algoritmo de Ordenação Radix
RadixSort
radix(v [] , d){
  //d indica o número de dígitos
  para (i = 1; i <= d; i++){
    //ordene v pelo i­ésimo dígito
    //usando um método estável
  }
}
Indicado apenas 
para ordenar 
pequenos 
números inteiros!
 
Algoritmo de Ordenação Radix
RadixSort
radix(v [] , d){
  //d indica o número máximo de dígitos
  //dos elementos do vetor
  para (i = 1; i <= d; i++){
    //ordene v pelo i­ésimo dígito
    //usando um método estável
  }
} Θ(d[complexidade do 
método estável de 
ordenação])
 
Sumário
● Fundamentos da Ordenação
● Comparação e Troca
● Distribuição e Coleta
● Ordenação por Contagem
● Ordenação Radix
● Ordenação por ’Balde’
 
Algoritmo de Ordenação por ’Balde’
BucketSort
ordenacaoBucket(v[], n, max){
  para(int i = 0; i < (max + 1); i++)
    bucket[i] = 0
  para(int i = 0; i < n; i++) 
    bucket[v[i]] = bucket[v[i]] + 1
  outPos = 0;
  para(int i = 0; i < (max + 1); i++) 
    para(int j = 0; j < bucket[i]; j++) {
      v[outPos]=i;
      outPos = outPos + 1;
    }
}
 
Algoritmo de Ordenação por ’Balde’
BucketSort
ordenacaoBucket(v[], n, max){
  para(int i = 0; i < (max + 1); i++)
    bucket[i] = 0
  para(int i = 0; i < n; i++) 
    bucket[v[i]] = bucket[v[i]] + 1
  outPos = 0;
  para(int i = 0; i < (max + 1); i++) 
    para(int j = 0; j < bucket[i]; j++) {
      v[outPos]=i;
      outPos = outPos + 1;
    }
}
Ω(n + k)
Θ(n + k)
O(n²)
NÚMERO DE 
BUCKETS
TODOS OS ELEMENTOS 
ESTÃO NO MESMO BUCKET
 
Leitura Recomendada
N. Ziviani. Projeto de Algoritmos com 
Implementações em Java e C++. Thompson 
Learning, 2007, pp. 111­161
M. T. Goodrich, R. Tamassia. Estruturas de 
Dados e Algoritmos em Java. Quarta Edição, 
Bookman, 2006, pp. 431­468
A. F. G. Ascencio, G. S. Araújo. Estruturas de 
Dados. Algoritmos, Análise da Complexidade e 
Implementações em Java e C/C++. Pearson, 
2011, pp. 21­90
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51