ACH2002-Aula14_Algoritmos_elementares_de_ordenacao

Prévia do material em texto

3SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3SISTEMAS DE
INFORMAÇÃO 3SISTEMAS DE
INFORMAÇÃO 33 3SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO
3
Aula 14
Algoritmos de Ordenação: 
estabilidade e alg.
inserção, seleção direta e 
bolha
Profa. Ariane Machado Lima
ACH2002
4SISTEMAS DE
INFORMAÇÃO
44SISTEMAS DE
INFORMAÇÃO
44SISTEMAS DE
INFORMAÇÃO
4SISTEMAS DE
INFORMAÇÃO
44SISTEMAS DE
INFORMAÇÃO
44SISTEMAS DE
INFORMAÇÃO
4SISTEMAS DE
INFORMAÇÃO
4SISTEMAS DE
INFORMAÇÃO
44 4SISTEMAS DE
INFORMAÇÃO
44SISTEMAS DE
INFORMAÇÃO
4SISTEMAS DE
INFORMAÇÃO
44SISTEMAS DE
INFORMAÇÃO
44SISTEMAS DE
INFORMAÇÃO
4SISTEMAS DE
INFORMAÇÃO
44SISTEMAS DE
INFORMAÇÃO
4
Motivação
•Grande parte das operações de Sistemas de Informações 
é constituída por buscas em bases de dados.
•Exemplos?
5SISTEMAS DE
INFORMAÇÃO
55SISTEMAS DE
INFORMAÇÃO
55SISTEMAS DE
INFORMAÇÃO
5SISTEMAS DE
INFORMAÇÃO
55SISTEMAS DE
INFORMAÇÃO
55SISTEMAS DE
INFORMAÇÃO
5SISTEMAS DE
INFORMAÇÃO
5SISTEMAS DE
INFORMAÇÃO
55 5SISTEMAS DE
INFORMAÇÃO
55SISTEMAS DE
INFORMAÇÃO
5SISTEMAS DE
INFORMAÇÃO
55SISTEMAS DE
INFORMAÇÃO
55SISTEMAS DE
INFORMAÇÃO
5SISTEMAS DE
INFORMAÇÃO
55SISTEMAS DE
INFORMAÇÃO
5
Motivação
•Grande parte das operações de Sistemas de Informações 
é constituída por buscas em bases de dados.
•Exemplos?
•consultar saldo bancário, fornecendo número da conta 
corrente;
•consultar nota no sistema Júpiter, fornecendo número 
USP;
•consultar preço de um livro em uma loja, fornecendo 
seu código.
6SISTEMAS DE
INFORMAÇÃO
66SISTEMAS DE
INFORMAÇÃO
66SISTEMAS DE
INFORMAÇÃO
6SISTEMAS DE
INFORMAÇÃO
66SISTEMAS DE
INFORMAÇÃO
66SISTEMAS DE
INFORMAÇÃO
6SISTEMAS DE
INFORMAÇÃO
6SISTEMAS DE
INFORMAÇÃO
66 6SISTEMAS DE
INFORMAÇÃO
66SISTEMAS DE
INFORMAÇÃO
6SISTEMAS DE
INFORMAÇÃO
66SISTEMAS DE
INFORMAÇÃO
66SISTEMAS DE
INFORMAÇÃO
6SISTEMAS DE
INFORMAÇÃO
66SISTEMAS DE
INFORMAÇÃO
6
Motivação
Para essas operações, os dados devem estar ordenados.
•Algoritmos de ordenação constituem uma classe muito 
estudada de algoritmos. 
•Por quê?
7SISTEMAS DE
INFORMAÇÃO
77SISTEMAS DE
INFORMAÇÃO
77SISTEMAS DE
INFORMAÇÃO
7SISTEMAS DE
INFORMAÇÃO
77SISTEMAS DE
INFORMAÇÃO
77SISTEMAS DE
INFORMAÇÃO
7SISTEMAS DE
INFORMAÇÃO
7SISTEMAS DE
INFORMAÇÃO
77 7SISTEMAS DE
INFORMAÇÃO
77SISTEMAS DE
INFORMAÇÃO
7SISTEMAS DE
INFORMAÇÃO
77SISTEMAS DE
INFORMAÇÃO
77SISTEMAS DE
INFORMAÇÃO
7SISTEMAS DE
INFORMAÇÃO
77SISTEMAS DE
INFORMAÇÃO
7
Motivação
Para essas operações, os dados devem estar ordenados.
•Algoritmos de ordenação constituem uma classe muito 
estudada de algoritmos. 
•é impossível pensar em buscas sem ordenação;
•buscas exigem que os dados estejam organizados;
•volume de dados geralmente é grande.
8SISTEMAS DE
INFORMAÇÃO
88SISTEMAS DE
INFORMAÇÃO
88SISTEMAS DE
INFORMAÇÃO
8SISTEMAS DE
INFORMAÇÃO
88SISTEMAS DE
INFORMAÇÃO
88SISTEMAS DE
INFORMAÇÃO
8SISTEMAS DE
INFORMAÇÃO
8SISTEMAS DE
INFORMAÇÃO
88 8SISTEMAS DE
INFORMAÇÃO
88SISTEMAS DE
INFORMAÇÃO
8SISTEMAS DE
INFORMAÇÃO
88SISTEMAS DE
INFORMAÇÃO
88SISTEMAS DE
INFORMAÇÃO
8SISTEMAS DE
INFORMAÇÃO
88SISTEMAS DE
INFORMAÇÃO
8
O problema da ordenação
Mas obviamente os mesmos algoritmos podem ser facilmente adaptados para 
realizar uma ordenação decrescente
9SISTEMAS DE
INFORMAÇÃO
99SISTEMAS DE
INFORMAÇÃO
99SISTEMAS DE
INFORMAÇÃO
9SISTEMAS DE
INFORMAÇÃO
99SISTEMAS DE
INFORMAÇÃO
99SISTEMAS DE
INFORMAÇÃO
9SISTEMAS DE
INFORMAÇÃO
9SISTEMAS DE
INFORMAÇÃO
99 9SISTEMAS DE
INFORMAÇÃO
99SISTEMAS DE
INFORMAÇÃO
9SISTEMAS DE
INFORMAÇÃO
99SISTEMAS DE
INFORMAÇÃO
99SISTEMAS DE
INFORMAÇÃO
9SISTEMAS DE
INFORMAÇÃO
99SISTEMAS DE
INFORMAÇÃO
9
Algoritmos de ordenação
 Terceira parte da disciplina
 Já vimos em aulas anteriores:
– InsertionSort (inserção direta)
– MergeSort (ordenação por intercalação)
 Vamos revisar hoje outros que já devem ter visto:
– SelectionSort (ordenação por seleção direta) 
– BubbleSort (ordenação pelo método da bolha)
 Vamos comparar os quatro levando em consideração:
– Quanto usa de espaço
– Complexidade de tempo (total, comparações e movimentações)
– Estabilidade
Veremos outros até o 
final da disciplina, m
as 
mesmo assim ainda 
não veremos todos!!!
10SISTEMAS DE
INFORMAÇÃO
1010SISTEMAS DE
INFORMAÇÃO
1010SISTEMAS DE
INFORMAÇÃO
10SISTEMAS DE
INFORMAÇÃO
1010SISTEMAS DE
INFORMAÇÃO
1010SISTEMAS DE
INFORMAÇÃO
10SISTEMAS DE
INFORMAÇÃO
10SISTEMAS DE
INFORMAÇÃO
1010 10SISTEMAS DE
INFORMAÇÃO
1010SISTEMAS DE
INFORMAÇÃO
10SISTEMAS DE
INFORMAÇÃO
1010SISTEMAS DE
INFORMAÇÃO
1010SISTEMAS DE
INFORMAÇÃO
10SISTEMAS DE
INFORMAÇÃO
1010SISTEMAS DE
INFORMAÇÃO
10
Algoritmos de ordenação
 Terceira parte da disciplina
 Já vimos em aulas anteriores:
– InsertionSort (inserção direta)
– MergeSort (ordenação por intercalação)
 Vamos revisar hoje outros que já devem ter visto:
– SelectionSort (ordenação por seleção direta) 
– BubbleSort (ordenação pelo método da bolha)
 Vamos comparar os quatro levando em consideração:
– Quanto usa de espaço
– Complexidade de tempo (total, comparações e movimentações)
– Estabilidade
Vamos agora falar um 
pouquinho disso
11SISTEMAS DE
INFORMAÇÃO
1111SISTEMAS DE
INFORMAÇÃO
1111SISTEMAS DE
INFORMAÇÃO
11SISTEMAS DE
INFORMAÇÃO
1111SISTEMAS DE
INFORMAÇÃO
1111SISTEMAS DE
INFORMAÇÃO
11SISTEMAS DE
INFORMAÇÃO
11SISTEMAS DE
INFORMAÇÃO
1111 11SISTEMAS DE
INFORMAÇÃO
1111SISTEMAS DE
INFORMAÇÃO
11SISTEMAS DE
INFORMAÇÃO
1111SISTEMAS DE
INFORMAÇÃO
1111SISTEMAS DE
INFORMAÇÃO
11SISTEMAS DE
INFORMAÇÃO
1111SISTEMAS DE
INFORMAÇÃO
11
Ordenação interna x externa
 Ordenação interna: 
– o arquivo/vetor cabe inteiramente na memória principal
– tema desta disciplina 
 Ordenação externa: 
– o arquivo/vetor NÃO cabe inteiramente na memória 
principal, e portanto a memória secundária (disco/SSD) 
precisa ser usada como apoio 
– Tema da disciplina ACH2024 (AED 2) 
12SISTEMAS DE
INFORMAÇÃO
1212SISTEMAS DE
INFORMAÇÃO
1212SISTEMAS DE
INFORMAÇÃO
12SISTEMAS DE
INFORMAÇÃO
1212SISTEMAS DE
INFORMAÇÃO
1212SISTEMAS DE
INFORMAÇÃO
12SISTEMAS DE
INFORMAÇÃO
12SISTEMAS DE
INFORMAÇÃO
1212 12SISTEMAS DE
INFORMAÇÃO
1212SISTEMAS DE
INFORMAÇÃO
12SISTEMAS DE
INFORMAÇÃO
1212SISTEMAS DE
INFORMAÇÃO
1212SISTEMAS DE
INFORMAÇÃO
12SISTEMAS DE
INFORMAÇÃO
1212SISTEMAS DE
INFORMAÇÃO
12
Uso de espaço
• O uso econômico da memória disponível é um 
requisito primordial na ordenação interna.
• Métodos de ordenação in situ ou in loco (que 
ordenam no próprio vetor, usando no máximo 
algumas poucas variáveis a mais) são os preferidos.
• Métodos que utilizam listas encadeadas não são 
muito utilizados (ponteiro gasta espaço).
13SISTEMAS DE
INFORMAÇÃO
1313SISTEMAS DE
INFORMAÇÃO
1313SISTEMAS DE
INFORMAÇÃO
13SISTEMAS DE
INFORMAÇÃO
1313SISTEMAS DE
INFORMAÇÃO
1313SISTEMAS DE
INFORMAÇÃO
13SISTEMAS DE
INFORMAÇÃO
13SISTEMAS DE
INFORMAÇÃO
1313 13SISTEMAS DE
INFORMAÇÃO
1313SISTEMAS DE
INFORMAÇÃO
13SISTEMAS DE
INFORMAÇÃO
1313SISTEMAS DE
INFORMAÇÃO
1313SISTEMAS DE
INFORMAÇÃO
13SISTEMAS DE
INFORMAÇÃO
1313SISTEMAS DE
INFORMAÇÃO
13
Algoritmos de ordenação
 Terceira parte da disciplina
 Já vimos em aulas anteriores:
– InsertionSort (inserção direta)
– MergeSort (ordenação por intercalação)
 Vamos revisar hoje outros que já devem ter visto:
– SelectionSort (ordenação por seleção direta) 
– BubbleSort (ordenação pelo método da bolha)
 Vamos levar em consideração nas comparações:
