CODE:

import java.util.Arrays;

public class Sorts  {
 
   public static void heapSort(int[] arr) {
       int n = arr.length;
       
       for (int i = n / 2 - 1; i >= 0; i--)
           heapify(arr, n, i);

       
       for (int i = n - 1; i >= 0; i--) {
         
           int temp = arr[0];
           arr[0] = arr[i];
           arr[i] = temp;

           
           heapify(arr, i, 0);
       }
   }

   static void heapify(int[] arr, int n, int i) {
       int largest = i;
       int l = 2 * i + 1;
       int r = 2 * i + 2;

     
       if (l < n && arr[l] > arr[largest])
           largest = l;

   
       if (r < n && arr[r] > arr[largest])
           largest = r;

       if (largest != i) {
           int swap = arr[i];
           arr[i] = arr[largest];
           arr[largest] = swap;

 
           heapify(arr, n, largest);
       }
   }
   
 public static void main(String[] args) {
       
       int[] arr = { 4, 10, 3, 5, 1 };
       System.out.println("Array before sorting: " + Arrays.toString(arr));  
       Sorts.heapSort(arr);
       System.out.println("Array after sorting: "+Arrays.toString(arr));  
   }
}

Transcribed Image Text:

Implement a fast sorting algorithm as described in class. Here is some example code to use as a guideline. You need only implement the sorting algorithm; the main method will be provided for you. You must hand in the Sorts class with the heapSort sorting algorithm implemented. This is the only file you should hand in. The heading of the method is as in the provided file. Do not change it or you will lose credit! Implement a fast sorting algorithm as described in class. Here is some example code to use as a guideline. You need only implement the sorting algorithm; the main method will be provided for you. You must hand in the Sorts class with the heapSort sorting algorithm implemented. This is the only file you should hand in. The heading of the method is as in the provided file. Do not change it or you will lose credit!

Answer rating: 100% (QA)

import javautilArrays public class Sorts public static void heapSortint arr int n arrlength Buil... View the full answer