Ir ao conteúdo
  • Cadastre-se
kazamuru

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

Posts recomendados

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

 

Compartilhar este post


Link para o post
Compartilhar em outros sites
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?

 

  • Obrigado 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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.

Compartilhar este post


Link para o post
Compartilhar em outros sites
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

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...