– Quanto usa de espaço
– Complexidade de tempo (total, comparações e movimentações)
– Estabilidade
Vamos agora falar um 
pouquinho disso
14SISTEMAS DE
INFORMAÇÃO
1414SISTEMAS DE
INFORMAÇÃO
1414SISTEMAS DE
INFORMAÇÃO
14SISTEMAS DE
INFORMAÇÃO
1414SISTEMAS DE
INFORMAÇÃO
1414SISTEMAS DE
INFORMAÇÃO
14SISTEMAS DE
INFORMAÇÃO
14SISTEMAS DE
INFORMAÇÃO
1414 14SISTEMAS DE
INFORMAÇÃO
1414SISTEMAS DE
INFORMAÇÃO14SISTEMAS DE
INFORMAÇÃO
1414SISTEMAS DE
INFORMAÇÃO
1414SISTEMAS DE
INFORMAÇÃO
14SISTEMAS DE
INFORMAÇÃO
1414SISTEMAS DE
INFORMAÇÃO
14
Algoritmos de ordenação
 Ordenação utilizando um determinado campo chave
 Normalmente usaremos vetores com apenas um valor (ao invés de 
uma estrutura) para simplificar o problema e focar apenas na lógica 
de ordenação
 Mas na prática, quando as estruturas (registros) são muito grandes, 
minimizar movimentações é interessante. Por isso…. 
15SISTEMAS DE
INFORMAÇÃO
1515SISTEMAS DE
INFORMAÇÃO
1515SISTEMAS DE
INFORMAÇÃO
15SISTEMAS DE
INFORMAÇÃO
1515SISTEMAS DE
INFORMAÇÃO
1515SISTEMAS DE
INFORMAÇÃO
15SISTEMAS DE
INFORMAÇÃO
15SISTEMAS DE
INFORMAÇÃO
1515 15SISTEMAS DE
INFORMAÇÃO
1515SISTEMAS DE
INFORMAÇÃO
15SISTEMAS DE
INFORMAÇÃO
1515SISTEMAS DE
INFORMAÇÃO
1515SISTEMAS DE
INFORMAÇÃO
15SISTEMAS DE
INFORMAÇÃO
1515SISTEMAS DE
INFORMAÇÃO
15
Complexidade de tempo de 
algoritmos de ordenação
Para um vetor de tamanho n, a complexidade de tempo 
pode ser analisada pela:
 Complexidade total - T(n): número de operações 
(como fizemos até agora)
 Número de comparações (entre as chaves) – C(n)
 Número de movimentações de registros - M(n)
16SISTEMAS DE
INFORMAÇÃO
1616SISTEMAS DE
INFORMAÇÃO
1616SISTEMAS DE
INFORMAÇÃO
16SISTEMAS DE
INFORMAÇÃO
1616SISTEMAS DE
INFORMAÇÃO
1616SISTEMAS DE
INFORMAÇÃO
16SISTEMAS DE
INFORMAÇÃO
16SISTEMAS DE
INFORMAÇÃO
1616 16SISTEMAS DE
INFORMAÇÃO
1616SISTEMAS DE
INFORMAÇÃO
16SISTEMAS DE
INFORMAÇÃO
1616SISTEMAS DE
INFORMAÇÃO
1616SISTEMAS DE
INFORMAÇÃO
16SISTEMAS DE
INFORMAÇÃO
1616SISTEMAS DE
INFORMAÇÃO
16
Algoritmos de ordenação
 Terceira parte da disciplina
 Já vimos em aulas anteriores:
– InsertionSort (inserção direta)
– MergeSort (ordenação por intercalação)
 Vamos revisar hoje outros que já devem ter visto:
– SelectionSort (ordenação por seleção direta) 
– BubbleSort (ordenação pelo método da bolha)
 Vamos levar em consideração nas comparações:
– Quanto usa de espaço
– Complexidade de tempo (total, comparações e movimentações)
– Estabilidade Vamos agora falar um pouquinho disso
17SISTEMAS DE
INFORMAÇÃO
1717SISTEMAS DE
INFORMAÇÃO
1717SISTEMAS DE
INFORMAÇÃO
17SISTEMAS DE
INFORMAÇÃO
1717SISTEMAS DE
INFORMAÇÃO
1717SISTEMAS DE
INFORMAÇÃO
17SISTEMAS DE
INFORMAÇÃO
17SISTEMAS DE
INFORMAÇÃO
1717 17SISTEMAS DE
INFORMAÇÃO
1717SISTEMAS DE
INFORMAÇÃO
17SISTEMAS DE
INFORMAÇÃO
1717SISTEMAS DE
INFORMAÇÃO
1717SISTEMAS DE
INFORMAÇÃO
17SISTEMAS DE
INFORMAÇÃO
1717SISTEMAS DE
INFORMAÇÃO
17
Estabilidade: motivação 
Suponha que você quer ordenar uma planilha por um determinado 
campo, ex. Nome:
18SISTEMAS DE
INFORMAÇÃO
1818SISTEMAS DE
INFORMAÇÃO
1818SISTEMAS DE
INFORMAÇÃO
18SISTEMAS DE
INFORMAÇÃO
1818SISTEMAS DE
INFORMAÇÃO
1818SISTEMAS DE
INFORMAÇÃO
18SISTEMAS DE
INFORMAÇÃO
18SISTEMAS DE
INFORMAÇÃO
1818 18SISTEMAS DE
INFORMAÇÃO
1818SISTEMAS DE
INFORMAÇÃO
18SISTEMAS DE
INFORMAÇÃO
1818SISTEMAS DE
INFORMAÇÃO
1818SISTEMAS DE
INFORMAÇÃO
18SISTEMAS DE
INFORMAÇÃO
1818SISTEMAS DE
INFORMAÇÃO
18
Estabilidade: motivação 
Suponha que você quer ordenar uma planilha por um determinado 
campo, ex. Nome:
19SISTEMAS DE
INFORMAÇÃO
1919SISTEMAS DE
INFORMAÇÃO
1919SISTEMAS DE
INFORMAÇÃO
19SISTEMAS DE
INFORMAÇÃO
1919SISTEMAS DE
INFORMAÇÃO
1919SISTEMAS DE
INFORMAÇÃO
19SISTEMAS DE
INFORMAÇÃO
19SISTEMAS DE
INFORMAÇÃO
1919 19SISTEMAS DE
INFORMAÇÃO
1919SISTEMAS DE
INFORMAÇÃO
19SISTEMAS DE
INFORMAÇÃO
1919SISTEMAS DE
INFORMAÇÃO
1919SISTEMAS DE
INFORMAÇÃO
19SISTEMAS DE
INFORMAÇÃO
1919SISTEMAS DE
INFORMAÇÃO
19
Estabilidade: motivação 
Suponha que você quer ordenar uma planilha por um determinado 
campo, ex. Nome:
Agora você quer ordenar por outro campo (ex. Idade) mantendo a 
ordenação por nome no caso de empate de idade (ou seja, sem 
alterar a ordem relativa entre os empates)
20SISTEMAS DE
INFORMAÇÃO
2020SISTEMAS DE
INFORMAÇÃO
2020SISTEMAS DE
INFORMAÇÃO
20SISTEMAS DE
INFORMAÇÃO
2020SISTEMAS DE
INFORMAÇÃO
2020SISTEMAS DE
INFORMAÇÃO
20SISTEMAS DE
INFORMAÇÃO
20SISTEMAS DE
INFORMAÇÃO
2020 20SISTEMAS DE
INFORMAÇÃO
2020SISTEMAS DE
INFORMAÇÃO
20SISTEMAS DE
INFORMAÇÃO
2020SISTEMAS DE
INFORMAÇÃO
2020SISTEMAS DE
INFORMAÇÃO
20SISTEMAS DE
INFORMAÇÃO
2020SISTEMAS DE
INFORMAÇÃO
20
Estabilidade: motivação 
Suponha que você quer ordenar uma planilha por um determinado 
campo, ex. Nome:
Agora você quer ordenar por outro campo (ex. Idade) mantendo a 
ordenação por nome no caso de empate de idade (ou seja, sem 
alterar a ordem relativa entre os empates)
Ou seja, você quer um algoritmo de ordenação estável !
21SISTEMAS DE
INFORMAÇÃO
2121SISTEMAS DE
INFORMAÇÃO
2121SISTEMAS DE
INFORMAÇÃO
21SISTEMAS DE
INFORMAÇÃO
2121SISTEMAS DE
INFORMAÇÃO
2121SISTEMAS DE
INFORMAÇÃO
21SISTEMAS DE
INFORMAÇÃO
21SISTEMAS DE
INFORMAÇÃO
2121 21SISTEMAS DE
INFORMAÇÃO
2121SISTEMAS DE
INFORMAÇÃO
21SISTEMAS DE
INFORMAÇÃO
2121SISTEMAS DE
INFORMAÇÃO
2121SISTEMAS DE
INFORMAÇÃO
21SISTEMAS DE
INFORMAÇÃO
2121SISTEMAS DE
INFORMAÇÃO
21
Estabilidade
Definição: Um algoritmo de ordenação é estável se 
não altera a posição relativa de elementos que têm 
um mesmo valor.
Ex.:
22SISTEMAS DE
INFORMAÇÃO
2222SISTEMAS DE
INFORMAÇÃO
2222SISTEMAS DE
INFORMAÇÃO
22SISTEMAS DE
INFORMAÇÃO
2222SISTEMAS DE
INFORMAÇÃO
2222SISTEMAS DE
INFORMAÇÃO
22SISTEMAS DE
INFORMAÇÃO
22SISTEMAS DE
INFORMAÇÃO
2222 22SISTEMAS DE
INFORMAÇÃO
2222SISTEMAS DE
INFORMAÇÃO
22SISTEMAS DE
INFORMAÇÃO
2222SISTEMAS DE
INFORMAÇÃO
2222SISTEMAS DE
INFORMAÇÃO
22SISTEMAS DE
INFORMAÇÃO
2222SISTEMAS DE
INFORMAÇÃO
22
Estabilidade
 Alguns dos métodos de ordenação mais eficientes 
não são estáveis.
24SISTEMAS DE
INFORMAÇÃO
2424SISTEMAS DE
INFORMAÇÃO
2424SISTEMAS DE
INFORMAÇÃO
24SISTEMAS DE
INFORMAÇÃO
2424SISTEMAS DE
INFORMAÇÃO
2424SISTEMAS DE
INFORMAÇÃO
24SISTEMAS DE
INFORMAÇÃO
24SISTEMAS DE
INFORMAÇÃO
2424 24SISTEMAS DE
INFORMAÇÃO
2424SISTEMAS DE
INFORMAÇÃO
24SISTEMAS DE
INFORMAÇÃO
2424SISTEMAS DE
INFORMAÇÃO
2424SISTEMAS DE
INFORMAÇÃO
24SISTEMAS DE
INFORMAÇÃO
2424SISTEMAS DE
INFORMAÇÃO
24
Algoritmos de ordenação
• Algoritmos elementares (simples)
 Inserção Direta (InsertionSort)
 Seleção Direta (SelectionSort)
 Método da Bolha (BubbleSort)
25 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO
25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO
25
Insertion sort 
(inserção direta)
Complexidade de tempo: 
In loco?:
Estável: 
insercao (n, v) 
 para j ← 2 até tamanho de v faça
 chave ← v[j];
 // ordenando elementos à esquerda
 i ← j – 1
 enquanto i > 0 e v[i] > chave faça
 v[i+1] ← v[i]
 i ← i - 1
 fim enquanto
 v[i+1] ← chave
 fim para
 
26 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO
26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DEINFORMAÇÃO 2626 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO
26
Insertion sort 
(inserção direta)
Complexidade de tempo: O(n2) 
In loco?:
Estável: 
insercao (n, v) 
 para j ← 2 até tamanho de v faça
 chave ← v[j];
 // ordenando elementos à esquerda
 i ← j – 1
 enquanto i > 0 e v[i] > chave faça
 v[i+1] ← v[i]
 i ← i - 1
 fim enquanto
 v[i+1] ← chave
 fim para
 
