[INF1007] Resumo Ordenação

Programação II 
Monitor: André Vicente Pessanha 
Resumo Ordenação: 
 
*************************************************************************************************** 
 
OBS:​ Essa matéria só cai na P2! 
 
*************************************************************************************************** 
 
­ Descrição:  
 
Usamos ordenação para ordenar vetores de forma crescente ou decrescente. (De acordo 
com o critério pedido no enunciado) 
 
 
Assim como na Busca binária, toda função de ordenação é >SEMPRE< acompanhada de 
uma função de comparação! Sendo que na maioria das provas, já é organizado dessa 
forma, letra A pedindo a função de comparação, letra B a função que ordena, etc. 
 
Mas também é possível cobrarem os dois no mesmo item da questão! Mesmo se não 
deixarem claro, use sempre uma função auxiliar pra fazer a comparação! 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
Tipos de ordenação:  
 
­ Bolha:  
 
OBS: Raramente cobrado em prova, mas é bom dar uma lida como prevenção! 
 
Exemplo: Ordenar um vetor de ponteiros para Aluno em ordem crescente de matrícula. 
 
 
typedef struct aluno{ 
char turma[50]; 
int matricula; 
float nota; 
}Aluno; 
 
int comparaAluno (Aluno *a1, Aluno *a2){ 
if(a1­>matricula > a2­>matricula) return 1; 
else if(a1­>matricula < a2­>matricula) return ­1; 
return 0; 
} 
 
************************************************************************************************** 
 
Regra Importante: 
 
Na função auxiliar, sempre comparamos dois elementos seguidos do vetor e sempre de 
acordo com o critério de ordenação do enunciado. 
 
Como foi pedido pra ordenar de forma crescente por matrícula:  
 
Se a matrícula do primeiro for maior que a do segundo, retornamos 1 para representar que 
ele deve vir >>DEPOIS<<! Da mesma forma, se o primeiro for menor que o segundo, 
retornamos ­1 pra representar que além de já estar na ordem correta, ele deve continuar 
vindo >>ANTES<< do segundo elemento. E por fim, se forem iguais, retornamos zero pra 
representar um "Tanto faz a ordem" :) 
 
************************************************************************************************** 
 
void bolha (Aluno **a, int n){ 
int fim, i, troca; 
Aluno * temp; 
 
for (fim = n­1; fim > 0; fim­­){ 
troca = 0; 
for(i = 0; i<fim; i++){ 
if(comparaAluno (a[i], a[i+1]) == 1){ 
temp = a[i]; 
a[i] = a[i+1]; 
a[i+1] = temp; 
troca = 1; 
} 
} 
if(troca == 0) return ; 
} 
} 
 
OBS:​ A cada "passo"(Término do segundo 'for'), o maior elemento é colocado no final do 
vetor. Se houver trocas, atribuimos troca = 1; pra sinalizar que houve pelo menos uma troca! 
Pois se caso não houver trocas, faz sentido continuar ordenando? 
  
NÃO! É justamente por isso que ao término de cada "passo", testamos se a variável troca é 
igual a zero, se for o caso, encerramos a função! E pra isso dar certo, precisamos inicializar 
a variável troca com zero sempre >> antes << de entrar no segundo 'for'! 
 
OBS:​ >> return ; << é uma forma de encerrar manualmente funções do tipo void! 
 
Sempre enviamos de 2 em 2 elementos do vetor para a função Compara. Sem risco de 
ultrapassar o limite do vetor, pois como a cada "passo" (Assim que termina o segundo 'for') 
o maior elemento vai pro final do vetor, não faz sentido fazer comparações com os 
elementos que já foram colocados no final do vetor, pois já estão ordenados! 
 
É justamente isso que o primeiro 'for' controla, como se a cada "passo" o tamanho do vetor 
tivesse um elemento a menos a ser ordenado. 
 
OBS​: No geral, >>TODA<< função bolha é assim, só muda um mini detalhe ou outro! Nesse 
exemplo foi um vetor de ponteiros para struct, mas poderia ser um vetor de ponteiros para 
char ou um simples vetor de inteiros. Então o que vai mudar são os parâmetros que você 
envia para a função compara e o tipo de retorno da função busca. 
 
