Resumo_Ordenação

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

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 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 é a seguinte: A cada chamada da função ordena, definimos o primeiro elemento pra ser o Pivô e o objetivo de cada chamada da função é colocar o >>Pivô<< na ordem certa! Lembrando que o Pivô vai mudando por causa da recursão!
Declaramos dois contadores ('a' e 'b') pra andar nos índices do vetor e fazer as comparações com o Pivô. Colocamos 'a' >SEMPRE< na posição 1 e 'b' >SEMPRE< no final do vetor. (n-1)
while(a < n && compara(v[a], pivo) <= 0) a++;
Enquanto o primeiro elemento for menor ou igual ao segundo na comparação, incrementamos o contador 'a'.
OBS: a < n é uma prevenção, pois e se o Pivô for o maior elemento de todos? É justamente pra não ter risco do 'a' passar o limite do vetor!
while(compara(v[b], pivo) > 0) b--;
Enquanto o primeiro elemento for maior que o Pivô, decrementamos b.
OBS: Aqui não precisamos de prevenção, pois mesmo que todos os elementos sejam maiores que o Pivô, no pior caso, a comparação será do Pivô com ele próprio, ou seja, sem risco dele
sem maior que ele mesmo. :D 
Se após avançar os contadores, o contador 'a' continuar sendo menor que 'b' , acabamos de achar um elemento (v[a]) maior que o Pivô e que vem antes de um elemento menor que o Pivô! (v[b]). 
Nesse caso fazemos uma troca simples! Lembrando que o tipo da variável Temp pode mudar de acordo com o enunciado!
OBS: O objetivo era colocar o primeiro Pivô na ordem certa e através dessas comparações com o próprio Pivô, já conseguimos dar uma mini ordenada nos outros elementos! (Não quer dizer que será a posição definitiva deles!)
Mas se o contador 'a' ficar >Maior< que 'b' quer dizer que não há mais "Mini ordenações" pra se fazer" e já podemos colocar o Pivô na posição definitiva dele!
-------------------------------------//------------------------------------------
Imagina esse conjunto de valores sendo o nosso vetor e o número 25 é o Pivô: 
Vamos imaginar que ambos contadores já "avançaram" e o 'a' parou no 37 e o 'b' no 12. Ou seja, o contador 'a' ficou maior que o 'b'. 
25 12 37 48 57 86 33 92
Então pra colocar o Pivô na posição definitiva, basta trocar o 25 (Pivô) pelo 12 que é onde está o contador 'b'! E sempre que fazemos isso, incrementamos ambos contadores, pois essas posições já acabamos de ordenar! a++; b--; 
12 25 37 48 57 86 33 92
OBS: Assim que o Pivô está na posição correta, ele divide o vetor em dois sub-vetores que faltam ser ordenados! O primeiro Sub-vetor de elementos que estão à esquerda do Pivô e um segundo Sub-vetor de elementos que estão à direita do Pivô.
Mas não precisa se preocupar com mais nada, o resto é com a recursão! 
É só passar os parâmetros corretos: Nesse exemplo dos números, o primeiro sub-vetor só possui um elemento (12), faz sentido ordenar um vetor com um único elemento? NÃO! É por isso que é importante colocar essa condição no começo de tudo! 
>> if(n < 2) return ; << 
ordena(v, b);
ordena(&v[a], n-a);
OBS: E o segundo Sub-Vetor começa exatamente onde parou o contador 'a'! E pra representar o novo começo de um vetor qualquer, no caso, do nosso segundo Sub-Vetor, enviamos como parâmetro dessa forma: &v[a] 
E o tamanho é n-a (Total de posições (8) - contador 'a'(2) = 6 que será o tamanho do segundo Sub-Vetor) 
------------------------------------//--------------------------------------------
Bom, essa foi uma tentativa de explicar o Quick Sort nos mínimos detalhes. Se por acaso você leu tudo isso e não entendeu nada, sem problemas! Tenho mais duas cartas na manga! Haha 
- Assista esse vídeo que mostra exatamente como é o funcionamento da Quick Sort através da dança!
https://www.passeidireto.com/video/4750383/ordenacao-quick-sort-folk-dance
- Decore urgentemente a função ordena desse exemplo! =D 
-----------------------------------//---------------------------------------------