27 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO
27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO
27
Insertion sort 
(inserção direta)
Complexidade de tempo: O(n2) 
In loco?: SIM!
Estável: 
insercao (n, v) 
 para j ← 2 até tamanho de v faça
 chave ← v[j];
 // ordenando elementos à esquerda
 i ← j – 1
 enquanto i > 0 e v[i] > chave faça
 v[i+1] ← v[i]
 i ← i - 1
 fim enquanto
 v[i+1] ← chave
 fim para
 
28 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO
28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO
28
Insertion sort 
(inserção direta)
Complexidade de tempo: O(n2) 
In loco?: SIM!
Estável: Sim! O que o torna estável?
insercao (n, v) 
 para j ← 2 até tamanho de v faça
 chave ← v[j];
 // ordenando elementos à esquerda
 i ← j – 1
 enquanto i > 0 e v[i] > chave faça
 v[i+1] ← v[i]
 i ← i - 1
 fim enquanto
 v[i+1] ← chave
 fim para
 
29 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO
29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO
29
Insertion sort 
(inserção direta)
Complexidade de tempo: O(n2) 
In loco?: SIM!
Estável: Sim! O que o torna estável? O 
menor elemento do subvetor à direita é 
inserido APÓS os elementos que já foram 
ordenados, e o processo é realizado da 
esquerda para a direita.
insercao (n, v) 
 para j ← 2 até tamanho de v faça
 chave ← v[j];
 // ordenando elementos à esquerda
 i ← j – 1
 enquanto i > 0 e v[i] > chave faça
 v[i+1] ← v[i]
 i ← i - 1
 fim enquanto
 v[i+1] ← chave
 fim para
 
30 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO
30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO
30
Insertion sort 
(inserção direta)
Complexidade de tempo: O(n2) 
Complexidade de tempo no melhor caso:
insercao (n, v) 
 para j ← 2 até tamanho de v faça
 chave ← v[j];
 // ordenando elementos à esquerda
 i ← j – 1
 enquanto i > 0 e v[i] > chave faça
 v[i+1] ← v[i]
 i ← i - 1
 fim enquanto
 v[i+1] ← chave
 fim para
 
31 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO
31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO
31
Insertion sort 
(inserção direta)
Complexidade de tempo: O(n2) 
Complexidade de tempo no melhor caso:
O(n) quando o vetor já está ordenado
insercao (n, v) 
 para j ← 2 até tamanho de v faça
 chave ← v[j];
 // ordenando elementos à esquerda
 i ← j – 1
 enquanto i > 0 e v[i] > chave faça
 v[i+1] ← v[i]
 i ← i - 1
 fim enquanto
 v[i+1] ← chave
 fim para
 
32 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO
32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO
32
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
?
Note que além das comparações entre chaves 
temos a comparação i > 0
Dá para eliminá-la… como?
insercao (n, v) 
 para j ← 2 até tamanho de v faça
 chave ← v[j];
 // ordenando elementos à esquerda
 i ← j – 1
 enquantoi > 0 e v[i] > chave faça
 v[i+1] ← v[i]
 i ← i - 1
 fim enquanto
 v[i+1] ← chave
 fim para
 
33 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO
33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO
33
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
?
Note que além das comparações entre chaves 
temos a comparação i > 0
Dá para eliminá-la… como?
Usando uma sentinela! - colocando na primeira 
posição (extra) um valor “-infinito” (ex: INT_MIN)
O código do slide a seguir está em C, por isso assumiremos que o vetor 
começa em 0 (mas terá uma posição a mais por conta da sentinela).
insercao (n, v) 
 para j ← 2 até tamanho de v faça
 chave ← v[j];
 // ordenando elementos à esquerda
 i ← j – 1
 enquanto i > 0 e v[i] > chave faça
 v[i+1] ← v[i]
 i ← i - 1
 fim enquanto
 v[i+1] ← chave
 fim para
 
