#include <stdio.h>
#define N 13
#define TRUE 1
/******************************************************************************
Exercício proposto em sala : 
     Escreva a função 'separa()' que tem os seguintes parâmetros:
     um vetor de inteiros v
     índices i e j, inteiros que delimitam um intervalo nesse vetor (i >= j).
     A função deve rearranjar os elementos do vetor da seguinte forma:
         supondo w o valor do último elemento do intervalo (v[j])
           - o trecho v[i] .. v[k-1] deve conter os valores de v menores que w
           - v[k] deve conter o valor w
           - 0 trecho v[k+1] .. v[j] deve conter os valores de v maiores ou 
              iguais a w.
              
    Suponha disponível a função  troca(int v[], int i, int j); que troca
    o valor de v[i] com v[j].
******************************************************************************/

int v[] = { 12, 3, 21, 2, 11, 47, 51, 18, 33, 11, 9, 37, 31 };
    
/**
    troca o valor dos elementos das posições i e j
    de um vetor (protótipo)
**/
void troca(int v[],int i, int j);

/**
   Rearranja os elementos do vetor de acordo com
   o exercício descrito acima. Retorna o índice
   do elemento usado com o base para a separação
   (também conhecido como pivô).
**/
int separa(int v[], int i, int j){
    int jj = j;
    int k = v[j];
    while(1){
        while(v[i] < k)  i++;
        while(v[j] >= k) j--;
        if(i < j) troca(v,i,j);
        else {
            troca(v,i,jj);
            return i;
        }
    }
}

/**
   Ordena um trecho de um vetor, usando a função separa().
   Essa função implementa o método conhecido como 'quicksort',
   que na média é um dos métodos mais eficientes para ordenação.
   Parâmetros:
       v: vetor contendo o trecho a ser ordenado
       i: índice do elemento inicial do intervalo
       j: índice do elemento final do intervalo
**/
void ordena(int v[],int i, int j){
    if(i >= j) return;      // nada a fazer, o intervalo tem 0 elementos
    int k = separa(v,i,j);  // senão separa o vetor 
    ordena(v,i,k-1);        // ordena recursivamente o primeiro trecho
    ordena(v,k+1,j);        // ordena recursivamente o segundo trecho
}

/** implementação da função troca() **/
void troca(int v[],int i, int j){
     int t = v[i];
     v[i] = v[j];
     v[j] = t;
}

/** escreve os valores do vetor **/
void escreve(int v[], int i, int j){
     int k;
     for(k = i; k <= j; k++) printf("%d ",v[k]);
     printf("\n");    
}


int main(){
    escreve(v,0,N-1);
    ordena(v,0,N-1);
    escreve(v,0,N-1);
    system("PAUSE");
}