Consider a special case of the sorting problem where each element in an array A[1..n] of...

 

Transcribed Image Text:

Consider a special case of the sorting problem where each element in an array A[1..n] of elements is within k of its position in the sorted array (there was a question in class on Oct 10 asking about exactly this issue). 1. (2 points) Describe briefly how insertion sort can do this quickly and state and justify informally the resultant running time. 2. (8 points) A better solution is to use heaps. This solution is given on many web sites, but try to not look at those solutions. You can put the first (k+1) items in a min-heap, and then keep extracting the minimum and adding to the heap the next element in the array, until there are no more elements left in A. After this simply go on extracting the minimum until the heap is empty. Write the above algorithm in pseudocode and prove its correctness. You can assume that Heap methods discussed in class (Build-Heap, Heapify, Extract-min) are correct. Also state and justify informally the running time of this algorithm. Consider a special case of the sorting problem where each element in an array A[1..n] of elements is within k of its position in the sorted array (there was a question in class on Oct 10 asking about exactly this issue). 1. (2 points) Describe briefly how insertion sort can do this quickly and state and justify informally the resultant running time. 2. (8 points) A better solution is to use heaps. This solution is given on many web sites, but try to not look at those solutions. You can put the first (k+1) items in a min-heap, and then keep extracting the minimum and adding to the heap the next element in the array, until there are no more elements left in A. After this simply go on extracting the minimum until the heap is empty. Write the above algorithm in pseudocode and prove its correctness. You can assume that Heap methods discussed in class (Build-Heap, Heapify, Extract-min) are correct. Also state and justify informally the running time of this algorithm.

Answer rating: 100% (QA)

1 Insertion Sort Insertion sort can handle this special case efficiently because it works by iterati... View the full answer