Question

A is an array with n elements such that each element is at most in k...

A is an array with n elements such that each element is at most in k position away of its ordered position. Give an algorithm that sorts the elements of A on O(n log k).
Example: [2,1,4,3]

Homework Answers

Answer #1

Algorithm to sort the elements of A where each element is at most in k position away of its ordered position.
Sort(A[],n,k)
inputs:A //array
n//legnth of A
k//distance k is less than n
now
heap = create a min heap with first k+1 elements in A//take O(klogk) time
now
index=0
for i=k+1 to n-1 ://runs n-k times
{
   A[index++] = heap.pop();//poping min element from heap and storing in sorted order :O(logk)
   heap.push(A[k+1]);//push new element :O(logk)
}//total complexity : O(nlogk)
//now pop all remaining elements from min heap
while(!heap.empty())//runs k times
{
   A[index++] = heap.pop();
}
//now array is sorted

Total complexity of algorithm : klogk+nlogk+k = O(nlogk)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
Describe an algorithm that selects and sorts k smallest elements from an array A of length...
Describe an algorithm that selects and sorts k smallest elements from an array A of length n of integers. Estimate the running time. The efficiency of your algorithm is important.
In java 1. Write a recursive algorithm to add all the elements of an array of...
In java 1. Write a recursive algorithm to add all the elements of an array of n elements 2. Write a recursive algorithm to get the minimum element of an array of n elements 3. Write a recursive algorithm to add the corresponding elements of two arrays (A and B) of n elements. Store the results in a third array C. 4. Write a recursive algorithm to get the maximum element of a binary tree 5. Write a recursive algorithm...
3. (10 marks) Describe a recursive algorithm for finding the maximum element in a array A...
3. Describe a recursive algorithm for finding the maximum element in a array A of n elements. Analyze its time complexity using a recursion tree.
The following algorithm takes as input an array, and returns the array with all the duplicate...
The following algorithm takes as input an array, and returns the array with all the duplicate elements removed. For example, if the input array is {77, 78, 78, 64, 39, 78, 39}, the algorithm returns {77, 78, 64, 39}. S = new empty set D = new empty dynamic array for every element x in input array if not S.member(x) then S.insert(x) D.append(x) return D What is the big-O complexity of this algorithm, if the set is implemented as a)...
2. Design a deterministic algorithm to solve the following problem. input: An array A[1...n] of n...
2. Design a deterministic algorithm to solve the following problem. input: An array A[1...n] of n integers. output: Two different indices i and j such that A[i] = A[j], if such indices exist. Otherwise, return NONE. Your algorithm must take O(n log(n)) time. You must describe your algorithm in plain English (no pseudocode) and you must explain why the running time of your algorithm is O(n log(n)).
An array is sorted (in ascending order) if each element of the array is less than...
An array is sorted (in ascending order) if each element of the array is less than or equal to the next element. An array of size 0 or 1 is sorted Compare the first two elements of the array; if they are out of order, the array is not sorted; otherwise, check the if the rest of the array is sorted. Write a boolean-valued method named isSorted that accepts an integer array, and the number of elements in the array...
1.A stack implemented with an array has what performance? Select one: a. O(n3) b. O(n log...
1.A stack implemented with an array has what performance? Select one: a. O(n3) b. O(n log n) c. O(n) d. O(n2) 2. A stack uses the first in first out insertion and deletion method. Select one: True False 3. Match the following stack operations with their meaning. object pop(); boolean isEmpty(); push (object); integer size(); object top(); meanings are: - returns the number of elements stored -just removes the last inserted elements - returns the last inserted elements without removing...
1. Define the problem Closest-Pair as follows. • Input: an array A consisting of distinct numbers....
1. Define the problem Closest-Pair as follows. • Input: an array A consisting of distinct numbers. • Output: the numbers x, y in A such that |x − y| is as small as possible. Design an O(n log n) time algorithm for this problem . Define the List-Delete problem as follows. • Input: A linked list L of distinct integers and an element a of L. • Output: L with the element a deleted. Design an O(1)-time algorithm for the...
First, understand the Selection-sort algorithm below: Selection-sort(A: Array [1..n] of numbers) 1       for i=n down to...
First, understand the Selection-sort algorithm below: Selection-sort(A: Array [1..n] of numbers) 1       for i=n down to 2 2                position=i 3                for j=1 to (i–1) 4                          if A[j]>A[position] then position=j 5                if position ≠ i then 6                          temp=A[i] 7                          A[i]=A[position] 8                          A[position]=temp (4 points) If input A=[12,5,11,6,10,7,9,8], what will A be after the 3rd iteration of the outermost for loop of the Selection-sort algorithm completes? A=[__, __, __, __, __, __, __, __] (8 points) Modify the algorithm to solve the...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT