Modify thisJAVA code to output the answers to these 4 questions: 1. Find the val

Question

Modify thisJAVA code to output the answers to these 4 questions:

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

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

import java.util.*;

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

Explanation / Answer

Modified Source File:-
------------------------------------package com.samples;
import java.util.*;
class ArrayIns
{
private long[] theArray; // ref to array theArray
private int nElems; // number of data items
static boolean first_Partition=true;
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)
{
long pivot_Element=0;
if (right - left <= 0) // if size <= 1,
{
return; // already sorted
}
else // size is 2 or larger
{
long pivot = theArray[right]; // rightmost item
pivot_Element= theArray[left + (right - left) / 2];
System.out.println("1.Pivot Element is:"+pivot_Element);
// partition range
int partition = partitionIt(left, right, pivot);
if(first_Partition)
{
System.out.println("-----------------------------------");
System.out.println("2.The result array Elemenst after partitionIt() is called first time");
display();
System.out.println("-----------------------------------");
System.out.println("3.The value of Partition is:"+partition);
first_Partition=false;
}
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
System.out.println("Please Enter 16 integer Elements");
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
}
}

sample output:-
--------------------
Please Enter 16 integer Elements
2
31
90
4
56
321
900
32
67
895
3221
2
34
30
210
434
Original Array = 2 31 90 4 56 321 900 32 67 895 3221 2 34 30 210 434
1.Pivot Element is:32
-----------------------------------
2.The result array Elemenst after partitionIt() is called first time
2 31 90 4 56 321 210 32 67 30 34 2 434 895 900 3221
-----------------------------------
3.The value of Partition is:12
1.Pivot Element is:321
1.Pivot Element is:210
1.Pivot Element is:210
1.Pivot Element is:30
1.Pivot Element is:67
1.Pivot Element is:34
1.Pivot Element is:90
1.Pivot Element is:67
1.Pivot Element is:900
1.Pivot Element is:895
Sorted Array = 2 2 4 30 31 32 34 56 67 90 210 321 434 895 900 3221

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.