34 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO
34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO
34
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
No total, assumindo que todas as permutações 
de n são igualmente prováveis no caso médio:
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
35 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO
35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO
35
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
No total, assumindo que todas as permutações 
de n são igualmente prováveis no caso médio:
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
36 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO
36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO
36
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
No total, assumindo que todas as permutações 
de n são igualmente prováveis no caso médio:
(j-1 números + sentinela)
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
37 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO
37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO
37
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
No total, assumindo que todas as permutações 
de n são igualmente prováveis no caso médio:
(j-1 números + sentinela)
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
38 3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO
38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO
38
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
No total, assumindo que todas as permutações 
de n são igualmente prováveis no caso médio:
(j-1 números + sentinela)
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
39 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO
39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO
39
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
No total, assumindo que todas as permutações 
de n são igualmente prováveis no caso médio:
Pois j começa em 2
(j-1 números + sentinela)
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
40 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO
40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO
40
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
No total, assumindo que todas as permutações 
de n são igualmente prováveis no caso médio:
(j-1 números + sentinela)
Pois j começa em 2
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
41 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO
41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO
41
Insertion sort 
(inserção direta)
Número de comparações entre chaves - C(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
No total (para j de 2 a n):
(j-1 números + sentinela)
Σ j+1 = 1 Σ j+1
j=2 j=2
nn
2 2
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
 média (1, j) 
 
0 n
-∞
-∞
-∞
42 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO
42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO
42
Insertion sort 
(inserção direta)
Número de movimentações de registros - M(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j: 
Melhor caso: Mj(n) = 2 
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
43 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO
43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO
43
Insertion sort 
(inserção direta)
Número de movimentações de registros - M(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
Melhor caso: Mj(n) = 2 
Pior caso: Mj(n) = (j-1)+2
Caso médio: Mj(n) = média(2, j+1) = (j+3)/2
No total (para j de 2 a n):
Melhor caso: M(n) = 2(n-1)
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
44 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO44SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO
44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO
44
Insertion sort 
(inserção direta)
Número de movimentações de registros - M(n):
Para análise de caso médio é útil entender o que 
ocorre em cada iteração:
Na iteração de um dado valor j:
Melhor caso: Mj(n) = 2 
Pior caso: Mj(n) = (j-1)+2
Caso médio: Mj(n) = média(2, j+1) = (j+3)/2
No total (para j de 2 a n):
Melhor caso: M(n) = 2(n-1)
#include <limits.h>
void insercao(int n, int [] v) { 
 int i, j, chave;
 v[0] = INT_MIN; //sentinela!!!
 for (j = 2; j <= n; j++) {
chave = v[j];
// ordenando elementos à esquerda
i = j – 1;
while (v[i] > chave){
 v[i+1] = v[i];
i = i - 1;
 }
 v[i+1] = chave;
 }
 }
0 n
-∞
-∞
-∞
No livro do Ziviani ele coloca a inicialização da sentinela dentro do for (v[0] = chave). É desnecessário, e 
aumenta em 1 o nr de movimentações (que ele só considerou no melhor caso, por isso lá ele coloca Mj(n) 
= 3). No pior caso e caso médio ficou igual porque acho que ele considerou usar o v[0] no lugar da chave. 
SISTEMAS DE
INFORMAÇÃO
45
45
45
45SISTEMAS DE
INFORMAÇÃO
45
45
45
45SISTEMAS DE
INFORMAÇÃO
45
45SISTEMAS DE
INFORMAÇÃO
45
45
45
45SISTEMAS DE
INFORMAÇÃO
45
45
45
45SISTEMAS DE
INFORMAÇÃO
45
45SISTEMAS DE
INFORMAÇÃO
45
45
45
SISTEMAS DE
INFORMAÇÃO
45
45
45
45 45SISTEMAS DE
INFORMAÇÃO
45
45
45
45SISTEMAS DE
INFORMAÇÃO
45
45SISTEMAS DE
INFORMAÇÃO
45
45
45
45SISTEMAS DE
INFORMAÇÃO
45
45
45
45SISTEMAS DE
INFORMAÇÃO
45
45SISTEMAS DE
INFORMAÇÃO
45
45
45
45SISTEMAS DE
INFORMAÇÃO
4545
Tabela comparativa dos 
algoritmos de ordenação
SISTEMAS DE
INFORMAÇÃO
46
46
46
46SISTEMAS DE
INFORMAÇÃO
46
46
46
46SISTEMAS DE
INFORMAÇÃO
46
46SISTEMAS DE
INFORMAÇÃO
46
46
46
46SISTEMAS DE
INFORMAÇÃO
46
46
46
46SISTEMAS DE
INFORMAÇÃO
46
46SISTEMAS DE
INFORMAÇÃO
46
46
46
SISTEMAS DE
INFORMAÇÃO
46
46
46
46 46SISTEMAS DE
INFORMAÇÃO
46
46
46
46SISTEMAS DE
INFORMAÇÃO
46
46SISTEMAS DE
INFORMAÇÃO
46
46
46
46SISTEMAS DE
INFORMAÇÃO
46
46
46
46SISTEMAS DE
INFORMAÇÃO
46
46SISTEMAS DE
INFORMAÇÃO
46
46
46
46SISTEMAS DE
INFORMAÇÃO
4646
Seleção Direta
• Primeiro passo:
– Encontrar o menor elemento do array
– Levar este menor elemento para o início do array (troca com o 
primeiro)
• Segundo passo:
– Encontrar o segundo menor elemento do array
– Levar este menor elemento para a segunda posição do array 
(troca de posição)
• E assim por diante...
52 125 -4 32 55 69 -78 200 0 63
SISTEMAS DE
INFORMAÇÃO
47
47
47
47SISTEMAS DE
INFORMAÇÃO
47
47
47
47SISTEMAS DE
INFORMAÇÃO
47
47SISTEMAS DE
INFORMAÇÃO
47
47
47
47SISTEMAS DE
INFORMAÇÃO
47
47
47
47SISTEMAS DE
INFORMAÇÃO
47
47SISTEMAS DE
INFORMAÇÃO
47
47
47
SISTEMAS DE
INFORMAÇÃO
47
47
47
47 47SISTEMAS DE
INFORMAÇÃO
47
47
47
47SISTEMAS DE
INFORMAÇÃO
47
47SISTEMAS DE
INFORMAÇÃO
47
47
47
47SISTEMAS DE
INFORMAÇÃO
47
47
47
47SISTEMAS DE
INFORMAÇÃO
47
47SISTEMAS DE
INFORMAÇÃO
47
47
47
47SISTEMAS DE
INFORMAÇÃO
4747
1) 52 125 -4 32 55 69 -78 200 0 63
Prox.
Posição a ser preenchida Subvetor a ser pesquisado 
pelo menor elemento
Seleção Direta
SISTEMAS DE
INFORMAÇÃO
48
48
48
48SISTEMAS DE
INFORMAÇÃO
48
48
48
48SISTEMAS DE
INFORMAÇÃO
48
48SISTEMAS DE
INFORMAÇÃO
48
48
48
48SISTEMAS DE
INFORMAÇÃO
48
48
48
48SISTEMAS DE
INFORMAÇÃO
48
48SISTEMAS DE
INFORMAÇÃO
48
48
48
SISTEMAS DE
INFORMAÇÃO
48
48
48
48 48SISTEMAS DE
INFORMAÇÃO
48
48
48
48SISTEMAS DE
INFORMAÇÃO
48
48SISTEMAS DE
INFORMAÇÃO
48
48
48
48SISTEMAS DE
INFORMAÇÃO
48
48
48
48SISTEMAS DE
INFORMAÇÃO
48
48SISTEMAS DE
INFORMAÇÃO
48
48
48
48SISTEMAS DE
INFORMAÇÃO
4848
1)
Prox.
Posição a ser preenchida Subvetor a ser pesquisado 
pelo menor elemento
Seleção Direta
// código para achar o menor elemento
// i é a prox posição a ser preenchida, min é o índice do menor elemento
min = i;
for (j = i+1; i < n; j++)
if (v[j] < v[min]) min = j;
52 125 -4 32 55 69 -78 200 0 63
SISTEMAS DE
INFORMAÇÃO
49
49
49
49SISTEMAS DE
INFORMAÇÃO
49
49
49
49SISTEMAS DE
INFORMAÇÃO
49
49SISTEMAS DE
INFORMAÇÃO
49
49
49
49SISTEMAS DE
INFORMAÇÃO
49
49
49
49SISTEMAS DE
INFORMAÇÃO
49
49SISTEMAS DE
INFORMAÇÃO
49
49
49
SISTEMAS DE
INFORMAÇÃO
49
49
49
49 49SISTEMAS DE
INFORMAÇÃO
49
49
49
49SISTEMAS DE
INFORMAÇÃO
49
49SISTEMAS DE
INFORMAÇÃO
49
49
49
49SISTEMAS DE
INFORMAÇÃO
49
49
49
49SISTEMAS DE
INFORMAÇÃO
49
49SISTEMAS DE
INFORMAÇÃO
49
49
49
49SISTEMAS DE
INFORMAÇÃO
4949
1) 52 125 -4 32 55 69 -78 200 0 63
Subvetor a ser pesquisado Menor valor encontrado
Seleção Direta
Prox.
posição
SISTEMAS DE
INFORMAÇÃO
50
50
50
50SISTEMAS DE
INFORMAÇÃO
50
50
50
50SISTEMAS DE
INFORMAÇÃO
50
50SISTEMAS DE
INFORMAÇÃO
50
50
50
50SISTEMAS DE
INFORMAÇÃO
50
50
50
50SISTEMAS DE
INFORMAÇÃO
50
50SISTEMAS DE
INFORMAÇÃO
50
50
50
SISTEMAS DE
INFORMAÇÃO
50
50
50
50 50SISTEMAS DE
INFORMAÇÃO
50
50
50
50SISTEMAS DE
INFORMAÇÃO
50
50SISTEMAS DE
INFORMAÇÃO
50
50
50
50SISTEMAS DE
INFORMAÇÃO
50
50
50
50SISTEMAS DE
INFORMAÇÃO
50
50SISTEMAS DE
INFORMAÇÃO
50
50
50
50SISTEMAS DE
INFORMAÇÃO
5050
1)
Prox.
posição
Menor valor encontrado
TROCA
Seleção Direta
52 125 -4 32 55 69 -78 200 0 63
SISTEMAS DE
INFORMAÇÃO
51
51
51
51SISTEMAS DE
INFORMAÇÃO
51
51
51
51SISTEMAS DE
INFORMAÇÃO
51
51SISTEMAS DE
INFORMAÇÃO
51
51
51
51SISTEMAS DE
INFORMAÇÃO
51
51
51
51SISTEMAS DE
INFORMAÇÃO
51
51SISTEMAS DE
INFORMAÇÃO
51
51
51
SISTEMAS DE
INFORMAÇÃO
51
51
51
51 51SISTEMAS DE
INFORMAÇÃO
51
51
51
51SISTEMAS DE
INFORMAÇÃO
51
51SISTEMAS DE
INFORMAÇÃO
51
51
51
51SISTEMAS DE
INFORMAÇÃO
51
51
51
51SISTEMAS DE
INFORMAÇÃO
51
51SISTEMAS DE
INFORMAÇÃO
51
51
51
51SISTEMAS DE
INFORMAÇÃO
5151
1)
Prox.
posição
Menor valor encontrado
TROCA
-78 125 -4 32 55 69 52 200 0 63
Seleção Direta
52 125 -4 32 55 69 -78 200 0 63
SISTEMAS DE
INFORMAÇÃO
52
52
52
52SISTEMAS DE
INFORMAÇÃO
52
52
52
52SISTEMAS DE
INFORMAÇÃO
52
52SISTEMAS DE
INFORMAÇÃO
52
52
52
52SISTEMAS DE
INFORMAÇÃO
52
52
52
52SISTEMAS DE
INFORMAÇÃO
52
52SISTEMAS DE
INFORMAÇÃO
52
52
52
SISTEMAS DE
INFORMAÇÃO
52
52
52
52 52SISTEMAS DE
INFORMAÇÃO
52
52
52
52SISTEMAS DE
INFORMAÇÃO
52
52SISTEMAS DE
INFORMAÇÃO
52
52
52
52SISTEMAS DE
INFORMAÇÃO
52
52
52
52SISTEMAS DE
INFORMAÇÃO
52
52SISTEMAS DE
INFORMAÇÃO
52
52
52
52SISTEMAS DE
INFORMAÇÃO
5252
2) -78 125 -4 32 55 69 52 200 0 63
Prox.
posição
Subvetor a ser pesquisado
Seleção Direta
SISTEMAS DE
INFORMAÇÃO
53
53
53
53SISTEMAS DE
INFORMAÇÃO
53
53
53
53SISTEMAS DE
INFORMAÇÃO
53
53SISTEMAS DE
INFORMAÇÃO
53
53
53
53SISTEMAS DE
INFORMAÇÃO
53
53
53
53SISTEMAS DE
INFORMAÇÃO
53
53SISTEMAS DE
INFORMAÇÃO
53
53
53
SISTEMAS DE
INFORMAÇÃO
53
53
53
53 53SISTEMAS DE
INFORMAÇÃO
53
53
53
53SISTEMAS DE
INFORMAÇÃO
53
53SISTEMAS DE
INFORMAÇÃO
53
53
53
53SISTEMAS DE
INFORMAÇÃO
53
53
53
53SISTEMAS DE
INFORMAÇÃO
53
53SISTEMAS DE
INFORMAÇÃO
53
53
53
53SISTEMAS DE
INFORMAÇÃO
5353
2) -78 125 -4 32 55 69 52 200 0 63
Prox.
posição
Subvetor a ser pesquisado
Menor valor encontrado
Seleção Direta
SISTEMAS DE
INFORMAÇÃO
54
54
54
54SISTEMAS DE
INFORMAÇÃO
54
54
54
54SISTEMAS DE
INFORMAÇÃO
54
54SISTEMAS DE
INFORMAÇÃO
54
54
54
54SISTEMAS DE
INFORMAÇÃO
54
54
54
54SISTEMAS DE
INFORMAÇÃO
54
54SISTEMAS DE
INFORMAÇÃO
54
54
54
SISTEMAS DE
INFORMAÇÃO
54
54
54
54 54SISTEMAS DE
INFORMAÇÃO
54
54
54
54SISTEMAS DE
INFORMAÇÃO
54
54SISTEMAS DE
INFORMAÇÃO
5454
54
54SISTEMAS DE
INFORMAÇÃO
54
54
54
54SISTEMAS DE
INFORMAÇÃO
54
54SISTEMAS DE
INFORMAÇÃO
54
54
54
54SISTEMAS DE
INFORMAÇÃO
5454
2)
Prox.
posição Menor valor encontrado
TROCA
-78 -4 125 32 55 69 52 200 0 63
Seleção Direta
-78 125 -4 32 55 69 52 200 0 63
SISTEMAS DE
INFORMAÇÃO
55
55
55
55SISTEMAS DE
INFORMAÇÃO
55
55
55
55SISTEMAS DE
INFORMAÇÃO
55
55SISTEMAS DE
INFORMAÇÃO
55
55
55
55SISTEMAS DE
INFORMAÇÃO
55
55
55
55SISTEMAS DE
INFORMAÇÃO
55
55SISTEMAS DE
INFORMAÇÃO
55
55
55
SISTEMAS DE
INFORMAÇÃO
55
55
55
55 55SISTEMAS DE
INFORMAÇÃO
55
55
55
55SISTEMAS DE
INFORMAÇÃO
55
55SISTEMAS DE
INFORMAÇÃO
55
55
55
55SISTEMAS DE
INFORMAÇÃO
55
55
55
55SISTEMAS DE
INFORMAÇÃO
55
55SISTEMAS DE
INFORMAÇÃO
55
55
55
55SISTEMAS DE
INFORMAÇÃO
5555
3) -78 -4 125 32 55 69 52 200 0 63
Subvetor a ser pesquisado
Seleção Direta
Prox.
posição
SISTEMAS DE
INFORMAÇÃO
56
56
56
56SISTEMAS DE
INFORMAÇÃO
56
56
56
56SISTEMAS DE
INFORMAÇÃO
56
56SISTEMAS DE
INFORMAÇÃO
56
56
56
56SISTEMAS DE
INFORMAÇÃO
56
56
56
56SISTEMAS DE
INFORMAÇÃO
56
56SISTEMAS DE
INFORMAÇÃO
56
56
56
SISTEMAS DE
INFORMAÇÃO
56
56
56
56 56SISTEMAS DE
INFORMAÇÃO
56
56
56
56SISTEMAS DE
INFORMAÇÃO
56
56SISTEMAS DE
INFORMAÇÃO
56
56
56
56SISTEMAS DE
INFORMAÇÃO
56
56
56
56SISTEMAS DE
INFORMAÇÃO
56
56SISTEMAS DE
INFORMAÇÃO
56
56
56
56SISTEMAS DE
INFORMAÇÃO
5656
3) -78 -4 125 32 55 69 52 200 0 63
Prox.
posição Menor valor encontrado
Seleção Direta
SISTEMAS DE
INFORMAÇÃO
57
57
57
57SISTEMAS DE
INFORMAÇÃO
57
57
57
57SISTEMAS DE
INFORMAÇÃO
57
57SISTEMAS DE
INFORMAÇÃO
57
57
57
57SISTEMAS DE
INFORMAÇÃO
57
57
57
57SISTEMAS DE
INFORMAÇÃO
57
57SISTEMAS DE
INFORMAÇÃO
57
57
57
SISTEMAS DE
INFORMAÇÃO
57
57
57
57 57SISTEMAS DE
INFORMAÇÃO
57
57
57
57SISTEMAS DE
INFORMAÇÃO
57
57SISTEMAS DE
INFORMAÇÃO
57
57
57
57SISTEMAS DE
INFORMAÇÃO
57
57
57
57SISTEMAS DE
INFORMAÇÃO
57
57SISTEMAS DE
INFORMAÇÃO
57
57
57
57SISTEMAS DE
INFORMAÇÃO
5757
3)
Prox.
posição Menor valor encontrado
TROCA
-78 -4 0 32 55 69 52 200 125 63
Seleção Direta
-78 -4 125 32 55 69 52 200 0 63
SISTEMAS DE
INFORMAÇÃO
58
58
58
58SISTEMAS DE
INFORMAÇÃO
58
58
58
58SISTEMAS DE
INFORMAÇÃO
58
58SISTEMAS DE
INFORMAÇÃO
58
58
58
58SISTEMAS DE
INFORMAÇÃO
58
58
58
58SISTEMAS DE
INFORMAÇÃO
58
58SISTEMAS DE
INFORMAÇÃO
58
58
58
SISTEMAS DE
INFORMAÇÃO
58
58
58
58 58SISTEMAS DE
INFORMAÇÃO
58
58
58
58SISTEMAS DE
INFORMAÇÃO
58
58SISTEMAS DE
INFORMAÇÃO
58
58
58
58SISTEMAS DE
INFORMAÇÃO
58
58
58
58SISTEMAS DE
INFORMAÇÃO
58
58SISTEMAS DE
INFORMAÇÃO
58
58
58
58SISTEMAS DE
INFORMAÇÃO
5858
4) -78 -4 0 32 55 69 52 200 125 63
Subvetor a ser pesquisado
E assim por diante...
Seleção Direta
Prox.
posição
SISTEMAS DE
INFORMAÇÃO
59
59
59
59SISTEMAS DE
INFORMAÇÃO
59
59
59
59SISTEMAS DE
INFORMAÇÃO
59
59SISTEMAS DE
INFORMAÇÃO
59
59
59
59SISTEMAS DE
INFORMAÇÃO
59
59
59
59SISTEMAS DE
INFORMAÇÃO
59
59SISTEMAS DE
INFORMAÇÃO
59
59
59
SISTEMAS DE
INFORMAÇÃO
59
59
59
59 59SISTEMAS DE
INFORMAÇÃO
59
59
59
59SISTEMAS DE
INFORMAÇÃO
59
59SISTEMAS DE
INFORMAÇÃO
59
59
59
59SISTEMAS DE
INFORMAÇÃO
59
59
59
59SISTEMAS DE
INFORMAÇÃO
59
59SISTEMAS DE
INFORMAÇÃO
59
59
59
59SISTEMAS DE
INFORMAÇÃO
5959
4)
Subvetor a ser pesquisado
E assim por diante... 
ATÉ QUANDO?
Seleção Direta
Prox.
posição
-78 -4 0 32 55 69 52 200 125 63
SISTEMAS DE
INFORMAÇÃO
60
60
60
60SISTEMAS DE
INFORMAÇÃO
60
60
60
60SISTEMAS DE
INFORMAÇÃO
60
60SISTEMAS DE
INFORMAÇÃO
60
60
60
60SISTEMAS DE
INFORMAÇÃO
60
60
60
60SISTEMAS DE
INFORMAÇÃO
60
60SISTEMAS DE
INFORMAÇÃO
60
60
60
SISTEMAS DE
INFORMAÇÃO
60
60
60
60 60SISTEMAS DE
INFORMAÇÃO
60
60
60
60SISTEMAS DE
INFORMAÇÃO
60
60SISTEMAS DE
INFORMAÇÃO
60
60
60
60SISTEMAS DE
INFORMAÇÃO
60
60
60
60SISTEMAS DE
INFORMAÇÃO
60
60SISTEMAS DE
INFORMAÇÃO
60
60
60
60SISTEMAS DE
INFORMAÇÃO
6060
4) -78 -4 0 32 55 69 52 200 125 63
Subvetor a ser pesquisado
E assim por diante... 
ATÉ QUANDO?
Seleção Direta
Prox.
posição
SISTEMAS DE
INFORMAÇÃO
61
61
61
61SISTEMAS DE
INFORMAÇÃO
61
61
61
61SISTEMAS DE
INFORMAÇÃO
61
61SISTEMAS DE
INFORMAÇÃO
61
61
61
61SISTEMAS DE
INFORMAÇÃO
61
61
61
61SISTEMAS DE
INFORMAÇÃO
61
61SISTEMAS DE
INFORMAÇÃO
61
61
61
SISTEMAS DE
INFORMAÇÃO
61
61
61
61 61SISTEMAS DE
INFORMAÇÃO
61
61
61
61SISTEMAS DE
INFORMAÇÃO
61
61SISTEMAS DE
INFORMAÇÃO
61
61
61
61SISTEMAS DE
INFORMAÇÃO
61
61
61
61SISTEMAS DE
INFORMAÇÃO
61
61SISTEMAS DE
INFORMAÇÃO
61
61
61
61SISTEMAS DE
INFORMAÇÃO
6161
4) -78 -4 0 32 52 69 55 200 125 6355
Prox.
posição
Subvetor a ser pesquisado
E assim por diante... 
ATÉ QUANDO?
Seleção Direta
SISTEMAS DE
INFORMAÇÃO
62
62
62
62SISTEMAS DE
INFORMAÇÃO
62
62
62
62SISTEMAS DE
INFORMAÇÃO
62
62SISTEMAS DE
INFORMAÇÃO
62
62
62
62SISTEMAS DE
INFORMAÇÃO
62
62
62
62SISTEMAS DE
INFORMAÇÃO
62
62SISTEMAS DE
INFORMAÇÃO
62
62
62
SISTEMAS DE
INFORMAÇÃO
62
62
62
62 62SISTEMAS DE
INFORMAÇÃO
62
62
62
62SISTEMAS DE
INFORMAÇÃO
62
62SISTEMAS DE
INFORMAÇÃO
62
62
62
62SISTEMAS DE
INFORMAÇÃO
62
62
62
62SISTEMAS DE
INFORMAÇÃO
62
62SISTEMAS DE
INFORMAÇÃO
62
62
62
62SISTEMAS DE
INFORMAÇÃO
6262
4) -78 -4 0 32 52 55 69 200 125 63
Prox.
posição
Subvetor a ser pesquisado
E assim por diante... 
ATÉ QUANDO?
Seleção Direta
SISTEMAS DE
INFORMAÇÃO
63
63
63
63SISTEMAS DE
INFORMAÇÃO
63
63
63
63SISTEMAS DE
INFORMAÇÃO
63
63SISTEMAS DE
INFORMAÇÃO
63
63
63
63SISTEMAS DE
INFORMAÇÃO
63
63
63
63SISTEMAS DE
INFORMAÇÃO
63
63SISTEMAS DE
INFORMAÇÃO
63
63
63
SISTEMAS DE
INFORMAÇÃO
63
63
63
63 63SISTEMAS DE
INFORMAÇÃO
63
63
63
63SISTEMAS DE
INFORMAÇÃO
63
63SISTEMAS DE
INFORMAÇÃO
63
63
63
63SISTEMAS DE
INFORMAÇÃO
63
63
63
63SISTEMAS DE
INFORMAÇÃO
63
63SISTEMAS DE
INFORMAÇÃO
63
63
63
63SISTEMAS DE
INFORMAÇÃO
6363
4) -78 -4 0 32 52 55 63 200 125 69
Subvetor a ser pesquisado
E assim por diante... 
ATÉ QUANDO?
Seleção Direta
Prox.
posição
SISTEMAS DE
INFORMAÇÃO
64
64
64
64SISTEMAS DE
INFORMAÇÃO
64
64
64
64SISTEMAS DE
INFORMAÇÃO
64
64SISTEMAS DE
INFORMAÇÃO
64
64
64
64SISTEMAS DE
INFORMAÇÃO
64
64
64
64SISTEMAS DE
INFORMAÇÃO
64
64SISTEMAS DE
INFORMAÇÃO
64
64
64
SISTEMAS DE
INFORMAÇÃO
64
64
64
64 64SISTEMAS DE
INFORMAÇÃO
64
64
64
64SISTEMAS DE
INFORMAÇÃO
64
64SISTEMAS DE
INFORMAÇÃO
64
64
64
64SISTEMAS DE
INFORMAÇÃO
64
64
64
64SISTEMAS DE
INFORMAÇÃO
64
64SISTEMAS DE
INFORMAÇÃO
64
64
64
64SISTEMAS DE
INFORMAÇÃO
6464
4) -78 -4 0 32 52 55 63 69 125 200200
Prox.
posição
Subvetor a ser pesquisado
E assim por diante... 
ATÉ QUANDO?
Seleção Direta
SISTEMAS DE
INFORMAÇÃO
65
65
65
65SISTEMAS DE
INFORMAÇÃO
65
65
65
65SISTEMAS DE
INFORMAÇÃO
65
65SISTEMAS DE
INFORMAÇÃO
65
65
65
65SISTEMAS DE
INFORMAÇÃO
65
65
65
65SISTEMAS DE
INFORMAÇÃO
65
65SISTEMAS DE
INFORMAÇÃO
65
65
65
SISTEMAS DE
INFORMAÇÃO
65
65
65
65 65SISTEMAS DE
INFORMAÇÃO
65
65
65
65SISTEMAS DE
INFORMAÇÃO
65
65SISTEMAS DE
INFORMAÇÃO
65
65
65
65SISTEMAS DE
INFORMAÇÃO
65
65
65
65SISTEMAS DE
INFORMAÇÃO
65
65SISTEMAS DE
INFORMAÇÃO
65
65
65
65SISTEMAS DE
INFORMAÇÃO
6565
4) -78 -4 0 32 52 55 63 69 125 200200
Prox.
posição
Subvetor a ser pesquisado
E assim por diante... 
ATÉ QUANDO?
Seleção Direta
?
SISTEMAS DE
INFORMAÇÃO
66
66
66
66SISTEMAS DE
INFORMAÇÃO
66
66
66
66SISTEMAS DE
INFORMAÇÃO
66
66SISTEMAS DE
INFORMAÇÃO
66
66
66
66SISTEMAS DE
INFORMAÇÃO
66
66
66
66SISTEMAS DE
INFORMAÇÃO
66
66SISTEMAS DE
INFORMAÇÃO
66
66
66
SISTEMAS DE
INFORMAÇÃO
66
66
66
66 66SISTEMAS DE
INFORMAÇÃO
66
66
66
66SISTEMAS DE
INFORMAÇÃO
66
66SISTEMAS DE
INFORMAÇÃO
66
66
66
66SISTEMAS DE
INFORMAÇÃO
66
66
66
66SISTEMAS DE
INFORMAÇÃO
66
66SISTEMAS DE
INFORMAÇÃO
66
66
66
66SISTEMAS DE
INFORMAÇÃO
6666
4)
Prox.
posição
Subvetor a ser pesquisado
Seleção Direta
?
E assim por diante... 
PÁRO QUANDO PRÓXIMA 
POSIÇÃO = TAM-1
(a última rodada é para pos = tam - 2)
-78 -4 0 32 52 55 63 69 125 200200
SISTEMAS DE
INFORMAÇÃO
6767
67
67SISTEMAS DE
INFORMAÇÃO
67
67
67
67SISTEMAS DE
INFORMAÇÃO
67
67SISTEMAS DE
INFORMAÇÃO
67
67
67
67SISTEMAS DE
INFORMAÇÃO
67
67
67
67SISTEMAS DE
INFORMAÇÃO
67
67SISTEMAS DE
INFORMAÇÃO
67
67
67
SISTEMAS DE
INFORMAÇÃO
67
67
67
67 67SISTEMAS DE
INFORMAÇÃO
67
67
67
67SISTEMAS DE
INFORMAÇÃO
67
67SISTEMAS DE
INFORMAÇÃO
67
67
67
67SISTEMAS DE
INFORMAÇÃO
67
67
67
67SISTEMAS DE
INFORMAÇÃO
67
67SISTEMAS DE
INFORMAÇÃO
67
67
67
67SISTEMAS DE
INFORMAÇÃO
6767
Algoritmo (vetor com início em 0):
• para cada posição do vetor original, onde a próxima 
posição a ser preenchida vai de 0 a tam-2
• Percorre subvetor (da próxima posição a ser preenchida 
até tamanho do vetor -1) para encontrar menor valor no 
subvetor
• Troca com o elemento da próxima posição a ser 
preenchida
Seleção Direta
SISTEMAS DE
INFORMAÇÃO
68
68
68
68SISTEMAS DE
INFORMAÇÃO
68
68
68
68SISTEMAS DE
INFORMAÇÃO
68
68SISTEMAS DE
INFORMAÇÃO
68
68
68
68SISTEMAS DE
INFORMAÇÃO
68
68
68
68SISTEMAS DE
INFORMAÇÃO
68
68SISTEMAS DE
INFORMAÇÃO
68
68
68
SISTEMAS DE
INFORMAÇÃO
68
68
68
68 68SISTEMAS DE
INFORMAÇÃO
68
68
68
68SISTEMAS DE
INFORMAÇÃO
68
68SISTEMAS DE
INFORMAÇÃO
68
68
68
68SISTEMAS DE
INFORMAÇÃO
68
68
68
68SISTEMAS DE
INFORMAÇÃO
68
68SISTEMAS DE
INFORMAÇÃO
68
68
68
68SISTEMAS DE
INFORMAÇÃO
6868
Seleção Direta
SISTEMAS DE
INFORMAÇÃO
69
69
69
69SISTEMAS DE
INFORMAÇÃO
69
69
69
69SISTEMAS DE
INFORMAÇÃO
69
69SISTEMAS DE
INFORMAÇÃO
69
69
69
69SISTEMAS DE
INFORMAÇÃO
69
69
69
69SISTEMAS DE
INFORMAÇÃO
69
69SISTEMAS DE
INFORMAÇÃO
69
69
69
SISTEMAS DE
INFORMAÇÃO
69
69
69
69 69SISTEMAS DE
INFORMAÇÃO
69
69
69
69SISTEMAS DE
INFORMAÇÃO
69
69SISTEMAS DE
INFORMAÇÃO
69
69
69
69SISTEMAS DE
INFORMAÇÃO
69
69
69
69SISTEMAS DE
INFORMAÇÃO
69
69SISTEMAS DE
INFORMAÇÃO
69
69
69
69SISTEMAS DE
INFORMAÇÃO
6969
Seleção Direta
In loco?: 
SISTEMAS DE
INFORMAÇÃO
70
70
70
70SISTEMAS DE
INFORMAÇÃO
70
70
70
70SISTEMAS DE
INFORMAÇÃO
70
70SISTEMAS DE
INFORMAÇÃO
70
70
70
70SISTEMAS DE
INFORMAÇÃO
70
70
70
70SISTEMAS DE
INFORMAÇÃO
70
70SISTEMAS DE
INFORMAÇÃO
70
70
70
SISTEMAS DE
INFORMAÇÃO
70
70
70
70 70SISTEMAS DE
INFORMAÇÃO
70
70
70
70SISTEMAS DE
INFORMAÇÃO
70
70SISTEMAS DE
INFORMAÇÃO
70
70
70
70SISTEMAS DE
INFORMAÇÃO
70
70
70
70SISTEMAS DE
INFORMAÇÃO
70
70SISTEMAS DE
INFORMAÇÃO
70
70
70
70SISTEMAS DE
INFORMAÇÃO
7070
Seleção Direta
In loco?: SIM!
Estável: 
SISTEMAS DE
INFORMAÇÃO
71
71
71
71SISTEMAS DE
INFORMAÇÃO
71
71
71
71SISTEMAS DE
INFORMAÇÃO
71
71SISTEMAS DE
INFORMAÇÃO
71
71
71
71SISTEMAS DE
INFORMAÇÃO
71
71
71
71SISTEMAS DE
INFORMAÇÃO
71
71SISTEMAS DE
INFORMAÇÃO
71
71
71
SISTEMAS DE
INFORMAÇÃO
71
71
71
71 71SISTEMAS DE
INFORMAÇÃO
71
71
71
71SISTEMAS DE
INFORMAÇÃO
71
71SISTEMAS DE
INFORMAÇÃO
71
71
71
71SISTEMAS DE
INFORMAÇÃO
71
71
71
71SISTEMAS DE
INFORMAÇÃO
71
71SISTEMAS DE
INFORMAÇÃO
71
71
71
71SISTEMAS DE
INFORMAÇÃO
7171
Seleção Direta
In loco?: SIM!
Estável: Não! Por quê?
SISTEMAS DE
INFORMAÇÃO
72
72
72
72SISTEMAS DE
INFORMAÇÃO
72
72
72
72SISTEMAS DE
INFORMAÇÃO
72
72SISTEMAS DE
INFORMAÇÃO
72
72
72
72SISTEMAS DE
INFORMAÇÃO
72
72
72
72SISTEMAS DE
INFORMAÇÃO
72
72SISTEMAS DE
INFORMAÇÃO
72
72
72
SISTEMAS DE
INFORMAÇÃO
72
72
72
72 72SISTEMAS DE
INFORMAÇÃO
72
72
72
72SISTEMAS DE
INFORMAÇÃO
72
72SISTEMAS DE
INFORMAÇÃO
72
72
72
72SISTEMAS DE
INFORMAÇÃO
72
72
72
72SISTEMAS DE
INFORMAÇÃO
72
72SISTEMAS DE
INFORMAÇÃO
72
72
72
72SISTEMAS DE
INFORMAÇÃO
7272
Seleção Direta
In loco?: SIM!
Estável: Não! Por quê?
A troca pode fazer com que um elemento da
posição j vá para a posição min, passando
“por cima” de outros elementos de igual valor 
SISTEMAS DE
INFORMAÇÃO
73
73
73
73SISTEMAS DE
INFORMAÇÃO
73
73
73
73SISTEMAS DE
INFORMAÇÃO
73
73SISTEMAS DE
INFORMAÇÃO
73
73
73
73SISTEMAS DE
INFORMAÇÃO
73
73
73
73SISTEMAS DE
INFORMAÇÃO
73
73SISTEMAS DE
INFORMAÇÃO
73
73
73
SISTEMAS DE
INFORMAÇÃO
73
73
73
73 73SISTEMAS DE
INFORMAÇÃO
73
73
73
73SISTEMAS DE
INFORMAÇÃO
73
73SISTEMAS DE
INFORMAÇÃO
73
73
73
73SISTEMAS DE
INFORMAÇÃO
73
73
73
73SISTEMAS DE
INFORMAÇÃO
73
73SISTEMAS DE
INFORMAÇÃO
73
73
73
73SISTEMAS DE
INFORMAÇÃO
7373
Seleção Direta
Complexidade de tempo: 
SISTEMAS DE
INFORMAÇÃO
74
74
74
74SISTEMAS DE
INFORMAÇÃO
74
74
74
74SISTEMAS DE
INFORMAÇÃO
74
74SISTEMAS DE
INFORMAÇÃO
74
74
74
74SISTEMAS DE
INFORMAÇÃO
74
74
74
74SISTEMAS DE
INFORMAÇÃO
74
74SISTEMAS DE
INFORMAÇÃO
74
74
74
SISTEMAS DE
INFORMAÇÃO
74
74
74
74 74SISTEMAS DE
INFORMAÇÃO
74
74
74
74SISTEMAS DE
INFORMAÇÃO
74
74SISTEMAS DE
INFORMAÇÃO
74
74
74
74SISTEMAS DE
INFORMAÇÃO
74
74
74
74SISTEMAS DE
INFORMAÇÃO
74
74SISTEMAS DE
INFORMAÇÃO
74
74
74
74SISTEMAS DE
INFORMAÇÃO
7474
Seleção Direta
Complexidade de tempo: O(n2) 
Complexidade de tempo no melhor caso:
SISTEMAS DE
INFORMAÇÃO
75
75
75
75SISTEMAS DE
INFORMAÇÃO
75
75
75
75SISTEMAS DE
INFORMAÇÃO
75
75SISTEMAS DE
INFORMAÇÃO
75
75
75
75SISTEMAS DE
INFORMAÇÃO
75
75
75
75SISTEMAS DE
INFORMAÇÃO
75
75SISTEMAS DE
INFORMAÇÃO
75
75
75
SISTEMAS DE
INFORMAÇÃO
75
75
75
75 75SISTEMAS DE
INFORMAÇÃO
75
75
75
75SISTEMAS DE
INFORMAÇÃO
75
75SISTEMAS DE
INFORMAÇÃO
75
75
75
75SISTEMAS DE
INFORMAÇÃO
75
75
75
75SISTEMAS DE
INFORMAÇÃO
75
75SISTEMAS DE
INFORMAÇÃO
75
75
75
75SISTEMAS DE
INFORMAÇÃO
7575
Seleção Direta
Complexidade de tempo: O(n2) 
Complexidade de tempo no melhor caso:
Não tem melhor caso – faz O(n2) sempre!
SISTEMAS DE
INFORMAÇÃO
76
76
76
76SISTEMAS DE
INFORMAÇÃO
76
76
76
76SISTEMAS DE
INFORMAÇÃO
76
76SISTEMAS DE
INFORMAÇÃO
76
76
76
76SISTEMAS DE
INFORMAÇÃO
76
76
76
76SISTEMAS DE
INFORMAÇÃO
76
76SISTEMAS DE
INFORMAÇÃO
76
76
76
SISTEMAS DE
INFORMAÇÃO
76
76
76
76 76SISTEMAS DE
INFORMAÇÃO
76
76
76
76SISTEMAS DE
INFORMAÇÃO
76
76SISTEMAS DE
INFORMAÇÃO
76
76
76
76SISTEMAS DE
INFORMAÇÃO
76
76
76
76SISTEMAS DE
INFORMAÇÃO
76
76SISTEMAS DE
INFORMAÇÃO
76
76
76
76SISTEMAS DE
INFORMAÇÃO
7676
Seleção Direta
para i←1 até n - 1 faça
 min ← i
 para j←i +1 até n faça
 se v[j] < v[min] min ← j 
 x ←v[i]
 v[i] ←v[min]
 v[min] ←x 
