Modify the partition.java program (Listing 7.2) so that the partitionIt() method always uses the highest-index (right) element as the pivot, rather than an arbitrary number. (This is similar to what happens in the quickSort1.java program in Listing 7.3.) Make sure your routine will work for arrays of three or fewer elements. To do so, you may need a few extra statements.

// 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 //-------------------------------------------------------------- Partitioning 327 public ArrayPar(int max) { theArray = new long[max]; nElems = 0; } // constructor // create the array // 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 left && // find smaller item theArray[--rightPtr] > pivot) ; // (nop) if(leftPtr >= rightPtr) break; else swap(leftPtr, rightPtr); } // end while(true) return leftPtr; // if pointers cross, // partition done // not crossed, so // swap elements // return partition } // end partitionIt() //-------------------------------------------------------------- public void swap(int dex1, int dex2) // swap two elements { long temp; temp = theArray[dex1]; theArray[dex1] = theArray[dex2]; theArray[dex2] = temp; // A into temp // B into A // temp into B } // end swap() //-------------------------------------------------------------- } // end class ArrayPar //////////////////////////////////////////////////////////////// class PartitionApp { public static void main(String[] { int maxSize = 16; ArrayPar arr; arr = new ArrayPar(maxSize); for(int j=0; j