/*********** Autor:
 ***********************/

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

/**/
void Fill_Vector (int vect[], int vect_size);

/**/
void Quick_Sort (int vect[], int p ,int vect_size);

int main ()
{
   long int num_trocas = 0, num_comparacoes = 0,p=0;

   int vect_size = 10;

   int elements[vect_size];

   /*Inserindo elementos*/
   Fill_Vector (elements,vect_size);

   /*Verificando os valores inseridos*/
   int i;
  // printf("Valores: \n");
   for (i = 0; i < vect_size; i++) {
      printf("Posição: %d, valor: %d\n", i, elements[i]);
   }

   /*Ordenando o vetor*/
   Quick_Sort (elements, p ,vect_size);

   //printf("\n\nValores ordenados: \n");
   for (i = 0; i < vect_size; i++) {
      printf("Posição: %d, valor: %d\n", i, elements[i]);

   }

   clock_t clock_start, clock_end;

   double elapsed;

   clock_start = clock();


    clock_end = clock();

   elapsed = ((double) (clock_end - clock_start)) / CLOCKS_PER_SEC;

   printf ("Tam. do vetor: %d, n. de trocas: %d, n. de comparações: %d, tempo de execução : %f\n", vect_size, num_trocas, num_comparacoes, elapsed);

   system("pause");
   return 0;
}


/*Esta função ... */

int Particiona (int vect[], int p,int vect_size)
{
     int x = vect[vect_size-1];
     int i = p-1;
     int temp;
     for(int j = p; j < vect_size; j++)
     {
          if (vect[j] <= x)
          {
             i++;

             temp = vect[i];
             vect[i] = vect[j];
             vect[j] = temp;

          }
          int aux;
          aux = vect[i+1];
          vect[i+1] = vect[vect_size];
          vect[vect_size] = aux;



     }

     return i+1;
}


void Quick_Sort (int vect[], int p ,int vect_size)
{
   //long int num_trocas = 0, num_comparacoes = 0;

   //clock_t clock_start, clock_end;

   //double elapsed;

   //clock_start = clock();

   /*Codifique o algoritmo!!!!!!!!!!!!!!!!*/


	if(p < vect_size)
    {
        int q = Particiona(vect, p ,vect_size);
        Quick_Sort(vect, p, q-1);
        Quick_Sort( vect, q+1, vect_size);
    }




   system("pause");

}

/*Esta função recebe um vetor {vect} vazio de tamanho {vect_size}
  e o preenche completamente com valores aleatórios.*/
void Fill_Vector (int vect[], int vect_size)
{
   /*Inicializando a função que gera números aleatórios com uma semente {time(NULL)}.
   Isso evita que a sequência de números aleatórios gerada seja sempre
   a mesma. Em caso de curiosidade, comente a chamada abaixo e verifique. */
   srand(time(NULL));

   /*Constante que define o maior valor inteiro possível no vetor*/
   int max_value = 10000;

   int i;
   for (i = 0; i < vect_size; i++) {
      /*O módulo abaixo evita que os valores sejam maiores que {max_value}*/
      vect[i] = rand() % max_value;
   }
}