Pseudocódigo:
(vetor começando em 1 facilita
as contas corretas)
SISTEMAS DE
INFORMAÇÃO
77
77
77
77SISTEMAS DE
INFORMAÇÃO
77
77
77
77SISTEMAS DE
INFORMAÇÃO
77
77SISTEMAS DE
INFORMAÇÃO
77
77
77
77SISTEMAS DE
INFORMAÇÃO
77
77
77
77SISTEMAS DE
INFORMAÇÃO
77
77SISTEMAS DE
INFORMAÇÃO
77
77
77
SISTEMAS DE
INFORMAÇÃO
77
77
77
77 77SISTEMAS DE
INFORMAÇÃO
77
77
77
77SISTEMAS DE
INFORMAÇÃO
77
77SISTEMAS DE
INFORMAÇÃO
77
77
77
77SISTEMAS DE
INFORMAÇÃO
77
77
77
77SISTEMAS DE
INFORMAÇÃO
77
77SISTEMAS DE
INFORMAÇÃO
77
77
77
77SISTEMAS DE
INFORMAÇÃO
7777
Seleção Direta
(n-i) = Σ n-1 + n-2 + + 1…
i=1
n-1
para i←1 até n - 1 faça
 min ← i
 para j←i +1 até n faça
 se v[j] < v[min] min ← j 
 x ←v[i]
 v[i] ←v[min]
 v[min] ←x 
