A maior rede de estudos do Brasil

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

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

é 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  
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­

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