QuickSort with last element as pivot

Question

QuickSort with last element as pivot

Navigation

#1 by (0 votes)

1

The following code should receive a string 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 entry:

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

output 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 output I'm getting is this:

{3 4 2 5 1 8 9}

{1 2 4 5 3 8 9}

I know that the problem is, in the second call of the partition function, where the pivot element is the smallest element of the vector to be sorted, now does anyone have any idea how I outline this problem?

c c++

asked by anonymous 26.03.2016 / 02:18

1 answer

problems with conversion haml to html / erb Foreign Keys from a SqlConnection.GetSchema ()

score 0 · 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 part is a little different from yours !!! but I'll 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 .. what if the same concept of yours !!