Question

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
//--------------------------------------------------------------
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
////////////////////////////////////////////////////////////////

Answer 1

Java Program:

class ArrayPar
{
    private long[] theArray; // ref to array theArray private
     int nElems; // number of data items

    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<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;
        int rightPtr = right;
        if(rightPtr - leftPtr <= 0)
        {
            System.out.println("\nSub-array too small to sort");
            return -1;
        }
         pivot = theArray[right];
        System.out.println("\nPivot = " + pivot);


        while(true)
        {
            while(leftPtr < right && theArray[++leftPtr] < pivot)
                ; //nop
            while(rightPtr > left && theArray[--rightPtr] > pivot)
                ; //nop
            if(leftPtr >= rightPtr) break;
            else swap(leftPtr, rightPtr);
        }
        swap(leftPtr, right); //move pivot to partition
        return leftPtr;
    } // 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[] args) {
        int maxSize = 16;
        ArrayPar arr;
        arr = new ArrayPar(maxSize);
        for (int j = 0; j < maxSize; j++) {

// array size
// reference to array // create the array
// 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("\nPartition is at index " + partDex);
        arr.display(); // display partitioned array

    }
}// end main()

//output