Question

JAVA- 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. 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
}
}

Answer 1

Date 10. 011 Page Ghiren ao lement 1926 84 69 SS 15 (16 -111ろares

Ahoin 19 687 SS

Page ん lement 8 gent of a ude

JAVA CODE :

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
*/

import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.HashMap;

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
Scanner in = new Scanner(System.in);
for (int j = 0; j < maxSize; j++) // fill array with
{
long n = in.nextInt();;
arr.insert(n);
}
System.out.print("Original Array = ");
arr.display(); // display items
arr.quickSort(); // quicksort them
System.out.print("Sorted Array = ");
arr.display(); // display them again
}
}