Teórica - Ordenação de Vetor

Prévia do material em texto

Curso: Engenharia Civil
Disciplina: Informática 2
Teórica 5 – Ordenação de Vetores 
Professor Ivandro José de Freitas Rocha
E-mail: Ivandro_rocha@yahoo.com.br
APLICAÇÕES
 Em vários momentos do dia a dia, o homem depara-se com a necessidade de
consultar dados ordenados. Por isso uma das atividades mais utilizada na
computação é a ordenação.
2
"Primeiro coloque os números em ordem.
Depois vamos decidir o que fazer."
Teórica 5 – Ordenação de Vetores 
APLICAÇÕES
 Ordenar corresponde ao processo de rearranjar um conjunto de objetos em
ordem ascendente ou descendente.
 O objetivo principal da ordenação é facilitar a recuperação posterior de itens
do conjunto ordenado.
...A atividade de colocar as coisas em ordem está presente na maioria das 
aplicações em que os objetos armazenados têm de ser pesquisados e 
recuperados...
3 Teórica 5 – Ordenação de Vetores 
MÉTODOS DE ORDENAÇÃO
 Ordenação por troca:
 Método da bolha (BubbleSort)
 Método da troca e partição (QuickSort)
 Ordenação por inserção:
 Inserção direta (InsertSort)
 Incrementos decrescentes (ShellSort)
 Ordenação por seleção:
 Seleção direta (SelectSort)
 Seleção em árvore (HeapSort)
4 Teórica 5 – Ordenação de Vetores 
BubbleSort
 É o método mais simples em termos de implementação, porém é o menos
eficiente.
 A ideia principal do algoritmo é percorrer o vetor n-1 vezes, a cada
passagem fazendo “flutuar” para o inicio o menor elemento da sequência.
 Essa movimentação lembra a forma como as bolhas procuram seu próprio
nível, por isso o nome do algoritmo.
 Não é recomendado para vetores com muitos elementos.
5 Teórica 5 – Ordenação de Vetores 
BubbleSort Vídeo
 Vídeo
6 Teórica 5 – Ordenação de Vetores 
BubbleSort.wmv
Pseudocódigo
1. sub-rotina BUBBLE_SORT (v[], tamanho numérico)
2. declare k, i, j, aux numérico
3. k  tamanho - 1
4. para i  1 até tamanho faça
5. início
6. j  1
7. enquanto j <= k faça
8. início
9. se v[ j ] > v[ j + 1]
10. então início
11. aux  v[ j ]
12. v[ j ]  v[ j + 1 ]
13. v[ j + 1 ]  aux
14. fim
15. j  j + 1
16. fim
17. k  k - 1
18. fim
19.fim sub-rotina
Teórica 5 – Ordenação de Vetores 7
BubbleSort
8 Teórica 5 – Ordenação de Vetores 
BubbleSort
Vantagens Desvantagens
- Fácil Implementação; - O fato de o arquivo já estar 
ordenado não ajuda em nada;
-Algoritmo Estável; - Ordem de complexidade 
quadrática;
9 Teórica 5 – Ordenação de Vetores 
InsertSort
 InsertSort é um algoritmo elementar de ordenação.
 É eficiente quando aplicado à um vetor com poucos elementos.
 Em cada passo, a partir de i = 2, o i-ésimo item da sequência fonte é
apanhado e transferido para a sequência destino, sendo inserido no seu
lugar apropriado.
 O algoritmo assemelha-se com a maneira que os jogadores de cartas
ordenam as cartas na mão em um jogo.
10 Teórica 5 – Ordenação de Vetores 
InsertSort Vídeo
 Vídeo
