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

import java.util.Scanner;
import java.util.Random;

public class qsortRS
{

  static ITEM[] arr;
  static int arrSize;

  static boolean less(ITEM x,ITEM y)
  {
    return x.less(y);
  }

  static void exch(ITEM[] a, int i, int j)
  {
    ITEM t = a[i];
    a[i] = a[j];
    a[j] = t;
  }

  static void dump(ITEM[] a,int low,int high)
  {
    if (low<=high)
    {
      System.out.print(" i     key    data\n");
      for (int i=low;i<=high;i++)
        System.out.format("%2d %7d %7d\n",i,arr[i].getValue(),
          arr[i].getData());
    }
  }

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

    System.out.print("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;

    System.out.print("Left output\n");
    dump(arr,p,i);

    System.out.print("In final position\n");
    System.out.format("%2d %7d %7d\n",i+1,arr[i+1].getValue(),
      arr[i+1].getData());

    System.out.print("Right output\n");
    dump(arr,i+2,r);

    return i+1;
  }

  static 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);
    }
  }

  static int partition(ITEM a[], int l, 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 = l-1, j = r; ITEM v = a[r];

    System.out.print("Input\n");
    dump(arr,l,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 == l) break;
        if (i >= j) break; // Don't need to swap
        exch(a, i, j);
      }
    exch(a, i, r);     // Place pivot at final position for sort

    System.out.print("Left output\n");
    dump(arr,l,i-1);

    System.out.print("In final position\n");
    System.out.format("%2d %7d %7d\n",i,arr[i].getValue(),arr[i].getData());

    System.out.print("Right output\n");
    dump(arr,i+1,r);

    return i;
  }

  static void quicksort(ITEM[] a, int l, int r)
  { 
    if (r <= l) return;
    int i = partition(a, l, r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
  }

  static int partitionFast(ITEM a[], int l, 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 = l-1, j = r+1; ITEM v = a[r];

    System.out.print("Input\n");
    dump(arr,l,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, j);
      else
      {
        System.out.print("Left output\n");
        dump(arr,l,i-1);

        System.out.print("Right output\n");
        dump(arr,i,r);

        return i;
      }
    }
  }

  static void quicksortFast(ITEM[] a, int l, int r)
  { 
    if (r <= l) return;
    int i = partitionFast(a, l, r);
    quicksortFast(a, l, i-1);
    quicksortFast(a, i, r);
  }

  public static void main(String[] args)
  {
  int i,seed;
  Random generator;

  Scanner sc=new Scanner(System.in);
  arrSize=sc.nextInt();
  arr=new ITEM[arrSize];
  seed=sc.nextInt();

  System.out.print("quicksort with both pointers going right\n");
  generator=new Random(seed);
  System.out.print(" i     key    data\n");
  for (i=0;i<arrSize;i++)
  {
    arr[i]=new ITEM(generator.nextInt(1000),i);
    System.out.format("%2d %7d %7d\n",i,arr[i].getValue(),arr[i].getData());
  }
  qsortBothRight(arr,0,arrSize-1);
  System.out.print(" i     key    data\n");
  for (i=0;i<arrSize;i++)
    System.out.format("%2d %7d %7d\n",i,arr[i].getValue(),arr[i].getData());

  System.out.print("Running slow LR pointers quicksort\n");
  generator=new Random(seed);
  System.out.print(" i     key    data\n");
  for (i=0;i<arrSize;i++)
  {
    arr[i]=new ITEM(generator.nextInt(1000),i);
    System.out.format("%2d %7d %7d\n",i,arr[i].getValue(),arr[i].getData());
  }
  quicksort(arr,0,arrSize-1);
  System.out.print(" i     key    data\n");
  for (i=0;i<arrSize;i++)
    System.out.format("%2d %7d %7d\n",i,arr[i].getValue(),arr[i].getData());

  System.out.print("Running fast LR pointers quicksort\n");
  generator=new Random(seed);
  System.out.print(" i     key    data\n");
  for (i=0;i<arrSize;i++)
  {
    arr[i]=new ITEM(generator.nextInt(1000),i);
    System.out.format("%2d %7d %7d\n",i,arr[i].getValue(),arr[i].getData());
  }
  quicksortFast(arr,0,arrSize-1);
  System.out.print(" i     key    data\n");
  for (i=0;i<arrSize;i++)
    System.out.format("%2d %7d %7d\n",i,arr[i].getValue(),arr[i].getData());
  }

}