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

/* protótipo de função para escolha de pivô */
typedef char (*func_ptr1) (char[], int, int);
/* protótipo de função para comparação de dois elementos do vetor */
typedef int (*func_ptr2) (char, char);

/* Estratégia de escolha do pivô: último caracter é escolhido */
char pivoUltimo(char A[], int p, int f)
{
   return A[f];
}

/* Estratégia de escolha do pivô: caracter aleatório é escolhido */
char pivoAleatorio(char A[], int p, int f)
{
   double r01;
   time_t s;
   int indPivo;

   s=time(NULL);
   srand((unsigned int) s);

   /* número aleatório entre 0 e 1 */
   r01 = rand()/(double)RAND_MAX;

   indPivo = p + (f+1-p)*r01;

   return A[indPivo];
}


/* comparação em ordem crescente */
int ordemDecrescente(char a, char b)
{
   return (a >= b);
}

/* comparação em ordem decrescente */
int ordemCrescente(char a, char b)
{
   return (a <= b);
}



int particao(char A[], int p, int f, char pivo, func_ptr2 comp)
{
   int i, j;
   char temp;

   i = p-1;
   for (j=p; j < f; j++)
   {
      if (comp(A[j], pivo))
      {
         i++;
         /* Trocar A[i] com A[j] */
         temp = A[i]; A[i] = A[j]; A[j] = temp;
      }
   }
   /* Trocar A[i+1] com o pivot  A[f] */
   temp = A[i+1]; A[i+1] = A[f]; A[f] = temp;

   return (i+1);
}


/* QuickSort genérico*/
void genQuickSort(char A[], int p, int f, func_ptr1 escPivo, func_ptr2 comp)
{
   int q;
   char pivo;

   if (p < f)
   {
      /* Escolha o pivô */
      pivo = escPivo(A, p, f);

      q = particao(A, p, f, pivo, comp);
      //printf ("%d\n",q);
      genQuickSort(A, p, q-1, escPivo, comp);
      genQuickSort(A, q, f, escPivo, comp);
   }
}


int main(void)
{
   char s[] = "896475312";

   /* assinatura 1, ordem crescente e último elemento é pivô */
   printf ("antes  %s\n", s);
   genQuickSort(s, 0, (strlen(s)-1), pivoUltimo, ordemCrescente);
   printf ("depois %s\n\n", s);

   /* assinatura 2, ordem decrescente e último elemento é pivô */
   printf ("antes  %s\n", s);
   genQuickSort(s, 0, (strlen(s)-1), pivoUltimo, ordemDecrescente);
   printf ("depois %s\n\n", s);

   /* assinatura 3, ordem crescente e pivô aleatório */
   printf ("antes  %s\n", s);
   genQuickSort(s, 0, (strlen(s)-1), pivoAleatorio, ordemCrescente);
   printf ("depois %s\n\n", s);

   /* assinatura 4, ordem decrescente e pivô aleatório */
   printf ("antes  %s\n", s);
   genQuickSort(s, 0, (strlen(s)-1), pivoAleatorio, ordemDecrescente);
   printf ("depois %s\n\n", s);

   return 1;
}