VA Analise Algoritmos 06

Prévia do material em texto

Aula 6
Métodos de ordenação
Análise de Algoritmos
Gisele Alves Santana
Nesta aula, você vai:
§ Conhecer as técnicas de ordenação
• Ordenação por inserção;
• Ordenação por seleção;
• Ordenação Quicksort.
Resumo da aula
Ordenar
§ Ato de se colocar os elementos em uma 
sequência que possui uma relação de 
ordem entre si e de acordo com um 
critério pré-estabelecido. 
Alguns tipos de algoritmos de ordenação:
§ Seleção;
§ Bolha (Bubble Sort);
§ Torneio (Quick Sort).
Métodos de ordenação
Ideia:
§ Percorrer o vetor, da primeira à última posição, 
em busca do menor ou maior elemento e 
colocá-lo na primeira posição;
§ Em seguida, a busca começa na segunda posição 
e percorre o resto do vetor à procura do próximo 
menor ou maior elemento e coloca-o 
na segunda posição;
§ Assim sucessivamente 
até a última posição.
Seleção direta
Pseudocódigo
Seleção direta
Exemplo:
Seleção direta
Análise da complexidade
Uma troca (no máximo) para cada valor de “i”. 
Se o vetor já se encontra ordenado, então não 
ocorre nenhuma troca
§ V(n) = 0.
Seleção direta
Uma troca exige três movimentos.
Para cada iteração do comando de repetição 
que possui o índice “k”, se existir uma troca, 
no pior caso: 
§ V(n) = 3 (n-1).
Seleção direta
Continuando...
Métodos de ordenação
Considerado um método estável. 
Deixa os registros com chaves iguais na 
mesma posição relativa. 
A cada iteração, o i-ésimo elemento de 
um vetor é transferido para a sequência 
destino, na posição correta. 
A inserção do elemento é realizada 
movendo-se os elementos com 
valores maiores para a direita e 
inserindo o elemento na 
posição que ficou vazia. 
Ordenação por inserção
Como critério de parada do processo, 
tem-se dois casos: 
§ Quando um elemento com menor valor que o 
elemento em consideração é encontrado;
§ Quando o final da sequência destino é 
atingido (à esquerda). 
Ordenação por inserção
Pseudocódigo
Ordenação por inserção
Complexidade
§ Melhor caso: O(n);
§ Pior caso: O(n2);
§ Caso médio: O(n2).
Ordenação por inserção
Finalizando...
Métodos de ordenação
Um dos algoritmos de ordenação mais rápidos. 
Emprega a estratégia de solução de problemas 
“dividir para conquistar”. 
Divide uma lista em duas sub listas a partir de um 
elemento central, chamado pivô. 
Em seguida, realiza o mesmo procedimento nas duas 
listas menores até o caso trivial de uma lista unitária.
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Funcionamento
Quicksort
Algoritmo
Quicksort
Algoritmo quickSort(vetor, inicio, fim) 
Variáveis
i, j, meio, aux: inteiro
Início
i = inicio
j = fim
meio = vetor[(inicio + fim) / 2]
repita
enquanto(vetor[i] < meio)
i++;
enquanto(vetor[j] > meio)
j--;
se(i <= j) então
aux = vetor[i]
vetor[i] = vetor[j]
vetor[j] = aux
i++
j- -
fimse
fimenquanto
enquanto(i <= j)
se(inicio < j) então
quickSort(vetor, inicio, j)
se(i < fim)
quickSort(vetor, i, fim)
} 
Análise da Complexidade
§ Independentemente da quantidade de elementos 
de um vetor, após a primeira partição são realizadas 
(n+1) comparações no máximo. Assim, tem-se: 
• C(n) ≤ (n + 1) + C(n1) + C(n2)
• Onde: n1 + n2 = n – 1
§ O pior caso acontece quando o vetor de entrada 
está ordenado de maneira 
inversa à desejada. 
§ Custo do pior caso:
• C(n) ≤ (n + 1) + n + (n-1) + 
... 3 = ½ (n-1) (n+4)
Quicksort
Análise da Complexidade
§ Desta maneira, tem-se:
• C(n) ≤ ½ (n-1) (n+4) = O(n2)
§ A complexidade do caso médio pode ser 
calculada por: 
• C(n) = (n log n). 
Quicksort
Dúvidas?