Aula 9b Algoritmos de Ordenação Insertion Sort

Prévia do material em texto

Estrutura de Dados
Aula 9b – Insertion Sort
UNIP – Universidade Paulista
Prof. Rafael de Alencar Segura Última atualização: 2º Sem 2017
Insertion Sort
• Sua teoria baseia-se em ordenar os valores da 
esquerda para a direita, deixando os elementos 
lidos (a esquerda) ordenados.
• A ideia é ordenar os elementos igual a ordenação 
das cartas em um jogo de baralho.
Complexidade
• Número de comparações é o mesmo do Bubble Sort:
• N*(N-1)/2.
• Muito embora a complexidade é igual ao Bubble Sort ele é 
consideravelmente mais rápido uma vez que o número de trocas (swap) é 
menor.
• Complexidade Pior Caso: O(n²)
• Complexidade Caso Médio: O(n²)
• Complexidade Melhor Caso: O(n)
Insertion Sort - Funcionamento
Insertion Sort Escolha da chave
Iteração 
nos 
valores 
antes 
do key
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 6 2 1
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
key i j
5 1
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 6 2 1
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
key i j
5 0 1
3>5? 
falso
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 6 2 1
key i j
6 0 2
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 6 2 1
key i j
6 1 2
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
5>6? 
falso
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 6 2 1
key i j
2 1 3
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 6 2 1
key i j
2 2 3
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
6>2? 
verdadeiro
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 6 6 1
key i j
2 2 3
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 6 6 1
key i j
2 1 3
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
5>2? 
verdadeiro
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 5 6 1
key i j
2 1 3
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 5 5 6 1
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
key i j
2 0 3
3>2? 
verdadeiro
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 3 5 6 1
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
key i j
2 0 3
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 3 3 5 6 1
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
key i j
2 -1 3
falso
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 2 3 5 6 1
public InsertionSort (int[] vetor) {
int j,key, i;
for (j=1;j<vetor.length;j++){ 
key=vetor[j];
for (i=j-1; (i>=0) && (vetor[i]>key);i--) { 
vetor [i+1]=vetor[i];
}
vetor[i+1]=key;
}
key i j
2 -1 3
Funcionamento do Insertion Sort: Programa em Java
vetor Posição
0 1 2 3 4
Valores iniciais 2 3 5 6 1
• Fazer o teste de mesa para o elemento 1 (posição 4) do vetor.
Insertion Sort: Exercício
• Implementar o método de ordenação na classe InsertionSort, e a classe 
com método principal InsertionSortApp.
• Exibir o vetor antes da ordenação e após a ordenação.
Referências Bibliográficas
http://www.devmedia.com.br/algoritmos-de-ordenacao-em-java/3269