Question

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 nlog2n. The predicted sort effort is 3nlog2n, 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.

This is the class, I am using
import java.util.Arrays;
import java.util.Random;
import javax.swing.JOptionPane;

public class HeapSortTemplate
{
public static void main(String[] args)
{
//int[] data = {1, 40, 36, 17, 3, 25, 1, 2, 4};
  
int size = Integer.parseInt(JOptionPane.showInputDialog("How Many Items to"
+ " sort," + " n = ?"));
int[] data = new int[size];
  
randomValues(data);
System.out.println("Unsorted");
System.out.println(Arrays.toString(data));
System.out.println();
  
//reheapDown(data.length, data, 0);
heapSort(data);
  
//reheapDownward(data.length, data, 0);
System.out.println("Sorted");
System.out.println(Arrays.toString(data));
}
  
public static void heapSort(int[] data)
{ // Step 1:
// do nothing, just think 2n+_1, 2n+2 (then every arrray OK)
// Step 2: // use reheap down to do this
for(int ip = data.length/2 - 1; ip >=0; ip--)
{
reheapDown(data.length, data, ip);
}
// Step 3:
for(int i = 1; i <=data.length; i++)
{
// place root in its correct place in the array
swap(data, 0, data.length - i);
reheapDown(data.length - i, data, 0);
}
}  
public static void reheapDown(int size, int[] data, int root)
{
if(size <=1 || (root*2 + 1) >= size)
{
return; // one node or no children
}
if(root*2+1 == size-1) // one child
{
if(data[root] > data[root*2+1] )
{
return;
}
else
{
swap(data, root, root*2+1); //root and left child
return; //root is not a leaf;
}
// root has 2 children
}
// root has 2 children
if(data[root] > data[root*2+1] && data[root] > data[root*2+2])
{
return; // root larger than oth children
}
else
{
if(data[root*2+1] > data[root*2+2]) // left child larger
{
swap(data, root, root*2+1);
reheapDown(size, data, root*2+1); //<*** use size
}
else // right child larger
{
swap(data, root, root*2+2);
reheapDown(size, data, root*2+2); //<** use size
}
}
}
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;
}
}

Answer 1

The changes made in the code are in bold. All the code edited have comments for better understanding. Hope this helps!

Code:

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

public class HeapSortTemplate
{

// two static integer class level variables to
// the actual number of comparisons and actual number of swaps
public static int actual_cmp = 0, actual_swap = 0;
  
public static void main(String[] args)
{
//int[] data = {1, 40, 36, 17, 3, 25, 1, 2, 4};
  
int size = Integer.parseInt(JOptionPane.showInputDialog("How Many Items to"
+ " sort," + " n = ?"));
int[] data = new int[size];
  
randomValues(data);
System.out.println("Unsorted");
System.out.println(Arrays.toString(data));
System.out.println();
  
//reheapDown(data.length, data, 0);
heapSort(data);
  
//reheapDownward(data.length, data, 0);
System.out.println("Sorted");
System.out.println(Arrays.toString(data));
  
// modify the main method to product the two lines of required output
int n = data.length;
// predicted sort effort is 3nlog2n
int predictedSortEffort = 3*n*(int)(Math.log(n)/Math.log(2));
// minimum sort effort is nlog2n
int minSortEffort = n*(int)(Math.log(n)/Math.log(2));
// predicted number of swaps is two thirds of the predicted sort effort
int predictedSwap = (2 * predictedSortEffort) / 3;
  
System.out.println("\nActual swaps = "+actual_swap
+"; Predicted swaps = " + predictedSwap);
System.out.println("Actual sort effort = "+actual_cmp
+"; Predicted sort effort = "+predictedSortEffort
+"; Min sort effort = "+minSortEffort);
}
  
public static void heapSort(int[] data)
{
// Step 1:
// do nothing, just think 2n+_1, 2n+2 (then every arrray OK)
// Step 2: // use reheap down to do this
for(int ip = data.length/2 - 1; ip >=0; ip--)
{
reheapDown(data.length, data, ip);
}
// Step 3:
for(int i = 1; i <=data.length; i++)
{
// place root in its correct place in the array
swap(data, 0, data.length - i);
reheapDown(data.length - i, data, 0);
}
}
  
public static void reheapDown(int size, int[] data, int root)
{
// modify the reheapDownward method to keep track to the sort effort
// by incrementing one of the class level variables whenever a comparison is made.
  
if(size <=1 || (root*2 + 1) >= size)
{
return; // one node or no children
}
if(root*2+1 == size-1) // one child
{
actual_cmp++; // comparison
if(data[root] > data[root*2+1] )
{
return;
}
else
{
swap(data, root, root*2+1); //root and left child
return; //root is not a leaf;
}
// root has 2 children
}
// root has 2 children
actual_cmp+= 2; // increase by 2 for 2 comparisons
if(data[root] > data[root*2+1] && data[root] > data[root*2+2])
{
return; // root larger than oth children
}
else
{
actual_cmp++; // comparison
if(data[root*2+1] > data[root*2+2]) // left child larger
{
swap(data, root, root*2+1);
reheapDown(size, data, root*2+1); //<*** use size
}
else // right child larger
{
swap(data, root, root*2+2);
reheapDown(size, data, root*2+2); //<** use size
}
}
}
  
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)
{
// modify the swap method to count the number of swaps
// by incrementing one of the class level variables.
actual_swap++;
  
int temp = data[i1];
data[i1] = data[i2];
data[i2] = temp;
}
}

Sample run:

Code screenshots: