Update thejavafile names to include your initials at the end, send .java file only.1. Completein-place heapSort, which takes an
array of data, convert it to maxheapusing bottom-up algorithm. The expected run time should be O(n), where n is the total number of data. BubbleDown method isNOTprovided, we went over a similar one in class and it’s on class website.swap method is provided and you have to write your own BubbleDown method.2. Complete the efficient quickSort. Choose the medianof three values as the pivot. Switch to insertSort if sub-problem is small. Check with sizes 3, 8, 20, choosesone that gives the best runtimeplease use code below:public class A4Sort{ public static void quickSort(int[] a, int l, int h){ if (l >= h) return; if (/*fill in */) { /*fill in */ } int pivot = partition(a, l, h); quickSort(a, l, pivot - 1); quickSort(a, pivot + 1, h); } public static int partition(int[] a, int l, int h){ int pivot = a[h]; //use last entry int last = h; h--; while (l < h){ while(a[l] < pivot) { l++; } while(a[h] > pivot){ h--; } if (l < h) swap(/*fill in */); else swap(/*fill in */); } return l; } public static void insertionSort(int[] a, int l, int h){ for (int i = /*fill in */; i++){ int j = i; int v = a[i]; while (j > 0 && v < a[j - 1]){ a[j] = a[j - 1]; j--; } a[j] = v; } } public static void swap(int[] a, int i, int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void heapSort(int[] a, int l, int h){ heapify(a); //maxheap } public static void heapify(int[] a){ /*fill in */ } public static void bubbleDown(int[] a, int i, int size){ /*fill in */ } public static void main(String[] args){ int[] a = new int[]{3,19,12,7,15,1,16,4,18,9,13,2,17,5,10,11,14,6,8,20}; int[] b = new int[]{3,19,12,7,15,1,16,4,18,9,13,2,17,5,10,11,14,6,8,20}; long time, nextTime; System.out.println("quickSort: "); time = System.nanoTime(); quickSort(a, 0, a.length - 1); nextTime = System.nanoTime(); System.out.println("\tTime used: " + (nextTime - time) + " nseconds"); for (int i = 0; i < a.length; i++) System.out.print(a[i] + ","); System.out.println(); System.out.println("heapSort: "); heapSort(b, 0, b.length - 1); for (int i = 0; i < b.length; i++) System.out.print(b[i] + ","); System.out.println(); }}