Pseudocódigo:
(vetor começando em 1 facilita
as contas corretas)
SISTEMAS DE
INFORMAÇÃO
78
78
78
78SISTEMAS DE
INFORMAÇÃO
78
78
78
78SISTEMAS DE
INFORMAÇÃO
78
78SISTEMAS DE
INFORMAÇÃO
78
78
78
78SISTEMAS DE
INFORMAÇÃO
78
78
78
78SISTEMAS DE
INFORMAÇÃO
78
78SISTEMAS DE
INFORMAÇÃO
78
78
78
SISTEMAS DE
INFORMAÇÃO
78
78
78
78 78SISTEMAS DE
INFORMAÇÃO
78
78
78
78SISTEMAS DE
INFORMAÇÃO
78
78SISTEMAS DE
INFORMAÇÃO
78
78
78
78SISTEMAS DE
INFORMAÇÃO
78
78
78
78SISTEMAS DE
INFORMAÇÃO
78
78SISTEMAS DE
INFORMAÇÃO
78
78
78
78SISTEMAS DE
INFORMAÇÃO
7878
Seleção Direta
(n-i) = Σ n-1 + n-2 + + 1…
i=1
n-1
para i←1 até n - 1 faça
 min ← i
 para j←i +1 até n faça
 se v[j] < v[min] min ← j 
 x ←v[i]
 v[i] ←v[min]
 v[min] ←x 
