/* 
   Algoritmos e Estruturas de Dados II - 2004
   quick.c
   Versão 1.0; 4/3/2004
*/

#include <stdio.h>

int v[12]={-1000,3,5,1,79,4,67,8,11,-1,23,1000};

void troca(int i, int j, int v[]) {
  int aux;

  aux = v[i];
  v[i] = v[j];
  v[j] = aux;
}

void quicksort(int inf, int sup, int v[]) {
  int esq, dir, elem, aux;

  esq = inf+1;
  dir = sup;
  elem = v[inf];
  while (v[esq] < elem)
    esq = esq + 1;
  while (v[dir] > elem)
    dir = dir - 1;
  do {
    if (esq < dir) {
      troca(esq, dir, v);
      esq = esq + 1;
      dir = dir - 1;
    }
    while (v[esq] < elem)
      esq = esq + 1;
    while (v[dir] > elem)
      dir = dir - 1;
  }
  while (esq < dir);
  troca(inf, dir, v);
  if (inf < dir - 1) quicksort(inf, dir - 1, v);
  if (dir + 1 < sup) quicksort(dir+1, sup, v);
}

void print_vector(int inf, int sup, int v[]) {
  int i;

  printf("\n");
  for (i = inf; i <= sup; i = i+1)
    printf("%d ", v[i]);
  printf("\n");
}

int main() {
  print_vector(1,10,v);
  quicksort(1,10,v);
  print_vector(1,10,v);
}