i. Implement a method to sort a given array using the heap sort algorithm. Use t

Question

i. Implement a method to sort a given array using the heap sort algorithm. Use the algorithm from the textbook (see below). You should finish implementing Build Max Heap and Max Heapify by the end of lab. You can finish implementing the full algorithm for homework. BUILD-MAX-H EAP (A,n) for i In/2 downto 1 MAX-HEAPIFY (A, i, n) HEAPSORT (A, n) BUILD-MAX-HEAPOA, n) for n downto 2 exchange A[1] with Ali MAX-HEAPIFY (A, l, l) MAx-HEAPIFY (A,i, n) LEFT (i) RIGHT (i) if l s n and All] Ali] largest else largest i if r S n and A r]> A[largest] largest r if largest exchange Ali] with Allargest MAX-HEAPIFY(A, largest, in) CS303 Lab Assignment 1 of 2 2. Write a driver program to test the Heapsort algorithm for the amays of varying lengths provided in Canvas. Use the input files provided earlier.

Explanation / Answer

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class HeapSort
{
public void sort(Integer[] arr)
{
int n = arr.length;

// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

for (int i=n-1; i>=0; i--)
{
// exchange current element to root
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

// max heapify to get max heap
heapify(arr, i, 0);
}
}

// heapify subtree rooted at i
void heapify(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 < 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
heapify(arr, n, largest);
}
}

// print array
static void printArray(Integer[] arr)
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}

// Driver program
public static void main(String args[])
{
File file = new File("input_5000.txt");
List<Integer> list = new ArrayList<>();
try {
Scanner sc = new Scanner(file);

while (sc.hasNextInt()) {
int i = sc.nextInt();
list.add(i);
}
sc.close();
}
catch (FileNotFoundException e) {
e.printStackTrace();
return;
}
  
Integer[] arr = list.toArray(new Integer[list.size()]);
int n = arr.length;

HeapSort ob = new HeapSort();
ob.sort(arr);

System.out.println("Sorted array is");
printArray(arr);
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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