Pseudocódigo:
(vetor começando em 1 facilita
as contas corretas)
Linear no número de movimentações!!! 
Muito atraente quando os registros são grandes!!! 
SISTEMAS DE
INFORMAÇÃO
79
79
79
79SISTEMAS DE
INFORMAÇÃO
79
79
79
79SISTEMAS DE
INFORMAÇÃO
79
79SISTEMAS DE
INFORMAÇÃO79
79
79
79SISTEMAS DE
INFORMAÇÃO
79
79
79
79SISTEMAS DE
INFORMAÇÃO
79
79SISTEMAS DE
INFORMAÇÃO
79
79
79
SISTEMAS DE
INFORMAÇÃO
79
79
79
79 79SISTEMAS DE
INFORMAÇÃO
79
79
79
79SISTEMAS DE
INFORMAÇÃO
79
79SISTEMAS DE
INFORMAÇÃO
79
79
79
79SISTEMAS DE
INFORMAÇÃO
79
79
79
79SISTEMAS DE
INFORMAÇÃO
79
79SISTEMAS DE
INFORMAÇÃO
79
79
79
79SISTEMAS DE
INFORMAÇÃO
7979
Comparando InsertionSort com 
SelectionSort
• InsertionSort: quando é uma boa escolha? 
– Boa escolha para arquivos quase ordenados, ou quando 
precisa inserir alguns poucos registros em um arquivo 
que já estava ordenado 
• SelectionSort:
– Boa escolha para quando os arquivos não estão quase 
ordenados e os registros são grandes – e estabilidade 
não é um problema (M(n) linear é um grande 
diferencial...)
SISTEMAS DE
INFORMAÇÃO
80
80
80
80SISTEMAS DE
INFORMAÇÃO
80
80
80
80SISTEMAS DE
INFORMAÇÃO
80
80SISTEMAS DE
INFORMAÇÃO
80
80
80
80SISTEMAS DE
INFORMAÇÃO
80
80
80
80SISTEMAS DE
INFORMAÇÃO
80
80SISTEMAS DE
INFORMAÇÃO
80
80
80
SISTEMAS DE
INFORMAÇÃO
80
80
80
80 80SISTEMAS DE
INFORMAÇÃO
80
80
80
80SISTEMAS DE
INFORMAÇÃO
80
80SISTEMAS DE
INFORMAÇÃO
80
80
80
80SISTEMAS DE
INFORMAÇÃO
80
80
80
80SISTEMAS DE
INFORMAÇÃO
80
80SISTEMAS DE
INFORMAÇÃO
80
80
80
80SISTEMAS DE
INFORMAÇÃO
8080
Comparando InsertionSort com 
SelectionSort
• InsertionSort: 
– Boa escolha para arquivos quase ordenados, ou quando 
precisa inserir alguns poucos registros em um arquivo 
que já estava ordenado 
• SelectionSort: quando é uma boa escolha? 
– Boa escolha para quando os arquivos não estão quase 
ordenados e os registros são grandes – e estabilidade 
não é um problema (M(n) linear é um grande 
diferencial...)
SISTEMAS DE
INFORMAÇÃO
81
81
81
81SISTEMAS DE
INFORMAÇÃO
81
81
81
81SISTEMAS DE
INFORMAÇÃO
81
81SISTEMAS DE
INFORMAÇÃO
81
81
81
81SISTEMAS DE
INFORMAÇÃO
81
81
81
81SISTEMAS DE
INFORMAÇÃO
81
81SISTEMAS DE
INFORMAÇÃO
81
81
81
SISTEMAS DE
INFORMAÇÃO
81
81
81
81 81SISTEMAS DE
INFORMAÇÃO
81
81
81
81SISTEMAS DE
INFORMAÇÃO
81
81SISTEMAS DE
INFORMAÇÃO
81
81
81
81SISTEMAS DE
INFORMAÇÃO
81
81
81
81SISTEMAS DE
INFORMAÇÃO
81
81SISTEMAS DE
INFORMAÇÃO
81
81
81
81SISTEMAS DE
INFORMAÇÃO
8181
Comparando InsertionSort com 
SelectionSort
• InsertionSort: 
– Boa escolha para arquivos quase ordenados, ou quando 
precisa inserir alguns poucos registros em um arquivo 
que já estava ordenado 
• SelectionSort:
– Boa escolha para quando os arquivos não estão quase 
ordenados e os registros são grandes – e estabilidade 
não é um problema (M(n) linear é um grande 
diferencial...)
SISTEMAS DE
INFORMAÇÃO
82
82
82
82SISTEMAS DE
INFORMAÇÃO
82
82
82
82SISTEMAS DE
INFORMAÇÃO
82
82SISTEMAS DE
INFORMAÇÃO
82
82
82
82SISTEMAS DE
INFORMAÇÃO
82
82
82
82SISTEMAS DE
INFORMAÇÃO
82
82SISTEMAS DE
INFORMAÇÃO
82
82
82
SISTEMAS DE
INFORMAÇÃO
82
82
82
82 82SISTEMAS DE
INFORMAÇÃO
82
82
82
82SISTEMAS DE
INFORMAÇÃO
82
82SISTEMAS DE
INFORMAÇÃO
82
82
82
82SISTEMAS DE
INFORMAÇÃO
82
82
82
82SISTEMAS DE
INFORMAÇÃO
82
82SISTEMAS DE
INFORMAÇÃO
82
82
82
82SISTEMAS DE
INFORMAÇÃO
8282
Seleção Direta - Exercício
Prove por indução que esse algoritmo está correto.
Dica: Qual é a invariante A no início do laço que pode ser usada nesta prova? 
SISTEMAS DE
INFORMAÇÃO
83
83
83
83SISTEMAS DE
INFORMAÇÃO
83
83
83
83SISTEMAS DE
INFORMAÇÃO
83
83SISTEMAS DE
INFORMAÇÃO
83
83
83
83SISTEMAS DE
INFORMAÇÃO
83
83
83
83SISTEMAS DE
INFORMAÇÃO
83
83SISTEMAS DE
INFORMAÇÃO
83
83
83
SISTEMAS DE
INFORMAÇÃO
83
83
83
83 83SISTEMAS DE
INFORMAÇÃO
83
83
83
83SISTEMAS DE
INFORMAÇÃO
83
83SISTEMAS DE
INFORMAÇÃO
83
83
83
83SISTEMAS DE
INFORMAÇÃO
83
83
83
83SISTEMAS DE
INFORMAÇÃO
83
83SISTEMAS DE
INFORMAÇÃO
83
83
83
83SISTEMAS DE
INFORMAÇÃO
8383
Método da bolha (BubbleSort)
• Passa pelo array uma bolha que ordena duas 
posições consecutivas (leva o maior elemento 
para o final do vetor)
• Percorre o array e, em cada passo:
– Testa se dois vizinhos estão ordenados
– Troca o par que não estiver ordenado
SISTEMAS DE
INFORMAÇÃO
84
84
84
84SISTEMAS DE
INFORMAÇÃO
84
84
84
84SISTEMAS DE
INFORMAÇÃO
84
84SISTEMAS DE
INFORMAÇÃO
84
84
84
84SISTEMAS DE
INFORMAÇÃO
84
84
84
84SISTEMAS DE
INFORMAÇÃO
84
84SISTEMAS DE
INFORMAÇÃO
84
84
84
SISTEMAS DE
INFORMAÇÃO
84
84
84
84 84SISTEMAS DE
INFORMAÇÃO
84
84
84
84SISTEMAS DE
INFORMAÇÃO
84
84SISTEMAS DE
INFORMAÇÃO
84
84
84
84SISTEMAS DE
INFORMAÇÃO
84
84
84
84SISTEMAS DE
INFORMAÇÃO
84
84SISTEMAS DE
INFORMAÇÃO
84
84
84
84SISTEMAS DE
INFORMAÇÃO
8484
1) 52 125 -4 32 55 69 -78 200 0 63
52 -4 125 32 55 69 -78 200 0 63
52 -4 32 125 55 69 -78 200 0 63
52 -4 32 55 125 69 -78 200 0 63
52 -4 32 55 69 125 -78 200 0 63
troca
troca
troca
troca
troca
não troca
não troca
52 -4 32 55 69 -78 125 0 200 63
troca
Posição 
correta
52 -4 32 55 69 -78 125 200 0 63
troca
52 -4 32 55 69 -78 125 0 63 200
SISTEMAS DE
INFORMAÇÃO
85
85
85
85SISTEMAS DE
INFORMAÇÃO
85
85
85
85SISTEMAS DE
INFORMAÇÃO
85
85SISTEMAS DE
INFORMAÇÃO
85
85
85
85SISTEMAS DE
INFORMAÇÃO
85
85
85
85SISTEMAS DE
INFORMAÇÃO
85
85SISTEMAS DE
INFORMAÇÃO
85
85
85
SISTEMAS DE
INFORMAÇÃO
85
85
85
85 85SISTEMAS DE
INFORMAÇÃO
85
85
85
85SISTEMAS DE
INFORMAÇÃO
85
85SISTEMAS DE
INFORMAÇÃO
85
85
85
85SISTEMAS DE
INFORMAÇÃO
85
85
85
85SISTEMAS DE
INFORMAÇÃO
85
85SISTEMAS DE
INFORMAÇÃO
85
85
85
85SISTEMAS DE
INFORMAÇÃO
8585
2)
-4 52 32 55 69 -78 125 0 63 200
troca
troca
não troca
-4 32 52 55 -78 69 0 63 125 200
Posição 
correta
52 -4 32 55 69 -78 125 0 63 200
....
-4 32 52 55 69 -78 125 0 63 200
SISTEMAS DE
INFORMAÇÃO
86
86
86
86SISTEMAS DE
INFORMAÇÃO
86
86
86
86SISTEMAS DE
INFORMAÇÃO
86
86SISTEMAS DE
INFORMAÇÃO
86
86
86
86SISTEMAS DE
INFORMAÇÃO
86
86
86
86SISTEMAS DE
INFORMAÇÃO
86
86SISTEMAS DE
INFORMAÇÃO
86
86
86
SISTEMAS DE
INFORMAÇÃO
86
86
86
86 86SISTEMAS DE
INFORMAÇÃO
86
86
86
86SISTEMAS DE
INFORMAÇÃO
86
86SISTEMAS DE
INFORMAÇÃO
86
86
86
86SISTEMAS DE
INFORMAÇÃO
86
86
86
86SISTEMAS DE
INFORMAÇÃO
86
86SISTEMAS DE
INFORMAÇÃO
86
86
86
86SISTEMAS DE
INFORMAÇÃO
8686
2)
-4 52 32 55 69 -78 125 0 63 200
troca
troca
não troca
-4 32 52 55 -78 69 0 63 125 200
Posição 
correta
52 -4 32 55 69 -78 125 0 63 200
....
-4 32 52 55 69 -78 125 0 63 200
E assim por diante...
SISTEMAS DE
INFORMAÇÃO
87
87
87
87SISTEMAS DE
INFORMAÇÃO
87
87
87
87SISTEMAS DE
INFORMAÇÃO
87
87SISTEMAS DE
INFORMAÇÃO
87
87
87
87SISTEMAS DE
INFORMAÇÃO
87
87
87
87SISTEMAS DE
INFORMAÇÃO
87
87SISTEMAS DE
INFORMAÇÃO
87
87
87
SISTEMAS DE
INFORMAÇÃO
87
87
87
87 87SISTEMAS DE
INFORMAÇÃO
87
87
87
87SISTEMAS DE
INFORMAÇÃO
87
87SISTEMAS DE
INFORMAÇÃO
87
87
87
87SISTEMAS DE
INFORMAÇÃO
87
87
87
87SISTEMAS DE
INFORMAÇÃO
87
87SISTEMAS DE
INFORMAÇÃO
87
87
87
87SISTEMAS DE
INFORMAÇÃO
8787
Algoritmo:
• Quantas vezes?
– Percorre o vetor desde o início até onde já estiver 
ordenado (ivet) e vai trocando o par de lugar quando 
posicão [j-1] > posição [j]
Método da bolha (BubbleSort)
SISTEMAS DE
INFORMAÇÃO
88
88
88
88SISTEMAS DE
INFORMAÇÃO
88
88
88
88SISTEMAS DE
INFORMAÇÃO
88
88SISTEMAS DE
INFORMAÇÃO
88
88
88
88SISTEMAS DE
INFORMAÇÃO
88
88
88
88SISTEMAS DE
INFORMAÇÃO
88
88SISTEMAS DE
INFORMAÇÃO
88
88
88
SISTEMAS DE
INFORMAÇÃO
88
88
88
88 88SISTEMAS DE
INFORMAÇÃO
88
88
88
88SISTEMAS DE
INFORMAÇÃO
88
88SISTEMAS DE
INFORMAÇÃO
88
88
88
88SISTEMAS DE
INFORMAÇÃO
88
88
88
88SISTEMAS DE
INFORMAÇÃO
88
88SISTEMAS DE
INFORMAÇÃO
88
88
88
88SISTEMAS DE
INFORMAÇÃO
8888
void bolha(int n, int [] v) { 
 int ivet, j, temp;
 // ivet é o “final” do vetor para onde deve ir o maior elemento (do fim para o início)
 for (ivet = n - 1; ivet > 0; ivet--) 
 {
 // a cada passagem o maior elemento é descolado para a sua posição correta
 for (j = 0; j < ivet; j++)
 // se ordem está errada para dois números consecutivos, troca os números
 if (v[j] > v[j+1])
 {temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 }
 }
 }
