Olá
Tenho uma duvida sobre o algoritmo Quick Sort, se puderem me ajudar, obrigado.
Dentro da função quick_sort eu não entendi esse momento no qual os dois valores se encontram e a troca é realizada. Pelo que entendi, os dois "while" caminham em direção ao centro ate encontrarem um valor que seja maior e um valor que seja menor que o pivo. Nesse momento 'esq' e 'dir' param de se mover, pois encontraram as posições dos dois valores que podem ser trocados para os lados opostos. Se 'esq' e 'dir' param nessas posições do vetor, como é possivel que eles acabem se encontrando, no caso do if (esq<=dir) para que a troca aconteça? Qual o erro na minha lógica? PS: Não assumam que os comentários no código estejam corretos, foi o que eu entendi até agora olhando para esse algoritmo.
#include<stdio.h>
#define tam 10
void imprimeVetor(int vetor[tam]){
for(int i=0;i<tam;i++){
printf("|%d| ",vetor[i]);
}
}
void quick_sort(int vetor[tam],int inicio,int fim){
int pivo,esq,dir,meio,aux;
//limites da esquerda e direita da regiao analisada
esq = inicio;
dir = fim;
//ajustando auxiliares do centro
meio = (int) (esq + dir) / 2; //meio = posicao do meio do vetor
pivo = vetor[meio]; //pivo = valor da posicao no meio do vetor
while(dir > esq){
//percorre a metade esquerda (sentido ->) até encontrar um valor que seja MAIOR que o pivo, então PARA nessa posição.
while(vetor[esq] < pivo){
esq = esq + 1;
}
//percorre a metade direita (sentido <-) até encontrar um valor que seja MENOR que o pivo, então PARA nessa posição.
while(vetor[dir] > pivo){
dir = dir - 1;
}
//quando os limites se cruzam, realiza a troca dos valores nas posições encontradas anteriormente.
if(esq <= dir){
//troca os valores dos lados do pivo
aux = vetor[esq];
vetor[esq] = vetor[dir];
vetor[dir] = aux;
//faz os limites laterais caminharem para o centro.
esq = esq + 1;
dir = dir - 1;
}
imprimeVetor(vetor);
printf("\n");
}
//AS RECURSÕES AGORA vão AJUSTAR AS METADES DIVIDIDAS PELO PIVO.
//recursao caso 1: dir agora esta no centro (os limites se cruzaram antes) e vai ate o inicio.
if(inicio < dir){
quick_sort(vetor,inicio,dir);
}
//recursao caso 2: esq agora esta no centro (os limites se cruzaram antes) e vai ate o fim.
if(esq < fim){
quick_sort(vetor,esq,fim);
}
}
int main(){
int vetor[tam] = {10,9,8,7,6,5,4,3,2,1};
imprimeVetor(vetor);
printf("\n");
quick_sort(vetor,0,tam); //passo (vetor,inicio,fim)
printf("\n");
return 0;
}