OBS2:​ Para fazer a troca precisamos sempre de uma variável auxiliar pra armazenar 
temporariamente o primeiro elemento. 
 
temp = a[i];  
 
Mas muito cuidado! Pois o tipo da variável temp pode mudar também! Nesse caso 
declaramos como Aluno *temp porque cada posição do vetor armazena um ponteiro para 
Aluno! Mas se fosse um simples inteiro, teriamos que declarar como: int temp; 
 
OBS:​ Se por acaso você não entendeu nada até agora, sem problemas! Assista esse vídeo 
que mostra exatamente como é o funcionamento da Bolha através da dança! (Sim, você leu 
certo! Haha) 
 
https://www.passeidireto.com/video/4750391/ordenacao­bolha­folk­dance 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
 
­ Ordenação Quick Sort: 
 
 
Existem dois tipos de ordenação Quick Sort:  
 
­ Implementando o algoritmo inteiro na mão. Tenta imaginar um algoritmo grande, agora 
imagina um 3 vezes maior e complexo. Esse é o Quick Sort feito a mão! D: 
 
­ Usando a função qsort da stdlib.h e sendo feliz! :) 
 
OBS: Em ambos os casos precisa criar uma função auxiliar de comparação!  
 
É exatamente aqui, (sim, aqui mesmo!) que é a >>GRANDE<< diferença de puxar Prog 2 
com um professor legal! Se esse for o seu caso, já pode começar a comemorar, pois você 
não vai precisar decorar e nem implementar o Quick Sort na mão! Mesmo se o enunciado 
deixar bem claro que quer que você faça na mão! :D 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
 
­ Quick Sort: (Usando a função qsort da stdlib.h)  
 
Exemplo: Ordenar um vetor de ponteiros para Aluno em ordem decrescente de matrícula e 
para matrículas iguais, ordenar de forma crescente por nome.  
 
OBS:​ Esse exemplo é bem parecido com o primeiro, mas dessa vez são dois critérios de 
comparação. Atenção total nas mudanças na função de comparação! 
 
typedef struct aluno{ 
char nome[50]; 
int matricula; 
}Aluno; 
 
int compara (const void *v1, const void *v2){ 
Aluno *a1 = *( (Aluno **)v1); 
Aluno *a2 = *( (Aluno **)v2); 
 
if(a1­>matricula < a2­>matricula) return 1; 
else if(a1­>matricula > a2­>matricula) return ­1; 
return strcmp(a1­>nome, a2­>nome); 
} 
 
void ordena (Aluno **a, int n){ 
qsort(a, n, sizeof(Aluno *), compara); 
} 
 
*************************************************************************************************** 
 
Sim, é isso mesmo, esse é o tamanho da função ordena, uma simples linha! :O 
 
Ela recebe como parâmetro o vetor de ponteiros para Aluno, seu tamanho e é só fazer a 
chamada da função qsort! 
 
Parâmetros da função qsort:  
 
1 ­ Um vetor (Pode ser qualquer um!) 
 
2 ­ Tamanho do vetor (Quantidade de posições) 
 
3 ­ Tamanho (Em bytes) em cada posição. 
 
4 ­ Ponteiro para a função de comparação. (Wait...Ponteiro pra função!? WHAT!? O_O) 
 
 
Sim, isso seria uma matéria nova, mas não é ensinado com detalhes em Prog 2, somente 
como se envia como parâmetro e >>Somente<< ao chamar a qsort! 
 
O mais parecido que vimos até então foi chamar uma função dentro de outra:  
 
Ex: printf("Resultado: %d\n", soma(x, y));  
 
Pra passar o endereço (Ponteiro) de uma função, é só passar o seu nome como parâmetro! 
Mas cuidado! Isso é algo específico da qsort! (Ela já espera receber esse parâmetro!)  
E Dessa forma a função qsort pode chamar a função compara quantas vezes precisar! 
 
Sobre o Tamanho em bytes (Terceiro parâmetro), é só pensar assim: Temos um vetor de 
ponteiros para struct, o que temos em cada posição?  Um ponteiro para struct, né? 
Então é justamente o tamanho disso que a qsort precisa! E usamos a sizeof() pra conseguir 
a quantidade de bytes. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
 
 
int compara (const void *v1, const