// QUICKSORT FUNCAO //
int quickSORT(vetor * vec, int left, int right){
  int i, j, tamanho=right-left+1, posicao;
  char * aux;
  // com tamanho 0 ou 1 esta ordenado
  if(left>=right ) return 0;
    else {
          int pos = rand()%tamanho + left; // determina pivot
          // colocar pivot no fim
          aux= vec->elementos[pos].str;
          vec->elementos[pos].str = vec->elementos[right].str;
          vec->elementos[right].str = aux;
          // passo de parti��o
          i = left; j = right-1;
    while(1) {
        while (strcmp(vec->elementos[i].str,vec->elementos[right].str)< 0 && i < right) i++;
        while (strcmp(vec->elementos[right].str, vec->elementos[j].str)< 0 && j >= 0) j--;
        if (i < j){
        //trocar vec->elementos[i].str com vec->elementos[j].str
            aux= vec->elementos[i].str;
            vec->elementos[i].str = vec->elementos[j].str;
            vec->elementos[j].str = aux;
          }

    }
    //reposi�ao do pivot
    //caso os elementos centrais sejam maiores que o pivot
    if(strcmp(vec->elementos[i].str, vec->elementos[right].str)>0 && strcmp(vec->elementos[j].str, vec->elementos[right].str)>0){
    		aux= vec->elementos[i].str;
    		vec->elementos[i].str = vec->elementos[right].str;
    		vec->elementos[right].str = aux;
    		posicao=i;}
    //caso os elementos centrais sejam menores que o pivot
    if(strcmp(vec->elementos[i].str, vec->elementos[right].str)<0 && strcmp(vec->elementos[j].str, vec->elementos[right].str)<0){
    		aux= vec->elementos[j+1].str;
    		vec->elementos[j+1].str = vec->elementos[right].str;
    		vec->elementos[right].str = aux;
    		posicao=j+1;}
    //caso um seja maior e outro menor ou entao iguais
    else{
    //caso os elementos estejam desordenados
    	if(strcmp(vec->elementos[i].str, vec->elementos[j].str)>0){
    		aux= vec->elementos[i].str;
    		vec->elementos[i].str = vec->elementos[j].str;
    		vec->elementos[j].str = aux;}
    //trocar o pivot de posi�ao com o valor mais baixo
    	aux= vec->elementos[i].str;
    	    		vec->elementos[i].str = vec->elementos[right].str;
    	    		vec->elementos[right].str = aux;
    	    		posicao=i;}
    //ordenar o sub-vector a esquerda do elemento ordenado
    quickSORT(vec, left, posicao-1);
    //ordenar o sub-vector a direita do elemento ordenado
    quickSORT(vec, posicao + 1 , right);
  }
}


int vetor_ordena_qsort(vetor* vec){
    int left = 0, right = vetor_tamanho(vec);
  quickSORT(vec, left, right);
return 0;
}