Hi, I need further assistance with this problem. So far I have the actual swaps
ID: 3835967 • Letter: H
Question
Hi, I need further assistance with this problem. So far I have the actual swaps output, but i need the preditced swaps, min sort effort, actual sort effort, and predicted sort effort output & calculated as well. Thank you.
The Code I have so far:
The code I have so far:
package heapsort.template;
import java.util.Random;
import javax.swing.JOptionPane;
public class HeapSortTemplate
{
static int se; //sort effort 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 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;
}
}
Explanation / Answer
Predicted swaps for heap sort :
import java.util.Scanner;
public class HeapSort
{
private static int N;
public static void sort(int arr[])
{
heapify(arr);
for (int i = N; i > 0; i--)
{
swap(arr,0, i);
N = N-1;
maxheap(arr, 0);
}
}
public static void heapify(int arr[])
{
N = arr.length-1;
for (int i = N/2; i >= 0; i--)
maxheap(arr, i);
}
public static void maxheap(int arr[], int i)
{
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i)
{
swap(arr, i, max);
maxheap(arr, max);
}
}
public static void swap(int arr[], int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Heap Sort Test ");
int n, i;
System.out.println("Enter number of integer elements");
n = scan.nextInt();
int arr[] = new int[ n ];
System.out.println(" Enter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
sort(arr);
System.out.println(" Elements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
min sort effort for heap sort:
package sorting;
public class HeapSort {
public static void main(String[] args) {
int[] array = new int[]{4, 10, 3, 5, 1};
new HeapSort().sort(array);
for (int i : array) {
System.out.print(i + " ");
}
}
public void sort(int data[]) {
int size = data.length;
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(i, data, size);
}
for(int i=data.length-1;i>=0;i--){
int temp = data[0];
data[0]=data[i];
data[i]=temp;
size = size-1;
heapify(0, data, size);
}
}
private int leftChild(int i){
return 2 * i + 1;
}
private int rightChild(int i) {
return 2 * i + 2;
}
private void heapify(int i, int[] data, int size) {
int largestElementIndex = i;
int leftChildIndex = leftChild(i);
if (leftChildIndex < size && data[leftChildIndex] > data[largestElementIndex]) {
largestElementIndex = leftChildIndex;
}
int rightChildIndex = rightChild(i);
if (rightChildIndex < size && data[rightChildIndex] > data[largestElementIndex]) {
largestElementIndex = rightChildIndex;
}
if (largestElementIndex != i) {
int swap = data[i];
data[i] = data[largestElementIndex];
data[largestElementIndex] = swap;
heapify(largestElementIndex, data, size);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.