2

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?

1
  • Vê se consegues implementar o "quick sort" sem o artifício do elemento extra. O primeiro if dentro do ciclo while na função particiona() parece-me errado. (Estou no telemóvel, sem acesso a um compilador, não posso testar)
    – pmg
    Commented 26/03/2016 às 10:59

1 Resposta 1

-1

**Então eu tenho esse código aqui **

#include <stdio.h>
#include <stdlib.h>

#define T 5

void mostraVetor(int *v);
void troca(int *a, int *b);
int particionar(int *v, int inicio, int fim);
void quickSort(int *v, int inicio, int fim);

// Fun??o principal
int main()
{
  int vetor[T] = {7, 3, 9, 4, 2};

  mostraVetor(vetor);
  quickSort(vetor, 0, T-1);
  mostraVetor(vetor);

  return 0;
}

// Fun??es auxiliares
void mostraVetor(int *v)
{
  int i;
  printf("\n\n");
  for (i = 0; i < T; i++) {
    printf("%d\t", v[i]);
  }
  printf("\n\n");
}

void troca(int *a, int *b)
{
  int aux = *a;
  *a = *b;
  *b = aux;
}

int particionar(int *v, int inicio, int fim)
{
  int pivo, i, j;

  pivo = v[(inicio+fim)/2];
  i = inicio - 1;
  j = fim + 1;

  printf("Pivo.....: %d\n", pivo);
  printf("i........: %d\n", i);
  printf("j........: %d\n\n", j);
  system("pause");

  while (i < j) {

    // Primeira metade
    do {
      j--;
      printf("j........: %d\n\n", j);
      system("pause");
    } while (v[j] > pivo);

    // Segunda metade
    do {
      i++;
      printf("i........: %d\n\n", i);
      system("pause");
    } while (v[i] < pivo);

    if (i < j)
      troca(&v[i], &v[j]);

    mostraVetor(v);
  }

  return j;
}

void quickSort(int *v, int inicio, int fim)
{
  int q;

  if (inicio < fim) {
    printf("Inicio....:%d\n", inicio);
    printf("Fim.......:%d\n\n", fim);
    system("pause");
    q = particionar(v, inicio, fim);
    printf("q.........:%d\n\n", q);
    quickSort(v, inicio, q);
    quickSort(v, q+1, fim);
  }

}

meu separa esta um pouco diferente do seu !!! mais vou compilar o seu.. pois o erro esta nele.. assim que fizer isso eu posto pra ti.. por enquanto deixo pra ti esse código ..que se o mesmo conceito do seu!!

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .