#include <stdio.h>

#define TAMANHO 16

void mostra_vetor(int v[]) {
  int i, j;
  for (i = TAMANHO-1; i >=0; i--) {
    printf("|");
    for (j = 0; j < TAMANHO; j++) 
      if (v[j] == i)
	printf(" XXX");
      else
	printf("    ");	
    printf("\n");
  }
  for (j = 0; j <= 4* TAMANHO; j++) 
      printf("-");    
  printf("\n");
  printf ("{  %2d", v[0]);
  
  for (i = 1; i < TAMANHO; i++) {
    printf (", %2d", v[i]);
  }

  printf ("}\n");
  
}

int separa (int v[], int p, int r) {

  int c = v[p]; /*Pivô*/
  int i = p+1;
  int j = r;
  int t;

  while (i <= j) {
    if (v[i] <= c) ++i;
    else if (c < v[j]) --j; 
    else {
      t = v[i]; 
      v[i] = v[j]; 
      v[j] = t;
      ++i; --j;
      }
  }

  t = v[p]; 
  v[p] = v[j]; 
  v[j] = t;
  mostra_vetor(v);
  return j; 
}

void quicksort (int v[], int p, int r) {
  int j;
  if (p < r) {
    j = separa (v, p, r);
    quicksort (v, p, j-1); 
    quicksort (v, j+1, r);
  }
}


int main () {
  int vetor[TAMANHO] = {13,7,2,5,9,11,4,15,0,10,1,12,6,14,3,8};

  mostra_vetor(vetor);
  quicksort (vetor, 0, TAMANHO - 1);
  mostra_vetor(vetor);
  
  return 0;
}