Quicksort with last element as pivot

Question

The following code should receive a sequence of characters separated by space and sort them:

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

receiving this input:

{7}  
{3 4 9 2 5 1 8}

the exit should be:

{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*/

But the way out I’m getting is this:

{3 4 2 5 1 8 9}

{1 2 4 5 3 8 9}

I know the problem is, in the second call of the partitioning function, where the pivot element is the smallest element of the vector to be ordered, now someone has some idea of how I outline this problem?

Answer 1

**So I have this code here **

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

}

my separates this a little different from your !!! but I will compile your.. because the error is in it.. as soon as I do this I put it to you.. for now I leave you this code .. that if the same concept of yours!!