// Traces the basic partitioning technique in Sedgewick

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

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 i,int j)
{
int k;

for (k=0;k<arrSize;k++)
{
  if (k==i)
    printf("A");
  else
    printf(" ");
  if (k==j+1)
    printf("B");
  else
    printf(" ");
  printf("%2d ",arr[k]);
}
if (j==arrSize-1)
  printf("B");
}

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];

for (;;)
  {
    // Since pivot is the right end, this while has a sentinel.
    // Stops at any element >= pivot
    while (1)
    {
      ++i;
      dump(a,i,j);
      if (!less(a[i], v))
        break;
      printf(" Left continues\n");
    }
    printf(" Left positioned\n");
    // Stops at any element <= pivot (but not the pivot) or at the left end
    while (1)
    {
      --j;
      dump(a,i,j);
      if (!less(v,a[j]))
        break;
      if (j == ell) break;
      printf(" Right continues\n");
    }

    if (i >= j) break; // Don't need to swap
    printf(" Right positioned\n");
    exch(a[i], a[j]);
    dump(a,i,j);
    printf(" After swap\n");
  }
printf(" Pointers collided\n");
exch(a[i], a[r]);     // Place pivot at final position for sort

return i;
}

int main()
{
int i,j;

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

for (i=0;i<arrSize;i++)
  scanf("%d",arr+i);

i=partition(arr,0,arrSize-1);
for (j=0;j<arrSize;j++)
  if (j==i)
    printf(" <%2d>",arr[j]);
  else
    printf("  %2d ",arr[j]);
printf(" Pivot positioned\n");
}