Java Programming - Algorithms I created code to run heapSort and recorded timet
ID: 3750328 • Letter: J
Question
Java Programming - Algorithms
I created code to run heapSort and recorded timet on 7 different input files. I'm a beginner coder and my program won't even run the files. Please correct my code. For clarity sake, the seven input file , each file contains random numbers. For example, 100_input.txt contains 100 elements, 1000_input.txt contains 1000 elements. I cannot attach the actual input txt files. Please provide properly formatted code. Thanks in advance. Professor wanted me to use this pseudocode to make our code:
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class heapSort
{
public void heapSort(int arr[])
{
int n = arr.length;
BuildMaxHeap(arr, n);
// One by one extract an element from heap
for (int i=n-2; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
MaxHeapify(arr, i, 0);
}
}
void BuildMaxHeap(int arr[], int n){
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
MaxHeapify(arr, n, i);
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void MaxHeapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
MaxHeapify(arr, n, largest);
}
}
public static void main(String args[]) throws FileNotFoundException {
int arr[], temp[];
String Filename[] =
new String[] { "input_100.txt", "input_1000.txt", "input_5000.txt", "input_10000.txt",
"input_50000.txt", "input_100000.txt", "input_500000.txt" };
// Save filenames in a variable
double times[] = new double[Filename.length];
int file1 = 0, file2 = 0, file3 = 0, file4 = 0, file5 = 0, file6 = 0,
file7 = 0;
Scanner number;
for (int n = 0; n < Filename.length; n++) {
int mySum = 0;
number = new Scanner(new File(Filename[n]));
while (number.hasNextInt()) {
int x = number.nextInt();
// save values from file
mySum++;
// increments the value by 1 for each new value
}
// close the scanner
if (n == 0) {
file1 = mySum;
}
else if (n == 1) {
file2 = mySum;
}
else if (n == 2) {
file3 = mySum;
}
else if (n == 3) {
file4 = mySum;
}
else if (n == 4) {
file5 = mySum;
}
else if (n == 5) {
file6 = mySum;
}
else if (n == 6) {
file7 = mySum;
}
number.close();
}
int index[] = { file1, file2, file3, file4, file5, file6, file7 };
for (int n = 0; n < Filename.length; n++) {
arr = new int[index[n]];
temp = new int[index[n]];
long beginTime, finishTime, totalTime;
// declare variables to save time
System.out.println("File");
number = new Scanner(new File(Filename[n]));
if (n == 0) {
for (int i1 = 0; i1 < file1; i1++)
arr[i1] = Integer.parseInt(number.next());
}
else if (n == 1) {
for (int i2 = 0; i2 < file2; i2++)
arr[i2] = Integer.parseInt(number.next());
} else if (n == 2) {
for (int i3= 0; i3 < file3; i3++)
arr[i3] = Integer.parseInt(number.next());
} else if (n == 3) {
for (int i4 = 0; i4 < file4; i4++)
arr[i4] = Integer.parseInt(number.next());
} else if (n == 4) {
for (int i5 = 0; i5 < file5; i5++)
arr[i5] = Integer.parseInt(number.next());
} else if (n == 5) {
for (int i6 = 0; i6 < file6; i6++)
arr[i6] = Integer.parseInt(number.next());
} else if (n == 6) {
for (int i7 = 0; i7 < file7; i7++)
arr[i7] = Integer.parseInt(number.next());
}
beginTime = System.nanoTime();
finishTime = System.nanoTime();
totalTime = finishTime - beginTime;
times[n] = totalTime / 1000000;
System.out.println("Recorded time : " + times[n] +
" milliseconds to sort file " + Filename[n]);
number.close();
}
}
}
Explanation / Answer
import java.io.*; import java.util.ArrayList; import java.util.List; public class HeapSort { public static void heapSort(Integer[] arr) { int n = arr.length-1; buildMaxHeap(arr, n); // One by one extract an element from heap for (int i=n; i>=1; i--) { // Move current root to end int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap maxHeapify(arr, n--, 0); } } private static void buildMaxHeap(Integer arr[], int n){ // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) maxHeapify(arr, n, i); } // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap private static void maxHeapify(Integer[] arr, int n, int i) { int largest = i; // Initialize largest as root int l = 2*i + 1; // left = 2*i + 1 int r = 2*i + 2; // right = 2*i + 2 // If left child is larger than root if (l arr[largest]) largest = l; // If right child is larger than largest so far if (r arr[largest]) largest = r; // If largest is not root if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree maxHeapify(arr, n, largest); } } public static void main(String args[]) throws IOException { long beginTime, finishTime, totalTime; String filePath = "C:\Users\Achuth\Downloads\untitled\src\"; // Save filenames in a variable String filename[] = new String[] { "input_100.txt", "input_1000.txt", "input_5000.txt", "input_10000.txt", "input_50000.txt", "input_100000.txt", "input_500000.txt" }; //creating a buffer reader for reading the files BufferedReader reader; String text; //looping all the files given in fileName for (int n = 0; nRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.