Upload
draco
View
37
Download
0
Embed Size (px)
DESCRIPTION
Algoritmos de Ordenação. CONTEÚDO (1) Auto-avaliação (2) InsertionSort (3) SelectionSort. Ordenação/Classificação. Antes de prosseguir: - PowerPoint PPT Presentation
Citation preview
Prof. Frederico Brito [email protected]
Algoritmos de OrdenaçãoAlgoritmos de OrdenaçãoAlgoritmos de OrdenaçãoAlgoritmos de Ordenação
CONTEÚDO
(1) Auto-avaliação(2) InsertionSort(3) SelectionSort
Frederico Brito FernandesFrederico Brito Fernandes 2Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Ordenação/ClassificaçãoOrdenaçã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.
(1) Auto-avaliação
Frederico Brito FernandesFrederico Brito Fernandes 3Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Ordenação por Inserção (Insertion Sort)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
(2) InsertionSort
Frederico Brito FernandesFrederico Brito Fernandes 4Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Ordenação por Inserção (Insertion Sort)Ordenação por Inserção (Insertion Sort)
7 4 1 9 2
7 7 1 9 2
4 7 1 9 2
4 7 7 9 2
4 4 7 9 2
1 4 7 9 2
i=1
i=2
1 4 7 9 2 i=3
1 4 7 9 9
1 4 7 7 9
1 4 4 7 9i=4
1 2 4 7 9
4 7 1 9 2
1 4 7 9 2
(2) InsertionSort
Frederico Brito FernandesFrederico Brito Fernandes 5Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
PseudocódigoPseudocó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
}
O(n2)
(2) InsertionSort
Frederico Brito FernandesFrederico Brito Fernandes 6Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Código em CCó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();
}
(2) InsertionSort
Frederico Brito FernandesFrederico Brito Fernandes 7Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Ordenação por Seleção (Selection Sort)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.
(3) SelectionSort
Frederico Brito FernandesFrederico Brito Fernandes 8Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
PseudocódigoPseudocó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
O(n2)
(3) SelectionSort
Frederico Brito FernandesFrederico Brito Fernandes 9Estrutura, Pesquisa e Ordenação de DadosEstrutura, Pesquisa e Ordenação de Dados
Código em CCódigo em C
#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;
}
void selectionSort(int n, int v[]){ int i; for (i=0;i<n;i++){ troca(i,encontraIndiceDoMenor(i,n-1,v), v); } }
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();}
(3) SelectionSort