Hi, I need some help with this. Thanks! The Code: package heapsort.template; imp

Question

Hi, I need some help with this. Thanks!

The Code:

package heapsort.template;

import java.util.Random;
import javax.swing.JOptionPane;

public class HeapSortTemplate
{
public static void main(String[] args)
{
int size = Integer.parseInt(JOptionPane.showInputDialog("How Many Items to"
+ " sort," + " n = ?"));
int[] data = new int [size];
  
randomValues(data);
//int[] data = {7,40,36,17,3,25,1,2};
System.out.println("****** Unsorted *******");
for(int index = 0; index < data.length; index++)
{ System.out.println(data[index]);
}

//reheapDownward(8, data, 0);
  
System.out.println("*********************");

   heapSort(data);
System.out.println("****** Sorted ******");
for(int index = 0; index < data.length; index++)
{ System.out.println(data[index]);
}
System.out.println();
}
public static void reheapDownward(int size, int[] data, int root)
{
if(root*2+1 >= size) //base case, root has no children
{
return;
}
if(root*2+1 == size - 1) //one child, a left child
{
if(data[root] > data[root*2+1]) // base case 2, the root is > than it's child
{
return;
}
else // swap it with it's child
{
swap(data, root, root*2+1);
return;
}
}
  
//root has 2 children
if(data[root] > data[root*2+1] && data[root] > data[root*2+2])
{
return; // base case 3, root larger than both of children
}
else // swap root with its largest child
{
if(data[root*2+1] > data[root*2+2])// left child > than right
{
swap(data, root, root*2+1);
reheapDownward(size, data, root*2+1); // build left subtree into a heap
return;
}
else // root is smaller than right child
{
swap(data, root, root*2+2);
reheapDownward(size, data, root*2+2); // build left subtree into a heap
return;
}
}
}
  
public static void heapSort(int[] data)
{ // Step 1: do nothing, all arrays are left balanced binary trees by default
// remember 2p+1, 2p+2
  
// Step 2: // build the initial heap
for(int p = data.length/2-1; p >= 0; p--) //all root node in the tree
{
reheapDownward(data.length, data, p);   
}
// Step 3: repeatedly place root in it's proper index, rebuild the heap ignoring it
for(int i = 1; i < data.length; i++)
{
swap(data, 0, data.length - i);
reheapDownward(data.length - i, data, 0);
}
}  
  
public static void randomValues(int[] data) // random numbers from 0 to 999, no duplicates
{ Random rn = new Random();
int r = -1;
boolean duplicate;
data[0] = rn.nextInt(data.length);
  
for(int index = 1; index < data.length; index++)
{ duplicate = true;
while(duplicate == true) // r is a duplicate value
{ r = rn.nextInt(data.length);
duplicate = false;
for(int j = 0; j < index; j++) // check all the set elements for a duplicate
{ if(data[j] == r) // a duplicate found
{ duplicate = true;
break;
}// end if  
}// end for
if(duplicate == false)
   data[index] = r;
}
}      
}      
public static void swap(int[] data, int i1, int i2)
{
  
int temp = data[i1];
data[i1] = data[i2];
data[i2] = temp;
}
}

Program 7 Heap Sort and Sorting Performance Complete the coding/testing of the heap sort method we began in class. Then modify your program so that it outputs a comparison of the actual number of swaps it performs to the predicted number of swaps, and a comparison of the actual sort effort to the predicted and minimum sort effort. The output should be formatted exactly as shown below. Actual swaps xxxx; Predicted swaps xxxx Actual sort effort xxxx: Predicted sort effort xxxx: Min sort effort xxxx As discussed in class, the minimum sort effort is nlog,n. The predicted sort effort is 3nlog,n, and the predicted number of swaps is two thirds of the predicted sort effort (see pg 457/458) To do this: modify the project class to include two static integer class level variables that will store the actual number of comparisons and actual number of swaps required to perform a sort modify the swap method to count the number of swaps by incrementing one of the class level variables. modify the reheapDownward method to keep track to the sort effort by incrementing one of the class level variables whenever a comparison is made. modify the main method to product the two lines of required output.

Explanation / Answer

package heapsort.template;
import java.util.Random;
import javax.swing.JOptionPane;

public class HeapSortTemplate
{
   static int noc; //no ofcomparison variable
   static int nos;   //no of swap variable
public static void main(String[] args)
{
int size = Integer.parseInt(JOptionPane.showInputDialog("How Many Items to"
+ " sort," + " n = ?"));
int[] data = new int [size];
  
randomValues(data);
//int[] data = {7,40,36,17,3,25,1,2};
System.out.println("****** Unsorted *******");
for(int index = 0; index < data.length; index++)
{ System.out.println(data[index]);
}
//reheapDownward(8, data, 0);
  
System.out.println("*********************");
heapSort(data);
System.out.println("****** Sorted ******");
for(int index = 0; index < data.length; index++)
{ System.out.println(data[index]);
}
System.out.println();
System.out.println("The total number of comparisions:"+noc);
System.out.println("The total number of swaps:"+nos);
}
public static void reheapDownward(int size, int[] data, int root)
{
if(root*2+1 >= size) //base case, root has no children
{
return;
}
if(root*2+1 == size - 1) //one child, a left child
{
if(data[root] > data[root*2+1]) // base case 2, the root is > than it's child
{
    nos=nos+1;
return;
}
else // swap it with it's child
{
swap(data, root, root*2+1);
return;
}
}
  
//root has 2 children
if(data[root] > data[root*2+1] && data[root] > data[root*2+2])
{
   nos=nos+1;
return; // base case 3, root larger than both of children
}
else // swap root with its largest child
{
if(data[root*2+1] > data[root*2+2])// left child > than right
{
swap(data, root, root*2+1);
reheapDownward(size, data, root*2+1); // build left subtree into a heap
return;
}
else // root is smaller than right child
{
swap(data, root, root*2+2);
reheapDownward(size, data, root*2+2); // build left subtree into a heap
return;
}
}
}
  
public static void heapSort(int[] data)
{ // Step 1: do nothing, all arrays are left balanced binary trees by default
// remember 2p+1, 2p+2
  
// Step 2: // build the initial heap
for(int p = data.length/2-1; p >= 0; p--) //all root node in the tree
{
reheapDownward(data.length, data, p);   
}
// Step 3: repeatedly place root in it's proper index, rebuild the heap ignoring it
for(int i = 1; i < data.length; i++)
{
swap(data, 0, data.length - i);
reheapDownward(data.length - i, data, 0);
}
}
  
public static void randomValues(int[] data) // random numbers from 0 to 999, no duplicates
{ Random rn = new Random();
int r = -1;
boolean duplicate;
data[0] = rn.nextInt(data.length);
  
for(int index = 1; index < data.length; index++)
{ duplicate = true;
while(duplicate == true) // r is a duplicate value
{ r = rn.nextInt(data.length);
duplicate = false;
for(int j = 0; j < index; j++) // check all the set elements for a duplicate
{ if(data[j] == r) // a duplicate found
{ duplicate = true;
break;
}// end if
}// end for
if(duplicate == false)
data[index] = r;
}
}
}
public static void swap(int[] data, int i1, int i2)
{
  
int temp = data[i1];
data[i1] = data[i2];
data[i2] = temp;
   nos=nos+1;
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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