In C++ 1. Heapsort Write a function that implements heapsort algorithm: 1. The d
ID: 3706153 • Letter: I
Question
In C++
1. Heapsort Write a function that implements heapsort algorithm: 1. The data file contains no more than 50 integers, each taking one line File name: a5.txt At "build a heap", the program prints out on screen the first 10 integers sequentially (indices 0 to 9) for each round of iteration where the heap is built All 10 integers should be on a single line At ..adjust the heap" the program prints out on screen the last 10 integers for each round of iteration where the heap is built, from indices N-10 to N-1. All 10 integers should be on a single line, with one space in between. 2. 3. 4. After sorting, the program prints out all integers in the sorted ordeir 5. For this assignment, the sorted numbers are in ascending order 2. Quicksort Write a function that implements quicksort algorithm 6. The data file contains no more than 50 integers, each taking one line File name: a5.txt (don't forget closing this file after part 1) At each pivot value assignment and partition, the program prints out on screen the pivot value and all integers in the array from index 0 to index N-1, where N is the number of integers in a5.txt. Each line displays 10 integers sequentially 7. 8. After sorting, the program prints out all integers in the sorted ordei 9. For this assignment, the sorted numbers are in ascending order. Your program should print out the outputs related to part 1 (heapsort) first, and continue with part 2 (quicksort) at a keyboard input. This is a single program; don't submit two separate programsExplanation / Answer
Note: The Heap is built here as Max-Heap and you are expecting it to be Min-Heap
CODE:
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
//Java program for implementation of Heap Sort and Quick
Sort
public class Heapest
{
public void heapSort(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
System.out.println("Printing 10 integers for every iteration
while building HEAP");
for (int i = n / 2 - 1; i >= 0; i--)
buildHeap(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max buildHeap on the reduced heap
buildHeap(arr, i, 0);
}
}
// To buildHeap a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void buildHeap(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int r = 2*i + 2; // right = 2*i + 2
int l = 2*i + 1; // left = 2*i + 1
// 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;
for(int k=0; k<10; k++)
System.out.print(arr[k] + " ");
System.out.println();
// Recursively buildHeap the affected sub-tree
buildHeap(arr, n, largest);
}
}
/ A utility function to print array of size n/
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
public int[] readFromFile(){
int[] maxFromFile = new int[50];
int[] arr;
int count = 0;
// please provide the path exactly as below
File file = new
File("H:\eclipse_workspace\algos\FullProblems\a.txt");
try {
Scanner input = new Scanner(file);
while (input.hasNextLine()) {
String line = input.nextLine();
maxFromFile[count] = Integer.parseInt(line);
count++;
}
input.close();
}
catch (FileNotFoundException e) {
e.printStackTrace();
}
arr = new int[count];
for(int i=0; i<count; i++){
arr[i] = maxFromFile[i];
}
return arr;
}
// QuickSort Partition
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller or equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
// pi is partitioning index, arr[pi] is now at right place
int pi = partition(arr, low, high);
System.out.println("Partition element is " + pi);
printArray(arr);
// Recursively quickSort elements before and after partition
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
public static void main(String args[])
{
Heapest ob = new Heapest();
int arr[] = ob.readFromFile();
System.out.println("HeapSort starts here");
ob.heapSort(arr);
System.out.println("HeapSorted array is");
printArray(arr);
System.out.println("--------------------------------------------
");
System.out.println("QuickSort starts here");
arr = ob.readFromFile();
ob.quickSort(arr, 0, arr.length-1);
System.out.println("QuickSorted Array is ");
printArray(arr);
}
}
OUTPUT:
HeapSort starts here
Printing 10 integers for every iteration while building HEAP
12 32 89 835 35 60 441 3 112 7
12 32 441 835 35 60 89 3 112 7
12 835 441 32 35 60 89 3 112 7
12 835 441 112 35 60 89 3 32 7
835 12 441 112 35 60 89 3 32 7
835 112 441 12 35 60 89 3 32 7
835 112 441 32 35 60 89 3 12 7
441 112 7 32 35 60 89 3 12 835
441 112 89 32 35 60 7 3 12 835
112 12 89 32 35 60 7 3 441 835
112 35 89 32 12 60 7 3 441 835
89 35 3 32 12 60 7 112 441 835
89 35 60 32 12 3 7 112 441 835
60 35 7 32 12 3 89 112 441 835
35 3 7 32 12 60 89 112 441 835
35 32 7 3 12 60 89 112 441 835
32 12 7 3 35 60 89 112 441 835
12 3 7 32 35 60 89 112 441 835
HeapSorted array is
3 7 12 32 35 60 89 112 441 835
--------------------------------------------
QuickSort starts here
Partition element is 4
12 32 7 3 35 60 441 835 112 89
Partition element is 0
3 32 7 12 35 60 441 835 112 89
Partition element is 2
3 7 12 32 35 60 441 835 112 89
Partition element is 6
3 7 12 32 35 60 89 835 112 441
Partition element is 8
3 7 12 32 35 60 89 112 441 835
QuickSorted Array is
3 7 12 32 35 60 89 112 441 835