Given the array containing the following integers: 3, 26, 67, 35, 9, -6, 43, 82,

Question

Given the array containing the following integers: 3, 26, 67, 35, 9, -6, 43, 82, 10, 54

a) Sort the input using heapsort by first building a heap using the linear-time build_algorithm. Then sort the heap using sort_heap algorithm.

b) How many comparisons in all did it take to finish sorting the input?

Explanation / Answer

class Test{ public static void main(String a[]){ int[] input = {3, 26, 67, 35, 9, -6, 43, 82, 10, 54}; System.out.println("Total comparisions = "+HeapSort.sort(input)); System.out.println("After sort: "); for (int i = 0; i 0; i--) { swap(arr,0, i); N = N-1; maxheap(arr, 0); } return comparisions; } public static void heapify(int arr[]) { N = arr.length-1; for (int i = N/2; i >= 0; i--) maxheap(arr, i); } public static void maxheap(int arr[], int i) { int left = 2*i ; int right = 2*i + 1; int max = i; if (left arr[i]) { comparisions++; max = left; } if (right arr[max]) { comparisions++; max = right; } if (max != i) { swap(arr, i, max); maxheap(arr, max); } } public static void swap(int arr[], int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.