ED09 Ordenacao de dados completo

Prévia do material em texto

AMS – ADS 
Estruturas de Dados
Tipos Abstratos de Dados:
manipulação
Algoritmos de Ordenação de Dados
Prof. Eliane Oliveira Santiago
Conteúdo Programático
Ordenação de Dados 
a. Ordenação por troca: 
i. BubbleSort (método da bolha); 
ii. QuickSort (método da troca e partição)
b. Ordenação por seleção: 
i. SelectionSort (método da seleção direta); 
ii. HeapSort (método da seleção em árvore) 
c. Ordenação por inserção: 
i. InsertionSort (método da inserção direta); 
ii. BinaryInsertionSort (método da inserção direta binária)
d. Outros métodos: 
i. MergeSort (método da intercalação); 
ii. BucketSort (método da distribuição de chave) 
iii. Radix
Glossário
Ordenar: processo de reorganizar um 
conjunto de objetos em uma ordem 
ascendente ou descendente, com o objetivo 
de facilitar a recuperação posterior de itens 
do conjunto ordenado.
Complexidade de algoritmos: taxa na qual 
o armazenamento ou tempo de execução 
cresce em função do tamanho dos dados de 
entrada.
Análise Assintótica: a medida em que a 
entrada cresce, a complexidade do 
algoritmo proporcionalmente tende a uma 
função conhecida 
O(n), O(n2), O(2n), O(nn)
O(n log n), O(log n)
Melhor Caso, Pior Caso, Caso Médio
Melhor Caso: [Big-O]
 Propriedade dos dados que resultam no melhor resultado possível
Pior Caso: [Big-omega] 
 Propriedade dos dados que resultam no pior resultado possível
Caso Médio: [Big-theta]
 Obtido fazendo uma media do desempenho do algoritmo atuando 
