Algoritmos de Ordenação
Prof. Frederico Brito Fernandes
[email protected]
CONTEÚDO
(1) Auto-avaliação
(2) InsertionSort
(3) SelectionSort
(1) Auto-avaliação
Ordenação/Classificação
• Antes de prosseguir:
– Transforme o algoritmo bubbleSortRecursivo da aula passada, de modo
que ele continue sendo recursivo, mas que não use nenhuma estrutura
de repetição, como por exemplo for, while, ou qualquer outra.
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
2
(2) InsertionSort
Ordenação por Inserção (Insertion Sort)
• Baseado na técnica usada por jogadores de cartas
– Quando um jogador pega uma nova carta, ele abre espaço para a nova
carta e então insere-a no seu lugar apropriado
– O jogador mantém em ordem as cartas já pegas
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
3
(2) InsertionSort
Ordenação por Inserção (Insertion Sort)
7 4 1
9 2
7 7 1
9 2
4 7 1
9 2
i=1
1 4 7
9 2
1 4 7
9 9
4 7 1
9 2
1 4 7
7 9
4 7 7
9 2
1 4 4
7 9
4 4 7
9 2
1 2 4
7 9
1 4 7
9 2
1 4 7
9 2
Estrutura, Pesquisa e Ordenação de Dados
i=2
i=4
i=3
Frederico Brito Fernandes
4
(2) InsertionSort
Pseudocódigo
Algorithm Insertion_Sort (A, N):
Input: An array A storing N items
Output: A sorted in ascending order
for i  1 to N-1 do {
current  A[i]
j  i
while (A[j-1] > current) And (j>0)
A[j]  A[j-1]
j  j-1
A[j]  current
}
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
O(n2)
5
(2) InsertionSort
Código em C
#include <stdio.h>
void insertionSort(int n, int v[]){
int i, j, elemento;
for (i=0; i<n;i++){
elemento=v[i];
j=i-1;
while (j>=0 && elemento<v[j]){
v[j+1]=v[j];
j--;
}
v[j+1] = elemento;
}
void imprimeVetor(int n, int v[]){
int i;
for (i=0;i<n;i++) printf(" %3d",v[i]);
}
main(){
int qtde = 5;
int vetor[10] = {2,6,1,3,7,5,4,9,10,8};
imprimeVetor(qtde, vetor);
insertionSort(qtde, vetor);
printf("\n");
imprimeVetor(qtde, vetor);
getchar();
}
}
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
6
(3) SelectionSort
Ordenação por Seleção (Selection Sort)
• Encontre o menor elemento no array e troque-o com o
elemento na primeira posição.
• Encontre o segundo menor elemento no array e troque-o
com o elemento na segunda posição, e assim por diante
até que o array todo esteja ordenado.
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
7
(3) SelectionSort
Pseudocódigo
Algorithm Selection_Sort (A, N):
Input: An array A storing N items
Output: A sorted in ascending order
for i  0 to N-2 do
min  i
for j  i+1 to N-1 do
if A[j] < A[min] then
min  j
temp  A[min]
A[min]  A[i]
A[i]  temp
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
O(n2)
8
(3) SelectionSort
Código em C
void selectionSort(int n, int v[]){
int i;
for (i=0;i<n;i++){
troca(i,encontraIndiceDoMenor(i,n-1,v),
v);
}
}
#include <stdio.h>
void troca(int i, int j, int v[]){
int aux= v[i];
v[i]=v[j];
v[j]=aux;
}
int encontraIndiceDoMenor(int inicio, int fim,
int v[]){
int i, indiceDoMenor=inicio;
for (i=inicio; i<=fim;i++){
if (v[i]<v[indiceDoMenor])
indiceDoMenor=i;
}
return indiceDoMenor;
}
Estrutura, Pesquisa e Ordenação de Dados
main(){
int qtde = 5;
int vetor[10] = {2,6,1,3,7,5,4,9,10,8};
imprimeVetor(qtde, vetor);
selectionSort(qtde, vetor);
printf("\n");
imprimeVetor(qtde, vetor);
getchar();
}
Frederico Brito Fernandes
9