A company (like Amazon) uses search in databases extensively and the databases n
ID: 3568714 • Letter: A
Question
A company (like Amazon) uses search in databases extensively and the databases need to be sorted frequently. Their favorite sorting algorithm is heapsort and they want to explore (and hopefully optimize) its performance. Given an array a[0..n-1], the task is to compute an array change[0..n-1] where change[i] is the number of times a[i] is changed when heapsort is performed on a[].
Write a program: worst(int n) that computes the worst permutation of numbers 1,2,..,n such that the total number of changes for it is maximized. Print the worst permutation (it may be not unique! print just one permutation) and the total number of changes in change[] for it
Explanation / Answer
Java Program:
/*
* Java Program to Implement Heap Sort
*/
import java.util.Scanner;
/* Class HeapSort */
public class ga
{
private static int N;
int swapCount[];
/* Sort Function */
public ga(int n)
{
swapCount = new int[n];
for(int i=0;i<n;i++)
swapCount[i]=0;
}
public void sort(int arr[])
{
heapify(arr);
for (int i = N; i > 0; i--)
{
swap(arr,0, i);
swapCount[i]++;
N = N-1;
maxheap(arr, 0);
}
}
/* Function to build a heap */
public void heapify(int arr[])
{
N = arr.length-1;
for (int i = N/2; i >= 0; i--)
maxheap(arr, i);
}
/* Function to swap largest element in heap */
public void maxheap(int arr[], int i)
{
int count = 0;
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)
{
count++;
swap(arr, i, max);
maxheap(arr, max);
}
// swapCount[i] = count;
}
/* Function to swap two numbers in an array */
public void swap(int arr[], int i, int j)
{
swapCount[i]++;
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public void printSwaps(int n)
{
for(int i=0;i<n;i++)
{
System.out.println(" The number of swaps of Arr["+ (i+1)+"] is: "+swapCount[i]);
}
}
/* Main method */
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
int n, i;
/* Accept number of elements */
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/* Make array of n elements */
int arr[] = new int[ n ];
ga ob = new ga(n);
/* Accept elements */
System.out.println(" Enter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/* Call method sort */
ob.sort(arr);
/* Print sorted Array */
System.out.println(" Elements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
ob.printSwaps(n);
}
}
--------------------------------------------------------------------------------------------------------
Enter number of integer elements
5
Enter 5 integer elements
5
4
3
2
1
Elements after sorting
1 2 3 4 5
The number of swaps of Arr[1] is: 7
The number of swaps of Arr[2] is: 2
The number of swaps of Arr[3] is: 1
The number of swaps of Arr[4] is: 1
The number of swaps of Arr[5] is: 1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.