Dificuldades com ordenação - Quicksort

paulopimenta6
(usa Debian)

Enviado em 10/06/2021 - 18:09h

Olá Pessoal,

Estou estudando métodos de ordenamento usando o método do quicksort e na implementação que eu fiz coloquei alguns prints para identificar alguns pontos da iteração no ordenamento de um vetor. O meu problema é que numa dada iteração, quando o vetor já está todo ordenado, ainda há passagens no interior dos laços da função. Eu tentei identificar o que poderia ter dado errado, mas ainda assim não consegui identificar. Vou enviar o código e espero que possam me ajudar!

#include <stdlib.h>

#include <stdio.h>



void quick_sort(int array[], int primeiro, int ultimo){

    int i, temp, baixo, alto, separador;

    baixo=primeiro;

    alto=ultimo;

    separador=array[(alto+baixo)/2];



    do{

        printf("Passei aqui... \n");

        for(i=0; i<5; i++){

            printf("%d ", array[i]);

        }

        printf("\n");

        while(array[baixo]<separador){

            baixo++;

        }

        while(array[alto]>separador){

            alto--;

        }

        if(baixo<=alto){

            temp=array[baixo];

            array[baixo++]=array[alto];

            array[alto--]=temp;

        }

        printf("\nwhile(%d<=%d)\n", baixo, alto);

     }while (baixo<=alto);



     printf("\n(%d<%d)\n", primeiro, alto);

     if((primeiro<alto)){

         printf("Entre no condicional primeiro<alto \n");

         quick_sort(array, primeiro, alto);

     }



     printf("\n(%d<%d)\n", baixo, ultimo);

     if((baixo<ultimo)){

         printf("Entre no condicional baixo<ultimo \n");

         quick_sort(array, baixo, ultimo);

     }

}



int main(){

    //int valores[100], i;

    //for(i=0; i<100; i++){

    //    valores[i]=rand()%100;

    //    }

    int valores[5]={5,3,4,1,2}, i;

    quick_sort(valores, 0, 4);

    for(i=0; i<5; i++){

        printf("%d ", valores[i]);

        }



    } 

pegando os prints do terminal as saídas são essas:

Passei aqui... 

5 3 4 1 2 



while(1<=3)

Passei aqui... 

2 3 4 1 5 



while(3<=2)



(0<2)

Entre no condicional primeiro<alto 

Passei aqui... 

2 3 1 4 5 



while(2<=1)



(0<1)

Entre no condicional primeiro<alto 

Passei aqui... 

2 1 3 4 5 



while(1<=0)



(0<0)



(1<1)



(2<2)



(3<4)

Entre no condicional baixo<ultimo 

Passei aqui... 

1 2 3 4 5 



while(4<=2)



(3<2)



(4<4)

1 2 3 4 5 

 

E fica a dúvida por que logo quando houve a ordenação a função não parou e continuou as iterações.
Espero que possam me ajudar!

Um abraço a todos!

leandropscardua
(usa Ubuntu)

Enviado em 10/06/2021 - 19:49h

Acho q vc poderia começar a função quicksort c uma verificação se a lista tem 1 elemento, nesse caso não fazer nada. Atualmente tem um do... while q sempre executa ao menos uma vez. Algo como if (ultimo - primeiro <= 1) return;