11 Teórica 5 – Ordenação de Vetores 
InsertSort.wmv
12
1. sub-rotina INSERTION_SORT (v[], tamanho numérico)
2. declare i, j, eleito numérico
3. para i  2 até tamanho faça
4. início 
5. eleito  v[ i ]
6. j  i - 1
7. enquanto j > 0 e eleito < v[ j ] faça
8. início
9. v[ j + 1 ]  v[ j ]
10. j  j - 1
11. fim
12. v[ j + 1 ]  eleito
13. fim
14.fim sub-rotina
Pseudocódigo
Teórica 5 – Ordenação de Vetores 
InsertSort
13 Teórica 5 – Ordenação de Vetores 
InsertSort Exemplo
14 Teórica 5 – Ordenação de Vetores 
InsertSort
Vantagens Desvantagens
- Fácil Implementação - Número grande de 
movimentações
- Algoritmo Estável - Ordem de complexidade 
quadrática
- O vetor já ordenado favorece 
a ordenação
- Ineficiente quando o vetor 
está ordenado inversamente;
15 Teórica 5 – Ordenação de Vetores 
SelectSort
 Tem como princípio de funcionamento selecionar o menor item do vetor e a
seguir trocá-lo pela primeira posição do vetor. Isto ocorre para os n-1
elementos restantes, depois com os n-2 itens, até que reste apenas um
elemento.
 A principal diferença deste método em relação aos dois já apresentados é que
ele realiza apenas uma troca por iteração.
16 Teórica 5 – Ordenação de Vetores 
SelectSort Vídeo
 Vídeo
17 Teórica 5 – Ordenação de Vetores 
Select-Sort.wmv
18
1. subrotina SELECTION_SORT (v[], tamanho numérico)
2. declare i, j, menor, aux numérico
3. para i  1 até tamanho -1 faça
4. início
5. menor  i
6. para j  i + 1 até tamanho faça
7. se v[ menor ] > v[ j ] 
8. então menor  j
9. se menor ≠ i
10. então início
11. aux  v[ menor ]
12. v[ menor ]  v[ i ]
13. v[ i ]  aux
14. fim
15. fim 
16.fim subrotina
Pseudocódigo
Teórica 5 – Ordenação de Vetores 
SelectSort Exemplo
19 Teórica 5 – Ordenação de Vetores 
SelectSort
Vantagens Desvantagens
- Fácil Implementação - O fato de o arquivo já estar 
ordenado não influencia em 
nada
- Pequeno número de 
movimentações 
- Ordem de complexidade 
quadrática
- Interessante para arquivos 
pequenos 
- Algoritmo não estável
20 Teórica 5 – Ordenação de Vetores 
ShellSort
 O algoritmo de inserção troca itens adjacentes quando está procurando o
ponto de inserção na sequência destino.
 De maneira geral ele passa várias vezes no vetor dividindo-o em vetores
menores, e nestes são aplicados o algoritmo de ordenação por inserção
tradicional.
21 Teórica 5 – Ordenação de Vetores 
ShellSort Vídeo
 Vídeo
22 Teórica 5 – Ordenação de Vetores 
Shell-sort.wmv
23
1. subrotina SHELL_SORT(v[], tamanho numérico)
2. declare i, j, valor, gap numérico
3. gap  1
4. enquanto gap < tamanho faça
5. gap  3 * gap + 1
6. enquanto gap > 1 faça
7. início
8. gap  gap / 3
9. para i  gap até tamanho faça
10. início
11. valor  v[ i ]
12. j  i - gap
13. enquanto j >= 0 e valor < v[ j ] faça
14. início
15. v[ j + gap ]  v[ j ]
16. j  j - gap
17. fim
18. v[ j + gap ]  valor
19. fim
20. fim
21. fim subrotina
Pseudocódigo
Teórica 5 – Ordenação de Vetores 
ShellSort
Vantagens Desvantagens
- Código Simples; - Algoritmo não estável;
- Interessante para arquivos de
tamanho moderado;
- Tempo de execução sensível à 
ordem inicial do arquivo;
24 Teórica 5 – Ordenação de Vetores 
QuickSort
 É o algoritmo mais rápido que se conhece entre os de ordenação interna para
