C Como entender esse trecho de código do algoritmo QuickSort?

[kazamuru]

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;
}

 

[arfneto]

Em 16/11/2019 às 09:19, kazamuru disse:

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?

Olá!

 

Os dois segmentos nunca se encontram. O limite entre eles é o pivo. As trocas acontecem entre os segmentos, que tem um tamanho elástico digamos: você apenas garante que tudo que ficou a esquerda do pivo é menor e tudo que fica a direita é maior e vai reajustando os tamanhos. Quando conseguir isso então faz o mesmo com os dois segmentos, recursivamente ou interativamente mesmo, e continua fazendo isso até os segmentos ficarem bem pequenos, com 1 elemento ou nenhum. E aí estará tudo em ordem.

 

é mais rápido para classificar do que para explicar. É muito rápido.

 

Exemplo com 9 números

[1 3 4 12 10 10 8 9 0]

Se o primeiro pivo for o 9 vai ficar com

[1 3 4 8 0] 9 [12 10 10] 

Ao fim do primeiro passo

 

No caso do primeiro segmento com o pivo 8

[1 3 4 0]  [8]  [9]  [12 10 10]

E usando o 4 como pivo

[0 1 3] [4] [8] [9] [12 10 10]

E usando o 1 como pivo

[0] [1] [3] [4] [8] [9] [12 10 10]

E usando o 10 como pivo

[0] [1] [3] [4] [8] [9] [10] [10] [12]

 

E não é que ficou tudo em ordem?

 

[arfneto]

Esqueci de comentar: é importante considerar que esse troço funciona in-place, por exemplo no próprio array, então uma vez que o pivo chega no lugar certo --- ou os segmentos, dependendo de como você vê isso --- são posições permanentes.

É como o HeapSort, onde a cada passo sai um classificado, ou o fim de cada loop no bubble sort onde o maior vai "afundando" por exemplo

[kazamuru]

Muito obrigado pelo seu tempo e empenho em me explicar o algoritmo Arfneto, agora ficou mais claro.

adicionado 2 minutos depois

8 horas atrás, arfneto disse:

Esqueci de comentar: é importante considerar que esse troço funciona in-place, por exemplo no próprio array, então uma vez que o pivo chega no lugar certo --- ou os segmentos, dependendo de como você vê isso --- são posições permanentes.

É como o HeapSort, onde a cada passo sai um classificado, ou o fim de cada loop no bubble sort onde o maior vai "afundando" por exemplo

Entendi. Não precisa de um vetor adicional, por exemplo, tudo acontece no mesmo intervalo de endereços na memória. Muito bom o quicksort.

[arfneto]

6 horas atrás, kazamuru disse:

Entendi. Não precisa de um vetor adicional, por exemplo, tudo acontece no mesmo intervalo de endereços na memória. Muito bom o quicksort

Sim. É muito bom e muito rápido, como o MErgeSort e o HeapSort. Genial.

 

E se você inclui a função que compara fica genérico, de modo que pode classificar qualquer coisa mesmo. Tipo pegar uma tabela e classificar por Nome e depois por CPF e depois pelo CEP do local de entrega e tal.

 

Note que C inclui uma implementação de Quicksort declarada assim

void qsort(
    void*  inicio,
    size_t total_de_itens, 
    size_t tamanho de cada um, 
    int    (*funcao_que_compara)(const void *, const void*)
);

 

E você pode usar para classificar qualquer coisa para a qual possa apontar