// Ordinary recursive quicksort with different partitioning implementations
// See Sedgewick for details

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define generateRandom(minRange,maxRange) \
  (minRange)+abs(random()) % ((maxRange)-(minRange)+1)

typedef int Item;
#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) { Item t = A; A = B; B = t; } 
#define compexch(A, B) if (less(B, A)) exch(A, B)

Item *arr;
int arrSize;

void dump(Item *a,int low,int high)
{
int i;

if (low<=high)
{
  printf(" i     key\n");
  for (i=low;i<=high;i++)
    printf("%2d %7d\n",i,arr[i]);
}
}

int partitionBothRight(Item *a,int p,int r)
// From CLRS, 2nd ed.
// Conceptually the simplest partitioner
// Subscripts <= i store elements <= pivot (arr[r])
// Subscripts in range i+1 .. j store elements > pivot
{
int i,j;
Item x,temp;

printf("Input\n");
dump(arr,p,r);

x=arr[r];
i=p-1;
for (j=p;j<r;j++)
  if (!less(x,arr[j]))
  {
    i++;
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
  }
// Place pivot at final position for sort
temp=arr[i+1];
arr[i+1]=arr[r];
arr[r]=temp;

printf("Left output\n");
dump(arr,p,i);

printf("In final position\n");
printf("%2d %7d\n",i+1,arr[i+1]);

printf("Right output\n");
dump(arr,i+2,r);

return i+1;
}

void qsortBothRight(Item *a,int p,int r)
{
int q;

if (p<r)
{
  q=partitionBothRight(a,p,r);
  qsortBothRight(a,p,q-1);
  qsortBothRight(a,q+1,r);
}
}

int partition(Item *a,int ell,int r)
{ 
// From Sedgewick, but more complicated since pointers move
// towards each other.
// Elements before i are <= pivot.
// Elements after j are >= pivot.
int i = ell-1, j = r; Item v = a[r];

printf("Input\n");
dump(arr,ell,r);

for (;;)
  {
    // Since pivot is the right end, this while has a sentinel.
    // Stops at any element >= pivot
    while (less(a[++i], v)) ;
    // Stops at any element <= pivot (but not the pivot) or at the left end
    while (less(v, a[--j])) if (j == ell) break;
    if (i >= j) break; // Don't need to swap
    exch(a[i], a[j]);
  }
exch(a[i], a[r]);     // Place pivot at final position for sort

printf("Left output\n");
dump(arr,ell,i-1);

printf("In final position\n");
printf("%2d %7d\n",i,arr[i]);
printf("Right output\n");
dump(arr,i+1,r);

return i;
}

void quicksort(Item *a, int ell, int r)
{ 
if (r <= ell) return;
int i = partition(a, ell, r);
quicksort(a, ell, i-1);
quicksort(a, i+1, r);
}

int partitionFast(Item *a, int ell, int r)
{
// Similar to partition, but a little faster.  See problem 7.3.
// The returned value is NOT the final position for the pivot!
int i = ell-1, j = r+1; Item v = a[r];

printf("Input\n");
dump(arr,ell,r);

for (;;)
{
  while (less(a[++i], v)) ;
  // Note that j is initialized so this while stops at the pivot
  // the first iteration of the enclosing for.
  while (less(v, a[--j])) ;
  if (i < j)
    exch(a[i], a[j])
  else
  {
    printf("Left output\n");
    dump(arr,ell,i-1);

    printf("Right output\n");
    dump(arr,i,r);

    return i;
  }
}
}

void quicksortFast(Item *a, int ell, int r)
{ 
if (r <= ell) return;
int i = partitionFast(a, ell, r);
quicksortFast(a, ell, i-1);
quicksortFast(a, i, r);
}

int main()
{
int i,seed;

scanf("%d",&arrSize);
arr=(int*) malloc(arrSize*sizeof(int));
if (!arr)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}
scanf("%d",&seed);

printf("quicksort with both pointers going right\n");
srandom(seed);
for (i=0;i<arrSize;i++)
  arr[i]=generateRandom(0,999);
dump(arr,0,arrSize-1);
qsortBothRight(arr,0,arrSize-1);
dump(arr,0,arrSize-1);

printf("Running slow LR pointers quicksort\n");
srandom(seed);
for (i=0;i<arrSize;i++)
  arr[i]=generateRandom(0,999);
dump(arr,0,arrSize-1);
quicksort(arr,0,arrSize-1);
dump(arr,0,arrSize-1);
printf("Running fast LR pointers quicksort\n");
srandom(seed);
for (i=0;i<arrSize;i++)
  arr[i]=generateRandom(0,999);
dump(arr,0,arrSize-1);
quicksortFast(arr,0,arrSize-1);
dump(arr,0,arrSize-1);}