sobre todos os conjuntos de dados possíveis
Resumo das complexidades
Denominações e Notações
BubbleSort (método da bolha); 
QuickSort (método da troca e partição)
Algoritmos de Ordenação por troca
Técnica basica
1. Comparam-se dois elementos e trocam-se suas posições
se o segundo elemento e menor do que o primeiro
2. Sao feitas varias passagens pela tabela
3. Em cada passagem, comparam-se dois elementos
adjacentes
4. Se estes elementos estiverem fora de ordem, eles são
trocados.
BubbleSort()
O algoritmo BubbleSort()
O algoritmo de ordenação da bolha (bubble sort)
percorre a coleção de elementos trocando a posição
de dois elementos consecutivos cada vez que
estiverem fora de ordem. Ao final de cada iteração,
o elemento maior estará no fim da coleção e pode
ficar fora da próxima rodada; ao mesmo tempo,
elementos menores mover-se-ão em direção ao início
da lista.
Bubble
3 10 10 10 40
2 20 20 40 10
1 30 40 20 20
0 40 30 30 30
3 10 10 10 40 40 40
2 20 20 40 10 10 30
1 30 40 20 20 30 10
0 40 30 30 30 20 20
Bubble
3 10 10 10 40
2 20 20 40 10
1 30 40 20 20
0 40 30 30 30
3 10 10 10 40 40 40 40
2 20 20 40 10 10 30 30
1 30 40 20 20 30 10 20
0 40 30 30 30 20 20 10
1a iteração
2a iteração 3a iteração
BubbleSort
Algoritmo Interativo para Ordenação por Troca, método
BubbleSort (bolha) para ordenação em ordem decrescente
public class Bolha {
public void bubbleSort(int v[]) {
for (int i = v.length; i >= 1; i--) {
for (int j = 1; j v[j]) {
int aux = v[j];
v[j] = v[j - 1];
v[j - 1] = aux;
}
}
}
}
}
1
2
3
4
3
2
1
0
1
2
4
3
1
4
2
3
4
1
2
3
4
1
2
3
4
1
3
2
4
3
1
2
4
3
2
1
4
3
1
2
1
2
3
4
3
2
1
0
1
2
4
3
1
4
2
3
4
1
2
3
4
1
2
3
4
1
3
2
4
3
1
2
4
3
2
1
4
3
1
2
QuickSort é baseado no conceito Dividir e Conquistar.
Este algoritimo divide o vetor em três partes principais:
1. Elementos menores que o pivô (à esquerda)
2. Pivô (elemento central)
3. Elementos maiores que o pivô (à direita)
QuickSort()
Quicksort()
Pivot: pode ser qualquer elemento do array (o primeiro, o último ou um randômico).
Exemplo: No vetor V = {52, 37, 63, 14, 17, 8, 6, 25}, considerando o elemento pivô como sendo o último do vetor (25),
após o primeiro passo, o vetor ficará {6 8 17 14 25 63 37 52} com o pivô na posição correta.
Após o primeiro passo, o pivô será definido em sua posição, com todos os elementos menores à esquerda e todos os
elementos maiores à direita.
6 8 17 14 e 63 37 52 são considerados como dois sub-arrays separados, e a lógica recursiva será aplicada sobre eles,
repetidamente até que o vetor esteja completamente ordenado.
V = {52, 37, 63, 14, 17, 8, 6, 25} //vetor de entrada = pivot é a última posição do vetor (25)
V1= {6, 8, 17, 14} e V2 = {63, 37, 52}  V = {6, 8, 17, 14, 25, 63, 37, 52}
V1.1= {6, 8, 14, 17} e V2.1 = {37, 52, 63}  V = {6, 8, 14, 17, 25, 37, 52, 63}
V1.1.1= {6, 8} V1.1.2 = {17} V2.1.1 = {37} V2.1.2 = {63}  V = {6, 8, 14, 17, 25, 37, 52, 63}
V1.1.1.1= {6, 8}  V = {6, 8, 14, 17, 25, 37, 52, 63}
Pseudocódigo
procedimento QuickSort(X[], IniVet, FimVet)
var
i, j, pivo, aux
início
i pivo) faça
| | j IniVet) então
| QuickSort(X, IniVet, j)
fimSe
se (i 
// trocar dois números
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
/* 
a[] é o vetor
p é o índice inicial (isto é, 0) 
r é o último índice do vetor
*/
void quicksort(int a[], int p, int r){
if(p pivo){ 
vet[j] = vet[j-1]; 
j--; 
}
vet[j] = ch; 
pivo++; 
}
}
if(pivo-1 >= esq){ 
quick(vet,esq,pivo-1); 
}
if(pivo+1sort) é um algoritmo de ordenação,
conceitualmente, mais simples.
É baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior
dependendo da ordem requerida), depois o segundo menor valor para a segunda posição, e
assim é feito sucessivamente com os n-1 elementos restantes, até os últimos dois elementos.
Processo:
1. Encontrar o menor elemento na matriz e trocá-lo com o elemento da primeira posição do vetor.
2. Encontrar o segundo menor elemento e trocá-lo com o elemento da segunda posição
3. Repetir até que todo o vetor esteja classificado.
SelectionSort
Selection Sort
Ordenação de vetor pela seleção do menor valor.
1. Procure a entrada que apresenta o menor valor de todo o vetor.
2. Troque seu conteúdo com aquele da primeira posição do vetor. Desta
forma, o menor valor estará na posição correta.
3. Repita então o procedimento para o restante do vetor, excluindo os
elementos que já estão na posição correta.
Selection Sort
Ordenação de vetor pela seleção do menor valor.
Implementação do Algoritmo SelectionSort
// Programa C implementando SelectionSort
# include 
// função para trocar elementos em um determinado indice
void swap(int vetor[], int firstIndex, int secondIndex){ 
int temp;
temp = vetor[firstIndex];
vetor[firstIndex] = vetor[secondIndex];
vetor[secondIndex] = temp;
}
// função para buscar o menor elemento em um sub-array
int indexOfMinimum(int vetor[], int startIndex, int n){
int minValue = vetor[startIndex];
int minIndex = startIndex;
for(int i = minIndex + 1; i A[i])
5. | | | minIndex ← i
6. | | fim_se
7. | fim_para
8. | retorne minIndex
9. fim_min
/* O método trocar(A, i, j) 
troca os valores das posições 
i e j do vetor A */
1. trocar(A, i, j)
2. | temp ← A[i]
3. | A[i] ← A[j]
4. | A[j] ← temp
5. fim_trocar
1. selectionSort(A[1...n])
2. | para i ← 1 até n - 1
3. | | minIndex ← min(A, i, n)
4. | | trocar(A, i, minIndex)
5. | fim_para
6. fim_selectionSort
O método
SelectionSort
modularizarizado
01. selectionSort(A[1...n])
02. | para i ← 1 até n - 1
03. | | minIndex ← i
04. | | para j ← i + 1 até n
05. | | | se(A[minIdex] > A[j])
06. | | | | minIndex ← j
07. | | | fim_se
08. | | fim_para
09. | | temp ← A[i]
10. | | A[i] ← A[minIndex]
11. | | A[minIndex] ← temp
12. | fim_para
13. fim_selectionSort
O método SelectionSort não modularizarizado
Um heap é uma árvore binária a qual tem uma propriedade
que cada filho é menor (ou maior) que o pai.
Frequentemente implementado como um vetor, onde os
filhos de um elemento na poposição n estão nas posições
2n+1 e 2n+2.
Existem dois tipos de heaps binários:
❑ Heaps máximos
❑ Heaps mínimos
Método da Seleção em Árvore: HeapSort
O que é um Heap?
Heap é uma estrutura de dados especial, baseada em árvore, que 
satisfaz as seguintes propriedades especiais:
Propriedade Shape: a estrutura de dados Heap é sempre uma Árvore 
Binária Completa, o que significa que todos os níveis da árvore são 
totalmente preenchidos.
Propriedade Heap: todos os nós são maiores ou iguais a ou menores ou
iguais a cada um de seus filhos. Se os nós pais forem maiores que os
nós filhos, o heap será chamado de Max-Heap e, se os nós pais forem
menores que os nós filhos, o heap será chamado Min-Heap.
Min-Heap e Max-Heap
Heap máximo (Max-Heap)
Em ambos os tipos, os valores nos nós satisfazem a uma propriedade de heap, cujos
detalhes específicos dependem do tipo de heap.
Em um heap máximo, a propriedade de heap máximo é que, para todo nó i diferente
da raíz, 
A[pai(i)>=A[i]
isto é, o valor de um nó é no máximo o valor de seu pai.
Desse modo, o maior elemento em um heap máximo é armazenado na raiz, e a
subárvore que tem raiz em um nó contém valores meores que o próprio nó.
Heap mínimo (Min-heap)
Um heap mínimo é organizado de modo oposto.
Em um heap mínimo, a propriedade de heap máximo é que, para todo nói
diferente da raíz, 
A[pai(i)0
30
1
62
2
78
3
45
4
50
índices (i)
Poda a última folha da árvora
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 62 78 45 50 85 99V
0
30
1
62
2
78
3
45
4
50
índices (i)
Repita o processo heapfy para V[0..n-3]
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 62 78 45 50 85 99V
0
30
1
62
2
78
3
45
4
50
índices (i)
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 62 78 45 50 85 99V
0
30
1
62
2
78
3
45
4
50
índices (i)
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
62 30 78 45 50 85 99V
0
62
1
30
2
78
3
45
4
50
índices (i)
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
62 30 78 45 50 85 99V
0
62
1
30
2
78
3
45
4
50
índices (i)
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
78 30 62 45 50 85 99V
0
78
1
30
2
62
3
45
4
50
índices (i)
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
78 30 62 45 50 85 99V
0
78
1
30
2
62
3
45
4
50
índices (i)
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
78 45 62 30 50 85 99V
0
78
1
45
2
62
3
30
4
50
índices (i)
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
78 45 62 30 50 85 99V
0
78
1
45
2
62
3
30
4
50
índices (i)
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
78 50 62 30 45 85 99V
0
78
1
50
2
62
3
30
4
45
índices (i)
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
78 50 62 30 45 85 99V
0
78
1
50
2
62
3
30
4
45
índices (i)
O Maior elemento do vetor está na raiz
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
78 50 62 30 45 85 99V
0
78
1
50
2
62
3
30
4
45
índices (i)
Trocar a raiz com a última folha (V[n-3]
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 50 62 30 78 85 99V
0
45
1
50
2
62
3
30
4
78
índices (i)
Trocar a raiz com a última folha (V[n-3]
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 50 62 30 78 85 99V
0
45
1
50
2
62
3
30
4
78
índices (i)
O 3o. Maior elemento está na posição correta
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 50 62 30 78 85 99V
0
45
1
50
2
62
3
30
4
78
índices (i)
Poda a árvore na última folha
Entendendo o funcionamento do HeapSort
3a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 50 62 30 78 85 99V
0
45
1
50
2
62
3
30
índices (i)
Repete o processo para V[0..n-4]
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 50 62 30 78 85 99V
0
45
1
50
2
62
3
30
índices (i)
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 50 62 30 78 85 99V
0
45
1
50
2
62
3
30
índices (i)
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
50 45 62 30 78 85 99V
0
50
1
45
2
62
3
30
índices (i)
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
50 45 62 30 78 85 99V
0
50
1
45
2
62
3
30
índices (i)
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
62 45 50 30 78 85 99V
0
62
1
45
2
50
3
30
índices (i)
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
62 45 50 30 78 85 99V
0
62
1
45
2
50
3
30
índices (i)
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
62 45 50 30 78 85 99V
0
62
1
45
2
50
3
30
índices (i)
Propriedades Shape e Heap-max 
satisfeitas
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
62 45 50 30 78 85 99V
0
62
1
45
2
50
3
30
índices (i)
Propriedades Shape e Heap-max 
satisfeitas
Troca a raiz com a última folha
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
1
45
2
50
3
62
índices (i)
Propriedades Shape e Heap-max 
satisfeitas
Troca a raiz com a última folha
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
1
45
2
50
3
62
índices (i)
O 4o. Maior elemento já está na
posição correta do vetor.
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
1
45
2
50
3
62
índices (i)
Poda a árvore na última folha
Entendendo o funcionamento do HeapSort
4a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
1
45
2
50
índices (i)
Repita o processo
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
1
45
2
50
índices (i)
Repita o processo
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
1
45
2
50
índices (i)
Repita o processo
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
2
50
índices (i)
Repita o processo
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
2
50
índices (i)
Repita o processo
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
50 30 45 62 78 85 99V
0
50
1
30
2
45
índices (i)
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
50 30 45 62 78 85 99V
0
50
1
30
2
45
índices (i)
Propriedades Shape e Heap
satisfeitas
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
50 30 45 62 78 85 99V
0
50
1
30
2
45
índices (i)
Troca a raiz com a última folha
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
2
50
índices (i)
Troca a raiz com a última folha
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
2
50
índices (i)
O Maior está na posição correta
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
2
50
índices (i)
Poda a árvore
Entendendo o funcionamento do HeapSort
5a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
índices (i)
Entendendo o funcionamento do HeapSort
6a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
índices (i)
Repita o processo
Entendendo o funcionamento do HeapSort
6a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
índices (i)
Entendendo o funcionamento do HeapSort
6a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
índices (i)
A árvore atende as propriedades Shape e Heap
Entendendo o funcionamento do HeapSort
6a. Iteração: criar o heap 
0 1 2 3 4 5 6
45 30 50 62 78 85 99V
0
45
1
30
índices (i)
Troca a raiz com a última folha
Entendendo o funcionamento do HeapSort
6a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
1
45
índices (i)
Troca a raiz com a última folha
Entendendo o funcionamento do HeapSort
6a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
1
45
índices (i)
O Maior está na posição correta
Entendendo o funcionamento do HeapSort
6a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
1
45
índices (i)
Podar a árvore
Entendendo o funcionamento do HeapSort
6a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
índices (i)
Entendendo o funcionamentodo HeapSort
7a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
índices (i)
Repita o processo
Entendendo o funcionamento do HeapSort
7a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
índices (i)
Repita o processo
Entendendo o funcionamento do HeapSort
7a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
índices (i)
Repita o processo
Entendendo o funcionamento do HeapSort
7a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
0
30
índices (i)
Poda a árvore
Entendendo o funcionamento do HeapSort
7a. Iteração: criar o heap 
0 1 2 3 4 5 6
30 45 50 62 78 85 99V
índices (i)
Vetor Ordenado.
Implementando 
o HeapSort
parte #1
#include 
using namespace std;
void heapify(int vetor[], int n, int i){
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
// verifica se filho à esquerda é maior que a raiz
if (l vetor[largest]) largest = l;
// verifica se o filho à direita é maior que o maior até agora
if (r vetor[largest]) largest = r;
// se o maior não está na raiz 
if (largest != i){
swap(vetor[i], vetor[largest]);
// empilhar (heapify) recursivamente a sub-árvore afetada
heapify(vetor, n, largest);
}
}
Implementando 
o HeapSort
parte #1
#include 
using namespace std;
void heapify(int vetor[], int n, int i){
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
// verifica se filho à esquerda é maior que a raiz
if (l vetor[largest]) largest = l;
// verifica se o filho à direita é maior que o maior até agora
if (r vetor[largest]) largest = r;
// se o maior não está na raiz 
if (largest != i){
swap(vetor[i], vetor[largest]);
// empilhar (heapify) recursivamente a sub-árvore afetada
heapify(vetor, n, largest);
}
}
void heapSort(int vetor[], int n){
// construa um heap (rearranja o vetor)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(vetor, n, i);
// extrair um elemento por vez do heap
for (int i=n-1; i>=0; i--){
// mover a raiz atural para o fim
swap(vetor[0], vetor[i]);
// chamada da função heapify sobre o heap reduzido
heapify(vetor, i, 0);
}
}
/* função para escrever o vetor de tamanho n */
void printArray(int vetor[], int n){
for (int i = 0; i 0) {
i--;
t = a[i];
} else {
n--;
if (n a[filho]))
filho++;
if(a[filho] > t) {
a[pai] = a[filho];
pai = filho;
filho = pai * 2 + 1;
} else {
break;
}
}
a[pai] = t;
}
}
InsertionSort (método de inserção direta)
BinaryInsertionSort (método da inserção direta binária)
Métodos de Ordenação por Inserção
Método de ordenação por inserção direta
InsertionSort
InsertionSort
Método de 
ordenação por 
inserção direta
InsertionSort
Método de ordenação por inserção direta
Método de Ordenação por Inserção Direta: 
InsertionSort
void insercao (int vet, int tam){
int i, j, x;
for (i=2; i= 0) && (vetor[i] > key); i--) 
{
21. vetor[i + 1] = vetor[i];
22. }
23. vetor[i + 1] = key;
24. }
25. }
Método da inserção direta binária
A classificação de inserção binária BinaryInsertionSort é uma variante da
classificação de inserção direta InsertionSort, na qual o local adequado para
inserir o elemento selecionado é encontrado usando a pesquisa binária.
A pesquisa binária reduz o número de comparações para encontrar o local 
correto na parte classificada dos dados.
BinaryInsertionSort
Método de Ordenação por Inserção Direta Binária: 
BinaryInsertionSort
O algoritmo de inserção direta apresentado na seção anterior faz uma pesquisa linear
para encontrar a posição em que a inserção será realizada.
No entanto, como o elemento é inserido em uma sequência que já está classificada,
podemos usar uma pesquisa binária em vez de uma pesquisa linear.
Enquanto uma pesquisa linear requer comparações O(n) no pior caso, uma pesquisa
binária requer apenas comparações O(log(n)).
Portanto, se o custo de uma comparação for significativo, a pesquisa binária poderá
ser preferida.
Algoritmo BinaryInsertionSort
import java.util.Arrays;
public class BinaryInsertionSort {
public static void main(String[] args) {
final int[] input = { 4, 10, 3, 1, 9, 15 };
System.out.println("Before Sorting - " + Arrays.toString(input));
new BinaryInsertionSort().sort(input);
System.out.println("After Sorting - " + Arrays.toString(input));
}
public void sort(int array[]) {
for (int i = 1; icorreta
}
}
}
Análise de Complexidade do algoritmo de 
Ordenação por Inserção Direta Binária: BinaryInsertionSort
 Na pior das hipóteses, a classificação por inserção direta possui custo de tempo proporcional 
a O(n), tempo em sua n-ésima iteração, enquanto o uso da pesquisa binária pode reduzi-lo a 
O(log(n)).
 A complexidade de tempo geral do algoritmo, na pior das hipóteses, ainda é O(n2) devido
ao número de trocas necessárias para colocar todos os elementos no local correto.
MergeSort: método de intercalação
BucketSort (método da distribuição de chave) 
Radix
Outros métodos
MergeSort é baseado no conceito Dividir e Conquistar, recursivamente,
consumindo menor tempo.
A matriz não classificada fornecida com n elementos é dividida em
n subarrays, cada um com um elemento, porque um único elemento
sempre é classificado em si.
Em seguida, mescla repetidamente essas sub-matrizes, para produzir
novas sub-matrizes ordenadas e, no final, uma matriz ordenada
completa é produzida.
Método por Intercalação: MergeSort()
Dividir e Conquistar
Consiste em dividir um problema grande e único em subproblemas menores, resolver os
subproblemas menores e combinar suas soluções para encontrar a solução para o grande
problema original.
Desta forma fica mais fácil resolver todo o problema.
O conceito Dividir e Conquistar envolve três passos:
1. Dividir o problema em múltiplos problemas menores. 
2. Conquistar o subproblema por ordená-lo. A ideia é quebrar o problema em subproblemas
atômicos, onde eles são solúveis.
3. Combinar as soluções dos subproblemas para encontrar a solução do problema atual. 
Dividir e Conquistar
MergeSort, dividir para conquistar
Implementação do 
Mergesort
/* a[] é o vetor
p é o índice inicial, 0
r é o último índice do vetor. 
*/
#include 
// Entrada sugerida a[5] = {32, 45, 67, 2, 7} como vetor a ser ordenado.
// função mergeSort
void mergeSort(int a[], int p, int r){
int q;
if(pO método SelectionSort não modularizarizado
	Slide 39: Método da Seleção em Árvore: HeapSort
	Slide 40: O que é um Heap?
	Slide 41: Min-Heap e Max-Heap
	Slide 42: Heap máximo (Max-Heap)
	Slide 43: Heap mínimo (Min-heap)
	Slide 44: Heap máximo visto como uma Árvore Binária
	Slide 45: Heap máximo visto como uma Árvore Binária
	Slide 46: Enxergando a árvore binária dentro de um vetor
	Slide 47: Enxergando a árvore binária dentro de um vetor
	Slide 48: Entendendo o funcionamento do HeapSort
	Slide 49: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 50: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 51: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 52: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 53: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 54: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 55: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 56: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 57: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 58: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 59: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 60: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 61: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 62: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 63: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 64: Entendendo o funcionamento do HeapSort 1a. Iteração: criar o heap 
	Slide 65: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 66: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 67: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 68: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 69: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 70: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 71: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 72: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 73: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 74: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 75: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 76: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 77: Entendendo o funcionamento do HeapSort 2a. Iteração: criar o heap 
	Slide 78: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 79: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 80: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 81: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 82: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 83: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 84: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 85: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 86: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 87: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 88: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 89: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 90: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 91: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 92: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 93: Entendendo o funcionamento do HeapSort 3a. Iteração: criar o heap 
	Slide 94: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 95: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 96: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 97: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 98: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 99: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 100: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 101: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 102: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 103: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 104: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 105: Entendendo o funcionamento do HeapSort 4a. Iteração: criar o heap 
	Slide 106: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 107: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 108: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 109: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 110: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 111: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 112: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 113: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 114: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 115: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 116: Entendendo o funcionamento do HeapSort 5a. Iteração: criar o heap 
	Slide 117: Entendendo o funcionamento do HeapSort 6a. Iteração: criar o heap 
	Slide 118: Entendendo o funcionamento do HeapSort 6a. Iteração: criar o heap 
	Slide 119: Entendendo o funcionamento do HeapSort 6a. Iteração: criar o heap 
	Slide 120: Entendendo o funcionamento do HeapSort 6a. Iteração: criar o heap 
	Slide 121: Entendendo o funcionamento do HeapSort 6a. Iteração: criar o heap 
	Slide 122: Entendendo o funcionamento do HeapSort 6a. Iteração: criar o heap 
	Slide 123: Entendendo o funcionamento do HeapSort 6a. Iteração: criar o heap 
	Slide 124: Entendendo o funcionamento do HeapSort 6a. Iteração: criar o heap 
	Slide 125: Entendendo o funcionamento do HeapSort 7a. Iteração: criar o heap 
	Slide 126: Entendendo o funcionamento do HeapSort 7a. Iteração: criar o heap 
	Slide 127: Entendendo o funcionamento do HeapSort 7a. Iteração: criar o heap 
	Slide 128: Entendendo o funcionamento do HeapSort 7a. Iteração: criar o heap 
	Slide 129: Entendendo o funcionamento do HeapSort 7a. Iteração: criar o heap 
	Slide 130: Implementando o HeapSort parte #1
	Slide 131: Implementando o HeapSort parte #1
	Slide 132
	Slide 133
	Slide 134: Análise de Complexidade do algoritmo de Ordenação pelo Método da Seleção em Árvore: HeapSort
	Slide 135: Análise de Complexidade do algoritmo de Ordenação pelo Método da Seleção em Árvore: HeapSort
	Slide 136: Conclusão da Análise de Complexidade do algoritmo de Ordenação pelo Método da Seleção em Árvore: HeapSort
	Slide 137
	Slide 138: Métodos de Ordenação por Inserção
	Slide 139: InsertionSort
	Slide 140: InsertionSort
	Slide 141: InsertionSort Método de ordenação por inserção direta
	Slide 142
	Slide 143: Método de Ordenação por Inserção Direta: InsertionSort
	Slide 144: Método de Ordenação por Inserção Direta: InsertionSort
	Slide 145: Método de Ordenação por Inserção Direta: InsertionSort
	Slide 146: BinaryInsertionSort
	Slide 147: Método de Ordenação por Inserção Direta Binária: BinaryInsertionSort
	Slide 148: Algoritmo BinaryInsertionSort
	Slide 149: Análise de Complexidade do algoritmo de Ordenação por Inserção Direta Binária: BinaryInsertionSort
	Slide 150: Outros métodos
	Slide 151: Método por Intercalação: MergeSort()
	Slide 152: Dividir e ConquistarSlide 153: Dividir e Conquistar
	Slide 154: MergeSort, dividir para conquistar
	Slide 155: Implementação do Mergesort
	Slide 156: Implementação do MergeSort
	Slide 157: Análise de Complexidade do algoritmo de Ordenação por Intercalação: Mergesort
	Slide 158: Outra Implementação do MergeSort
	Slide 159
	Slide 160: Método de Ordenação por Intercalação: MergeSort
	Slide 161: Bibliografias
	Slide 162: Vídeos que ilustram o funcionamento dos algoritmos de ordenação