/* partition function  accorting to Hoare, used in Quicksort */

void partition (int a[], int left, int right, int pivotindex,
     /* OUT limits of partition */  int* iloc, int* jloc)

{   int pivot = a[pivotindex];          /* Hoare's X */
    int i=left, j=right;
    int temp;
  while (1)
  {
    for (;i < right; i++) 		/* up:*/
	if (a[i] > pivot) break;

    for (; j > left; j--) 		/* down: */
	if (a[j] < pivot) break;	
					/* change: */
    if (i >= j) break;   		/* go to done; */
        temp = a[i];    	/* exchange */
        a[i++] = a[j];
        a[j--] = temp;		/* and advance i & j */
  }
/* done scans, now put pivot between partitions */

    if (pivotindex < j)
    {  a[pivotindex] = a[j];
       a[j--] = pivot;
    }
    if (pivotindex > i)
    {  a[pivotindex] = a[i];
       a[i++] = pivot;
    }
    *iloc = i;		/* return OUT args for partition range */
    *jloc = j;
} 			/* end partition */