Question

q: Write a java code to Test the heap sort algorithm

• Test the algorithms on arrays of size:

• .100,000 , 90,000 ,80,000 ,70,000 ,60,000 ,50,000 ,40,000 ,30,000 ,20,000 ,10,000

• Plot the execution time vs array size. without using excel

Answer 1

This is how time took to sort, time may vary based on system/platform and random number nad also below code provided where you can find TODO section for changing the array size and run the program.

100,000 -> 31 milliseconds

90,000 -> 28 milliseconds

80,000-> 26 milliseconds

70,000 -> 25 milliseconds

60,000 -> 24 milliseconds

50,000-> 21 milliseconds

40,000 -> 15 milliseconds

30,000 -> 13 milliseconds

20,000-> 10 milliseconds

10,000 -> 6 milliseconds

Plot generated

HeapSortTest.java

import java.util.Random;


public class HeapSortTest {
   
   /**
    * function to heapify the array
    * @param arr
    * @param i
    * @param sz
    */
   public static void _heapify_data(int arr[], int i, int sz) {
      
      int l = 2 * i + 1;
      int r = 2 * i + 2;
      
      
      int temp, temp_largest;
      
      if (l < sz && arr[l] > arr[i])
         temp_largest = l;
      else
         temp_largest = i;
      
      if (r < sz && arr[r] > arr[temp_largest])
         temp_largest = r;
      
      if (temp_largest != i) {
         temp = arr[temp_largest];
         arr[temp_largest] = arr[i];
         arr[i] = temp;
         
         _heapify_data(arr, temp_largest, sz);
      }
      
      
   }
   
   /**
    * helper function for build heap
    * @param arr
    */
   
   public static void _build_heap(int arr[]) {
      
      for (int i = (arr.length / 2) - 1; i >= 0; i--) {
         
         _heapify_data(arr, i, arr.length);
         
      }
      
   }
   
   /**
    * heap sort to data
    * @param arr
    */
   public static void heapSort(int arr[]) {
      int temp, j, i;
      
      _build_heap(arr);
      
      for (i = (arr.length) - 1; i > 0; ) {
         temp = arr[0];
         arr[0] = arr[i];
         arr[i] = temp;
         _heapify_data(arr, 0, i--);
         
      }
      
   }
   
   public static void main(String[] args) {
      // TODO: change the size of array as you want to test
      int size=10000;
      int arr[] = getArray(size);
      System.out.println("Sorting started .....");
      long starttime = System.currentTimeMillis();
      heapSort(arr);
      long endtime = System.currentTimeMillis();
      System.out.println("Sorting finished .....");
      System.out.printf("Time take taken for sorting "+size+" integers : %d milliseconds",(endtime-starttime));
   }
   
   /**
    * function to generate random array of given size
    * @param size
    * @return
    */
   public static int[] getArray(int size){
      System.out.println("Generating array of size : "+size);
      Random r = new Random();
      int arr[] = new int[size];
      for(int i=0;i<size;i++){
         arr[i] = r.nextInt(1000);
      }
      System.out.println("array generated.....\n");
      return arr;
   }
}

Please do let me know if u have any concern..