Dificuldades com ordenação - Quicksort

1. Dificuldades com ordenação - Quicksort

Paulo Pimenta
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!



  


2. Re: Dificuldades com ordenação - Quicksort

leandro peçanha scardua
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;