uma ampla variedade de situações.
 Em raras instâncias especiais ele é lento.
 Adotando a estratégia Dividir para conquistar o funcionamento resume-se a
dividir o problema de ordenar um vetor de n posições em dois outros
menores.
25 Teórica 5 – Ordenação de Vetores 
QuickSort
 O QuickSort é considerado o método mais eficiente e é altamente
recomendável para arquivos grandes.
 Quanto mais o vetor estiver desordenado, maior será sua vantagem em
relação aos outros métodos.
 A escolha correta do pivô é essencial para a garantia de eficiência do
algoritmo.
26 Teórica 5 – Ordenação de Vetores 
QuickSort Vídeo
 Vídeo
27 Teórica 5 – Ordenação de Vetores 
Quick Sort.wmv
28
1. subrotina QUICK_SORT(v[], iniv, fimv numérico)
2. declare i, j, pivo, aux numérico
4. i  iniv
5. j  fimv
6. pivo  v[ (iniv + fimv) / 2 ]
7. enquanto i < j
8. início
9. enquanto v[ i ] < pivo faça
10. i  i + 1
11. enquanto v[ j ] > pivo faça
12. j  j – 1
13. se i <= j
14. então início
15. aux  v[ i ]
16. v[ i ]  v[ j ]
17. v[ j ]  aux
18. i  i + 1
19. j  j – 1
20. fim
21. fim
22. se j > iniv
23. então QUICK_SORT( v, iniv, j )
24. se i < fimv
25. então QUICK_SORT( v, i, fimv )
26. fim subrotina
Pseudocódigo
Teórica 5 – Ordenação de Vetores 
QuickSort Exemplo
29 Teórica 5 – Ordenação de Vetores 
QuickSort
Vantagens Desvantagens
- Extremamente Eficiente ; - Tem um pior caso de O(n2);
- Necessita apenas de um 
pequena pilha
como memória extra;
- Implementação difícil;
- Complexidade n log n ; - Não é estável;
30 Teórica 5 – Ordenação de Vetores 
HeapSort
 Utilizando o mesmo princípio do SelectSort, o HeapSort é um algoritmo que
utiliza uma estrutura de dados conhecidacomo Heap binário para manter o
próximo item a ser selecionado.
31 Teórica 5 – Ordenação de Vetores 
32
1. subrotina HEAP_SORT(v[], tamanho numérico)
2. declare i, pai, filho, t numérico
3. i  tamanho / 2
4. repita
5. se i > 0 
6. então início
7. i  i - 1 
8. t  V[ i ]
9. fim 
10. senão início
11. tamanho  tamanho - 1 
12. se tamanho = 0
13. então interrompa
14. t  v[ tamanho ] 
15. v[ tamanho ]  v[ 0 ] 
16. fim
17. pai  i
18. // Primeiro será feita a comparação com o filho da 
esquerda.
19. filho  i * 2
20. enquanto filho < n
21. início
22. // Se o filho da esquerda for menor do que o filho da 
direita, então será feita a troca do filho que será 
comparado. 
23. se filho + 1 < tam e v[ filho + 1] > v[ filho ]
24. então filho  filho + 1 
25. se v[ filho ] > t
26. então início
27. v[ pai ]  v[ filho ]
28. pai  filho
29. filho  pai * 2 + 1
30 fim
31. senão interrompa
32. fim
33. v[ pai ]  t
34. fim
35. fim subrotina
Pseudocódigo
Teórica 5 – Ordenação de Vetores 
HeapSort
33 Teórica 5 – Ordenação de Vetores 
HeapSort Exemplo
34 Teórica 5 – Ordenação de Vetores 
HeapSort
Vantagens Desvantagens
- Tempo n log n; - O anel interno do algoritmo é 
bastante
complexo se comparado ao 
Quicksort;
- Não é estável;
35 Teórica 5 – Ordenação de Vetores