content: // partition.java
  // demonstrates partitioning an array
  // to run this program: C>java PartitionApp
  ////////////////////////////////////////////////////////////////
  class ArrayPar
     {
     private long[] theArray;          // ref to array theArray
     private int nElems;               // number of data items
  //--------------------------------------------------------------
     public ArrayPar(int max)          // constructor
        {
        theArray = new long[max];      // create the array
        nElems = 0;                    // no items yet
        }
  //--------------------------------------------------------------
     public void insert(long value)    // put element into array
        {
        theArray[nElems] = value;      // insert it
        nElems++;                      // increment size
        }
  //--------------------------------------------------------------
     public int size()                 // return number of items
        { return nElems; }
  //--------------------------------------------------------------
     public void display()             // displays array contents
        {
        System.out.print("A=");
        for(int j=0; j<nElems; j++)    // for each element,
           System.out.print(theArray[j] + " ");  // display it
        System.out.println("");
        }
  //--------------------------------------------------------------
      public int partitionIt(int left, int right, long pivot)
         {
         int leftPtr = left - 1;           // right of first elem
         int rightPtr = right + 1;         // left of pivot
         while(true)
            {
            while(leftPtr < right &&       // find bigger item
                  theArray[++leftPtr] < pivot)
               ;  // (nop)
  
            while(rightPtr > left &&       // find smaller item
                  theArray[--rightPtr] > pivot)
               ;  // (nop)
            if(leftPtr >= rightPtr)        // if pointers cross,
               break;                      //    partition done
            else                           // not crossed, so
               swap(leftPtr, rightPtr);    //    swap elements
            }  // end while(true)
         return leftPtr;                   // return partition
         }  // end partitionIt()
  //--------------------------------------------------------------
     public void swap(int dex1, int dex2)  // swap two elements
        {
        long temp;
        temp = theArray[dex1];             // A into temp
        theArray[dex1] = theArray[dex2];   // B into A
        theArray[dex2] = temp;             // temp into B
        }  // end swap()
  //--------------------------------------------------------------
     }  // end class ArrayPar
  ////////////////////////////////////////////////////////////////
  class PartitionApp
     {
     public static void main(String[] args)
        {
        int maxSize = 16;             // array size
        ArrayPar arr;                 // reference to array
        arr = new ArrayPar(maxSize);  // create the array
  
        for(int j=0; j<maxSize; j++)  // fill array with
           {                          // random numbers
           long n = (int)(java.lang.Math.random()*199);
           arr.insert(n);
           }
        arr.display();                // display unsorted array
  
        long pivot = 99;              // pivot value
        System.out.print("Pivot is " + pivot);
        int size = arr.size();
                                      // partition array
        int partDex = arr.partitionIt(0, size-1, pivot);
  
        System.out.println(", Partition is at index " + partDex);
        arr.display();                // display partitioned array
        }  // end main()
     }  // end class PartitionApp
  ////////////////////////////////////////////////////////////////
  