A maior rede de estudos do Brasil

Grátis
12 pág.
[INF1007] Resumo Ordenação

Pré-visualização | Página 2 de 3

void *v2) 
 
A qsort está >>sempre<< associada a uma função auxiliar de comparação! (Assim como 
todas as ordenações e a própria Busca Binária) 
Mas a função compara da qsort é "um pouco" diferente das outras. 
 
const serve pra garantir que a função >>NÃO<< vai alterar o conteúdo do nosso vetor! 
 
OBS:​ const também não é visto com detalhes em Prog 2, mas é só lembrar que é algo 
exclusivo da função de comparação da qsort. 
 
void * representa um ponteiro genérico, ou seja, um ponteiro que precisa ser convertido 
antes de ser usado! 
 
Pensa assim pra facilitar, quem criou a função qsort, planejou de uma forma que ela 
funcione pra qualquer vetor! Pois não ia adiantar nada funcionar pra vetor de int e não pra 
vetor de ponteiros né? 
E é a própria qsort que chama a função compara, lembrando que pra se chamar uma 
função é preciso passar os parâmetros corretos, então como a qsort vai adivinhar qual o 
tipo do nosso vetor?  
 
É exatamente por isso que a qsort envia como parâmetro para a função compara dois 
ponteiros genéricos! E cabe a você (sim, você mesmo!) converter pro tipo de vetor que 
estiver usando! :) 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
int compara (const void *v1, const void *v2){ 
Aluno *a1 = *( (Aluno **)v1); 
Aluno *a2 = *( (Aluno **)v2); 
 
 
Lembra como fizemos a comparação no exemplo 1 da ordenação Bolha? Precisamos 
sempre de dois elementos do vetor (Um seguido do outro). No caso, como se trata de um 
vetor de ponteiros para Aluno, cada elemento desse vetor é um ponteiro para Aluno! 
 
Então o primeiro passo é declarar dois ponteiros para Aluno: Aluno *a1 e Aluno *a2  
 
OBS:​ Recomendo usar nomes pequenos e com números pra deixar bem claro que um é 
seguido do outro! Por exemplo: Se fosse uma struct de Produtos chama de *p1 e *p2. 
 
E sempre use *v1 e *v2 nos parâmetros pra não ter risco de confundir. Pois *v1/*v2 e 
*a1/*a2 são variáveis diferentes! 
 
O segundo passo é converter o parâmetro *v1 e *v2 no tipo do nosso vetor! Como se trata 
de um vetor de ponteiros para Aluno, convertemos dessa forma: (Aluno **)v1 
 
OBS:​ Essa forma de converter um tipo em outro é chamado: Typecast  
Você deve ter visto algo parecido em Prog 1, converter um valor int em float, etc.  
Ex: int valor;  (float) valor;  
   
Mas lembra que precisamos de um ponteiro para Aluno? Bom, já declaramos os ponteiros, 
só falta o conteúdo deles! E pra conseguirmos o conteúdo de um ponteiro usamos asterisco 
seguido de parênteses!  *( (Aluno**)v1) 
 
E por fim, atribuimos esse conteúdo ao nosso recém declarado ponteiro para Aluno. 
Não precisa se preocupar com mais nada, assim que você passa pra qsort aqueles 
parâmetros, é justamente a informação necessária pra que ela faça um cálculo interno e 
consiga acessar os elementos da forma correta. 
 
OBS:​ A notícia boa é que mesmo se você não entendeu nada, sem problemas! É quase 
certeza total que será cobrado vetor de ponteiros para struct na P2. Então é só você 
decorar como se chama a qsort e esse comecinho da função compara!  
 
 
 
 
int compara (const void *v1, const void *v2){ 
Aluno *a1 = *( (Aluno **)v1); 
Aluno *a2 = *( (Aluno **)v2); 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
A única parte que você realmente precisa entender é a comparação em si. Dessa vez são 
dois critérios de comparação e é exatamente a forma que é cobrada nas provas.  
 
if(a1­>matricula < a2­>matricula) return 1; 
else if(a1­>matricula > a2­>matricula) return ­1; 
return strcmp(a1­>nome, a2­>nome); 
 
Dessa vez são dois critérios de comparação: Decrescente por matrícula e para a mesma 
matrícula, ordenar crescente por nome. 
 
************************************************************************************************ 
 
Regra Importante: (Ordenar decrescente) 
 
­ Se o primeiro elemento é menor que o segundo, retornar 1 pois ele deve vir >DEPOIS< do 
segundo elemento. 
 
­ Se o primeiro elemento é maior que o segundo, retornar ­1 pois ele deve vir >ANTES< do 
segundo elemento.  
 
OBS:​ Percebe que é só usar a lógica mesmo? Não precisa decorar nada! E se fosse pra 
ordenar de forma crescente é só inverter o 1 por ­1 nesses dois itens acima. 
 
*********************************************************************************************** 
 
Se o primeiro elemento não for maior, nem menor que o segundo, ele é igual.Então temos 
que partir pro segundo critério de ordenação que é ordem crescente por Nome! 
 
return strcmp(a1­>nome, a2­>nome); 
 
********************************************************************************************** 
 
Regra Importante: (Sobre a função strcmp) 
 
­ Retorna um valor >MENOR< que zero se o primeiro nome vem >ANTES< (Ordem 
alfabética) que o segundo. 
 
­ Retorna um valor >MAIOR< que zero se o primeiro nome vem >DEPOIS< que o segundo. 
 
­ Retorna zero se são iguais. 
 
Então se queremos ordenar de forma crescente por Nome, o próprio retorno da strcmp nos 
diz se o primeiro Nome deve vir antes ou depois do segundo! Ou seja, Não precisa usar 
condições if/else pra analisar cada caso separadamente!  
 
E se fosse de forma decrescente por Nome?  
 
É só >>INVERTER<< os parâmetros da função strcmp!!! Simples e prático! :) 
 
EX: return strcmp(a2­>nome, a1­>nome);  
 
************************************************************************************************ 
 
Os critérios de comparação não vão fugir muito disso não, crescente ou decrescente e 
ordenar por int/float e strings. Essas são todas as possibilidades, sendo que se você 
entendeu a comparação desse exemplo 2, sem riscos! :) 
 
Resumindo: Decore urgentemente a chamada da qsort, assim como o começo da função 
compara e entenda como faz as comparações de acordo com os critérios!  
 
OBS:​ Daqui em diante vou falar sobre como fazer o Quick Sort na mão.(sem usar a função 
qsort)  
Então se você puxou Prog 2 com um professor legal, já pode comemorar duplamente, pois 
esse bloco resumo acabou pra você! Clique no 'X' pra fechar o bloco e seja feliz! :D 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
 
­ Quick Sort: (Sem usar a função qsort)  
 
 
Sim, eu sei que é triste...não conseguiu vaga a tempo, critério de ordenação da matrícula 
mudou, turma lotou nos primeiros dias, sei como é, tristeza total.   
Mas como não tem jeito, vamos tentar pelo menos entender como funciona essa Quick Sort 
na mão? :D  
 
Uma notícia boa é que em algumas provas é dado a opção de ordenar usando a função 
qsort, mas como em outras não existe essa opção, então melhor nem arriscar! 
 
 
 
 
Vamos usar o mesmo enunciado do exemplo anterior:  
 
 
typedef struct aluno{ 
char nome[50]; 
int matricula; 
}Aluno; 
 
int compara (Aluno *a1, Aluno *a2){ 
if(a1­>matricula < a2­>matricula) return 1; 
else if(a1­>matricula > a2­>matricula) return ­1; 
return strcmp(a1­>nome, a2­>nome); 
} 
 
OBS:​ Opa! A função compara é menor e mais simples que a compara da função qsort, será 
que isso é um bom sinal? :O  
 
Agora vamos analisar a função ordena: 
 
void ordena (Aluno **v, int n){ 
int a, b; 
Aluno *pivo = v[0]; 
Aluno *temp; 
 
        a = 1; 
        b = n­1; 
 
        if(n < 2) return ; 
  
while(a <= b){ 
while(a < n && compara(v[a], pivo) <= 0) a++; 
while(compara(v[b], pivo) > 0) b­­; 
if(a < b){ 
temp = v[a]; 
v[a] = v[b]; 
v[b] = temp; 
a++; b­­; 
} 
} 
v[0] = v[b]; 
v[b] = pivo; 
ordena(v, b); 
ordena(&v[a], n­a); 
} 
 
OBS: ​Antes de tudo, observou no final da função as duas chamadas recursivas né?  
A única forma mais ""Tranquila"" de fazer o Quick Sort na mão, é através da recursão.  
 
A ideia

Crie agora seu perfil grátis para visualizar sem restrições.