JAVAA- Trace the recursive quick sort and partition methods in Lab6.java for this list of numbers:

47 71 15 35 66 61 44 26 68 56 18 19 36 84 69 55

1. Consider the quick sort routine:

public void recQuickSort(int left, int right) {

if (right - left <= 0) // if size <= 1,

return; // already sorted

else { // size is 2 or larger

long pivot = theArray[right]; // rightmost item

// partition, and then call recursive quick sort

int partition = partitionIt(left, right, pivot);

recQuickSort(left, partition - 1); // sort left side

recQuickSort(partition + 1, right); // sort right side

}

}

public int partitionIt(int left, int right, long pivot) {

int leftPtr = left - 1; // left (after ++)

int rightPtr = right; // right-1 (after --)

while (true) { // find bigger item

while (theArray[++leftPtr] < pivot) ;

while (rightPtr > 0 && theArray[--rightPtr] > pivot) ;

if (leftPtr >= rightPtr) break; // if pointers cross,

else // not crossed

swap(leftPtr, rightPtr); // swap elements

}

swap(leftPtr, right); // restore pivot

return leftPtr; // return pivot location

}

1. Find the value of pivot

2. Show the result after partitionIt() is called first time

3. Show the value of partition

4. Show the content of the array

/////////////////////////////

Lab6.java

class ArrayIns {

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

public ArrayIns(int max) { theArray = new long[max]; // create the array nElems = 0; // no items yet }

// put element into array public void insert(long value) { theArray[nElems] = value; // insert it nElems++; // increment size }

public void display() { for (int j = 0; j < nElems; j++) { System.out.print(theArray[j] + " "); // display it } System.out.println(""); }

public void quickSort() { recQuickSort(0, nElems - 1); }

public void recQuickSort(int left, int right) { if (right - left <= 0) // if size <= 1, { return; // already sorted } else // size is 2 or larger { long pivot = theArray[right]; // rightmost item // partition range int partition = partitionIt(left, right, pivot);

recQuickSort(left, partition - 1); // sort left side recQuickSort(partition + 1, right); // sort right side } }

public int partitionIt(int left, int right, long pivot) { int leftPtr = left - 1; // left (after ++) int rightPtr = right; // right-1 (after --) while (true) { // find bigger item while (theArray[++leftPtr] < pivot) ; // (nop) // find smaller item while (rightPtr > 0 && 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) swap(leftPtr, right); // restore pivot return leftPtr; // return pivot location }

public void swap(int dex1, int dex2) // swap two elements { long temp = theArray[dex1]; // A into temp theArray[dex1] = theArray[dex2]; // B into A theArray[dex2] = temp; // temp into B } }

public class Lab6 {

public static void main(String[] args) { int maxSize = 16; // array size ArrayIns arr; arr = new ArrayIns(maxSize); // create array

for (int j = 0; j < maxSize; j++) // fill array with { // random numbers long n = (int) (java.lang.Math.random() * 99); arr.insert(n); } System.out.print("Oritinal Array ="); arr.display(); // display items arr.quickSort(); // quicksort them System.out.print("Sorted Array ="); arr.display(); // display them again } }