#include <stdio.h>

void QSort(int *array, int low, int high);
void Swap(int *array, int i1, int i2);
int table[]= { 7, 5, 12, 3, 8, 11, 4, 10, 9, 2, 6, 1 };

void main() {
  int i;
  QSort(table, 0, 11);
  printf("Ordered table:\n");
  for(i=0; i<12; i++)
    printf("%2d  ",table[i]);
  printf("\n\n");
}

void QSort(int *array, int low, int high) {
  int lo=low;
  int hi=high;
  /* Choose the array's midpoint as the partition element */
  int mid=array[(low+high)/2];
  /* Run over the array until the indices cross */
  while(lo<=hi) {
    /* Search in ascending order for the first element greater than or 
       equal to the partition element. */
    while((lo<high) && (array[lo]<mid))
      lo++;
    /* Search in descending order for the first element less than or 
       equal to the partition element. */
    while((hi>low) && (mid<array[hi]))
      hi--;
    /* Swap if necessary */
    if(lo<=hi) {
      Swap(array, lo, hi);
      lo++;
      hi--;
    }
  }
  /* sort the left partition when the right index has not yet reached
     the array's left border */
  if(low<hi)
    QSort(array, low, hi);
  /* sort the right partition when the left index has not yet reached
     the array's right border */
  if(lo<high)
    QSort(array, lo, high);
}

void Swap(int *array, int i1, int i2) {
  int temp=array[i1];
  array[i1]=array[i2];
  array[i2]=temp;
}

