Aula_04

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
ESTRUTURAS DE DADOS – AULA 4
ANITA MACIEL
Rio de Janeiro, 2011
*
*
Ordenação e Pesquisa
Agora vai ficar ainda melhor!
*
*
Para comparar vetores numéricos e char de um caracter, usamos os operadores relacionais >, >=, <, <= , == e !=.
Para trocar os conteúdos das variáveis, o comando de atribuição poderá ser usado. 
*
*
Comparando números ou um caracter
*
*
Para comparar vetores de char, usaremos a função strcmp.
Para copiar o conteúdo de um vetor de char nas posições ocupadas por outro vetor de char,usaremos a função strcpy). 
*
*
Comparando vetores de char
*
*
Para comparar membros de struct, procedermos da seguinte maneira:
 Numéricos ou char de um caracter: >, >=, <, <= , == e != e, para trocar os conteúdos das variáveis, o comando de atribuição.
 Vetor de char: strcmp e strcpy. 
*
*
Comparando membros de structs
*
*
Uma das vantagens de se usar struct é na comparação porque trocamos a struct toda e não precisamos de vários trechos de trocas como fazíamos quando usávamos vetores. 
*
*
Métodos Simples 
indicados para conjuntos pequenos;
usam muitas comparações;
os códigos são pequenos;
códigos de fácil entendimento; 
mais eficientes para pequenos arquivos.
Exemplos:
1. Selection Sort
2. Insertion Sort
3. Bubble Sort 
*
*
Métodos Eficientes ou Sofisticados
indicados para conjuntos grandes;
usam menos comparações;
os códigos são grandes;
alguns incluem conceito de recursividade, deixando-os muito complexos.
Exemplos:
1. Quick Sort
2. Merge Sort
*
*
Selection Sort
O princípio básico desse método é sempre buscar o menor dos valores restantes e levá-lo às posições iniciais(ordenação crescente).
*
*
*
*
Ideal para arquivos pequenos.
Muito simples.
Não melhora sua performance se o arquivo já estiver ordenado.
Tem menos movimentos do que o Insertion Sort.
*
*
Insertion Sort
O princípio básico desse método é considerar o vetor como dois subvetores, um ordenado e o outro, desordenado, buscando posicionar o elemento que se encontra no subvetor desordenado, no vetor ordenado.
*
*
*
*
*
*
Só ordena quando necessário.
Quando um elemento é inserido, todos os elementos maiores do que ele, são deslocados para a direita.
É considerado o melhor dos três métodos estudados.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
#include<iostream>
using namespace std;
struct dados
{
 int matric;
 float CR;
}; 
void insercao(dados vetor[], int tam);
int main()
{
 dados vet[]={13,9.5, 23, 3, 8 , 10, 10};
 system("cls");
 cout<<"\nAntes da chamada da Funcao - INSERCAO\n";
 for(int x=0; x<3;x++)
 cout <<"\n"<<vet[x].matric<<"\t"<<vet[x].CR;
 cout<<"\n";
 insercao(vet, 3);
 cout<<"\n\nDepois da chamada da Funcao - INSERCAO\n";
 for(int x=0; x<3;x++)
 cout <<"\n"<<vet[x].matric<<"\t"<<vet[x].CR;
 cout<<"\n\n";
 system("pause");
}
void insercao(dados vetor[], int tam)
{
 int j,i;dados aux;
 for (i=1;i<tam;i++)
 {
 aux = vetor[i];
 for(j=i; j>0 && aux.CR <vetor[j-1].CR; j--)
 vetor[j]=vetor[j-1];
 vetor[j]=aux; 
 }
}
*
*
 Bubble Sort
O princípio básico desse método é trocar de posições toda vez que forem encontrados valores de posições adjacentes fora de ordem. 
*
*
*
*
É o mais conhecido método.
É muito simples.
Muito lento.
É considerado o pior dos três estudados.
*
*
*
*
*
*
*
*
*
*
*
*
Sequencial ou Binária?
*
*
Sequencial ou Binária?
O
R
D
E
N
A
D
O
*
*
*
*
Reveja todos os conceitos desta aula.
Aprimore seus conhecimentos pesquisando no material didático e na bibliografia recomendada (procure na Biblioteca do campus ou na Biblioteca Virtual/ SIA).
Faça todos os exercícios.
*
*
Esteja sempre em contato com seu professor.
Não durma com dúvidas.
Assista a esta aula quantas vezes for necessário.
*
*
*