Question

Consider an array of 10 elements sorted in ascending order. Assume that you sort the table in descending order by running a sorting algorithm.

a) Count the exact number of changes made to the array (i.e. the number of operations of assignment T [...]=) if the bubble sort is applied (Assuming two assignments per swap).

b) Count the exact number of changes made to the array (i.e. the number of operations of assignment T [...]=) if heap-sort is applied (Assuming two assignments per swap).

Answer 1

solution:

PROGRAM::

import java.util.*;
public class Main
{
   public static void main(String[] args) {
       int arr[] = new int[]{1,2,3,4,5,6,7,8,9,10};
       int len = arr.length;
       int temp=0;
       int changes=0;
       //apply bubble sort in descending order..
       for(int i=0;i<len-1;i++)
       {
       for(int j=0;j<len-i-1;j++)
       {
       if(arr[j]<arr[j+1])
       {
       temp = arr[j];
       arr[j] = arr[j+1];
       arr[j+1] = temp;
       changes += 2;
       }
       }
       }
       System.out.print("Using bubble sort printing Elements in Descending order: ");
       for(int i=0;i<len;i++)
       System.out.print(arr[i]+" ");
       System.out.println("\nNumber of Changes made to array using Bubble sort: "+changes);
       changes =0;
       Arrays.sort(arr); //sort the array again in ascending order..
       //apply heap sort in descending order..
       changes = heapSort(arr, len, changes);
System.out.print("Using heap sort printing Elements in Descending order: ");
printArray(arr, len);
System.out.print("Number of Changes made to array using Heap sort: "+changes);
   }
   public static int heapify(int arr[], int n, int i, int changes)
{
int smallest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
  
if (l < n && arr[l] < arr[smallest])
smallest = l;
  

if (r < n && arr[r] < arr[smallest])
smallest = r;
  
if (smallest != i) {
int temp = arr[i];
arr[i] = arr[smallest];
arr[smallest] = temp;
changes += 2;

changes = heapify(arr, n, smallest, changes);
}
return changes;
}
public static int heapSort(int arr[], int n, int changes)
{
int c1=0,c2=0;
for (int i = n / 2 - 1; i >= 0; i--)
c1 = heapify(arr, n, i, changes);
changes = c1+changes;
for (int i = n - 1; i >= 0; i--) {
  
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
changes += 2;
c2 = heapify(arr, i, 0, changes);
}
return changes;
}
public static void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
}

SCREENSHOTS:

please give me thumb up