O seguinte código deveria receber uma sequência de caracteres separados por espaço e ordená-los:
#include <stdio.h>
#include <stdlib.h>
int particiona(int *vector,int inicio,int fim){
int i,j,guarda,aux;
i = inicio-1, j = inicio, guarda = vector[fim];
while(j < fim){
if((vector[j]>vector[i]) && (vector[j]<guarda) && (j-i)<=1){
i++;
j++;
}
if((vector[j] > vector[i]) && (vector[j] > guarda)){
j++;
}
if((vector[i] > vector[j]) && (vector[j] < guarda) && (j-i)>1){
aux = vector[j];
vector[j] = vector[i+1];
vector[i+1] = aux;
i++,j++;
}
if((vector[j] > vector[i]) && (vector[j] < guarda) && (j-i)>1){
aux = vector[j];
vector[j] = vector[i+1];
vector[i+1] = aux;
i++,j++;
}
}
vector[fim] = vector[i+1];
vector[i+1] = guarda;
return (j-1);
}
void ordena(int *vector,int inicio,int fim,int tam){
if(inicio < fim){
int j,i;
j = particiona(vector,inicio,fim);
if(j == tam-1){
for(i=1; i<tam+1; i++)
printf("%d ",vector[i]);
}
ordena(vector,inicio,j-1,tam);
ordena(vector,j+1,fim,tam);
}
}
int main(void){
int *vector,i=1,N,num;
scanf("%d",&N);
vector = (int *)malloc((N+1)*sizeof(int));
vector[0] = -1;
while(i < (N+1)){
scanf("%d",&num);
vector[i++] = num;
}
ordena(vector,1,N,N);
printf("\n");
for(i=1; i<N+1; i++)
printf("%d ",vector[i]);
return 0;
}
recebendo essa entrada:
{7}
{3 4 9 2 5 1 8}
a saída deveria ser:
{3 4 2 5 1 8 9} /*Esta saída é exibida logo após a primeira chamada da função particiona*/
{1 2 3 4 5 8 9} /*Saída, após todas as chamas recursivas do método ordena serem feitas*/
Mas, a saída que estou obtendo é essa:
{3 4 2 5 1 8 9}
{1 2 4 5 3 8 9}
sei que o problema esta, na segunda chamada da função particiona, onde o elemento pivô é o menor elemento do vetor a ser ordenado, agora alguém tem alguma ideia de como eu contorno este problema?
if
dentro do ciclowhile
na funçãoparticiona()
parece-me errado. (Estou no telemóvel, sem acesso a um compilador, não posso testar)