Método da bolha (BubbleSort)
SISTEMAS DE
INFORMAÇÃO
89
89
89
89SISTEMAS DE
INFORMAÇÃO
89
89
89
89SISTEMAS DE
INFORMAÇÃO
89
89SISTEMAS DE
INFORMAÇÃO
89
89
89
89SISTEMAS DE
INFORMAÇÃO
89
89
89
89SISTEMAS DE
INFORMAÇÃO
89
89SISTEMAS DE
INFORMAÇÃO
89
89
89
SISTEMAS DE
INFORMAÇÃO
89
89
89
89 89SISTEMAS DE
INFORMAÇÃO
89
89
89
89SISTEMAS DE
INFORMAÇÃO
89
89SISTEMAS DE
INFORMAÇÃO
89
89
89
89SISTEMAS DE
INFORMAÇÃO
89
89
89
89SISTEMAS DE
INFORMAÇÃO
89
89SISTEMAS DE
INFORMAÇÃO
89
89
89
89SISTEMAS DE
INFORMAÇÃO
8989
void bolha(int n, int [] v) { 
 int ivet, j, temp;
 // ivet é o “final” do vetor para onde deve ir o maior elemento (do fim para o início)
 for (ivet = n - 1; ivet > 0; ivet--) 
 {
 // a cada passagem o maior elemento é descolado para a sua posição correta
 for (j = 0; j < ivet; j++)
 // se ordem está errada para dois números consecutivos, troca os números
 if (v[j] > v[j+1])
 {
 temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 }
 }
 }
Método da bolha (BubbleSort)
In loco?: 
SISTEMAS DE
INFORMAÇÃO
90
90
90
90SISTEMAS DE
INFORMAÇÃO
90
90
90
90SISTEMAS DE
INFORMAÇÃO
90
90SISTEMAS DE
INFORMAÇÃO
90
90
90
90SISTEMAS DE
INFORMAÇÃO
90
90
90
90SISTEMAS DE
INFORMAÇÃO
90
90SISTEMAS DE
INFORMAÇÃO
90
90
90
SISTEMAS DE
INFORMAÇÃO
90
90
90
90 90SISTEMAS DE
INFORMAÇÃO
90
90
90
90SISTEMAS DE
INFORMAÇÃO
90
90SISTEMAS DE
INFORMAÇÃO
90
90
90
90SISTEMAS DE
INFORMAÇÃO
90
90
90
90SISTEMAS DE
INFORMAÇÃO
90
90SISTEMAS DE
INFORMAÇÃO
90
90
90
90SISTEMAS DE
INFORMAÇÃO
9090
void bolha(int n, int [] v) { 
 int ivet, j, temp;
 // ivet é o “final” do vetor para onde deve ir o maior elemento (do fim para o início)
 for (ivet = n - 1; ivet > 0; ivet--) 
 {
 // a cada passagem o maior elemento é descolado para a sua posição correta
 for (j = 0; j < ivet; j++)
 // se ordem está errada para dois números consecutivos, troca os números
 if (v[j] > v[j+1])
 {
 temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 }
 }
 }
Método da bolha (BubbleSort)
In loco?: SIM!
SISTEMAS DE
INFORMAÇÃO
91
91
91
91SISTEMAS DE
INFORMAÇÃO
91
91
91
91SISTEMAS DE
INFORMAÇÃO
91
91SISTEMAS DE
INFORMAÇÃO
91
91
91
91SISTEMAS DE
INFORMAÇÃO
91
91
91
91SISTEMAS DE
INFORMAÇÃO
91
91SISTEMAS DE
INFORMAÇÃO
91
91
91
SISTEMAS DE
INFORMAÇÃO
91
91
91
91 91SISTEMAS DE
INFORMAÇÃO
91
91
91
91SISTEMAS DE
INFORMAÇÃO
91
91SISTEMAS DE
INFORMAÇÃO
91
91
91
91SISTEMAS DE
INFORMAÇÃO
91
91
91
91SISTEMAS DE
INFORMAÇÃO
91
91SISTEMAS DE
INFORMAÇÃO
91
91
91
91SISTEMAS DE
INFORMAÇÃO
9191
void bolha(int n, int [] v) { 
 int ivet, j, temp;
 // ivet é o “final” do vetor para onde deve ir o maior elemento (do fim para o início)
 for (ivet = n - 1; ivet > 0; ivet--) 
 {
 // a cada passagem o maior elemento é descolado para a sua posição correta
 for (j = 0; j < ivet; j++)
 // se ordem está errada para dois números consecutivos, troca os números
 if (v[j] > v[j+1])
 {
 temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 }
 }
 }
Método da bolha (BubbleSort)
In loco?: SIM!
Estável: Exercício! Se sim, o que o torna 
estável? Se não, dá para fazer alguma 
alteraçãozinha para torná-lo estável?
Complexidade de tempo: 
SISTEMAS DE
INFORMAÇÃO
92
92
92
92SISTEMAS DE
INFORMAÇÃO
92
92
92
92SISTEMAS DE
INFORMAÇÃO
92
92SISTEMAS DE
INFORMAÇÃO
92
92
92
92SISTEMAS DE
INFORMAÇÃO
92
92
92
92SISTEMAS DE
INFORMAÇÃO
92
92SISTEMAS DE
INFORMAÇÃO
92
92
92
SISTEMAS DE
INFORMAÇÃO
92
92
92
92 92SISTEMAS DE
INFORMAÇÃO
92
92
92
92SISTEMAS DE
INFORMAÇÃO
92
92SISTEMAS DE
INFORMAÇÃO
92
92
92
92SISTEMAS DE
INFORMAÇÃO
92
92
92
92SISTEMAS DE
INFORMAÇÃO
92
92SISTEMAS DE
INFORMAÇÃO
92
92
92
92SISTEMAS DE
INFORMAÇÃO
9292
void bolha(int n, int [] v) { 
 int ivet, j, temp;
 // ivet é o “final” do vetor para onde deve ir o maior elemento (do fim para o início)
 for (ivet = n - 1; ivet > 0; ivet--) 
 {
 // a cada passagem o maior elemento é descolado para a sua posição correta
 for (j = 0; j < ivet; j++)
 // se ordem está errada para dois números consecutivos, troca os números
 if (v[j] > v[j+1])
 {
 temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 }
 }
 }
Método da bolha (BubbleSort)
In loco?: SIM!
Estável: Exercício! Se sim, o que o torna 
estável? Se não, dá para fazer alguma 
alteraçãozinha para torná-lo estável?
Complexidade de tempo: O(n2) 
Complexidade de tempo no melhor caso:
SISTEMAS DE
INFORMAÇÃO
93
93
93
93SISTEMAS DE
INFORMAÇÃO
93
93
93
93SISTEMAS DE
INFORMAÇÃO
93
93SISTEMAS DE
INFORMAÇÃO
93
93
93
93SISTEMAS DE
INFORMAÇÃO
93
93
93
93SISTEMAS DE
INFORMAÇÃO
93
93SISTEMAS DE
INFORMAÇÃO
93
93
93
SISTEMAS DE
INFORMAÇÃO
93
93
93
93 93SISTEMAS DE
INFORMAÇÃO
93
93
93
93SISTEMAS DE
INFORMAÇÃO
93
93SISTEMAS DE
INFORMAÇÃO
93
93
93
93SISTEMAS DE
INFORMAÇÃO
93
93
93
93SISTEMAS DE
INFORMAÇÃO
93
93SISTEMAS DE
INFORMAÇÃO
93
93
93
93SISTEMAS DE
INFORMAÇÃO
9393
void bolha(int n, int [] v) { 
 int ivet, j, temp;
 // ivet é o “final” do vetor para onde deve ir o maior elemento (do fim para o início)
 for (ivet = n - 1; ivet > 0; ivet--) 
 {
 // a cada passagem o maior elemento é descolado para a sua posição correta
 for (j = 0; j < ivet; j++)
 // se ordem está errada para dois números consecutivos, troca os números
 if (v[j] > v[j+1])
 {
 temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 }
 }
 }
Método da bolha (BubbleSort)
In loco?: SIM!
Estável: Exercício! Se sim, o que o torna 
estável? Se não, dá para fazer alguma 
alteraçãozinha para torná-lo estável?
Complexidade de tempo: O(n2) 
Complexidade de tempo no melhor caso:
Não tem melhor caso – faz O(n2) sempre!
SISTEMAS DE
INFORMAÇÃO
94
94
94
94SISTEMAS DE
INFORMAÇÃO
94
94
94
94SISTEMAS DE
INFORMAÇÃO
94
94SISTEMAS DE
INFORMAÇÃO
94
94
94
94SISTEMAS DE
INFORMAÇÃO
94
94
94
94SISTEMAS DE
INFORMAÇÃO
94
94SISTEMAS DE
INFORMAÇÃO
94
94
94
SISTEMAS DE
INFORMAÇÃO
94
94
94
94 94SISTEMAS DE
INFORMAÇÃO
94
94
94
94SISTEMAS DE
INFORMAÇÃO
94
94SISTEMAS DE
INFORMAÇÃO
94
94
94
94SISTEMAS DE
INFORMAÇÃO
94
94
94
94SISTEMAS DE
INFORMAÇÃO
94
94SISTEMAS DE
INFORMAÇÃO
94
94
94
94SISTEMAS DE
INFORMAÇÃO
9494
void bolha(int n, int [] v) { 
 int ivet, j, temp;
 // ivet é o “final” do vetor para onde deve ir o maior elemento (do fim para o início)
 for (ivet = n - 1; ivet > 0; ivet--) 
 {
 // a cada passagem o maior elemento é descolado para a sua posição correta
 for (j = 0; j < ivet; j++)
 // se ordem está errada para dois números consecutivos, troca os números
 if (v[j] > v[j+1])
 {
 temp = v[j];
 v[j] = v[j+1];
 v[j+1] = temp;
 }
 }
 }
Método da bolha (BubbleSort)
Exercício: 
Faça as análises de nr de comparações e
Nr de movimentações para o melhor/pior 
Caso e caso médio.
SISTEMAS DE
INFORMAÇÃO
95
95
95
95SISTEMAS DE
INFORMAÇÃO
95
95
95
95SISTEMAS DE
INFORMAÇÃO
95
95SISTEMAS DE
INFORMAÇÃO
95
95
95
95SISTEMAS DE
INFORMAÇÃO
95
95
95
95SISTEMAS DE
INFORMAÇÃO
95
95SISTEMAS DE
INFORMAÇÃO
95
95
95
SISTEMAS DE
INFORMAÇÃO
95
95
95
95 95SISTEMAS DE
INFORMAÇÃO
95
95
95
95SISTEMAS DE
INFORMAÇÃO
95
95SISTEMAS DE
INFORMAÇÃO
95
95
95
95SISTEMAS DE
INFORMAÇÃO
95
95
95
95SISTEMAS DE
INFORMAÇÃO
95
95SISTEMAS DE
INFORMAÇÃO
95
95
95
95SISTEMAS DE
INFORMAÇÃO
9595
Algoritmos elementares x eficientes
• InsertionSort, SelectionSort e BubbleSort são exemplos 
de algoritmos elementares de ordenação
– Complexidade de tempo (pior caso): O(n2)
– Porém na prática são bem rápidos para arquivos 
pequenos (preferíveis)
– Algoritmos