Problem 3. (20p) Sorting-related problenm Consider the following problem. The in
ID: 3727550 • Letter: P
Question
Problem 3. (20p) Sorting-related problenm Consider the following problem. The input is an array A of size n of integers and some k n. The output is the k largest elements of A. For simplification you can assume that it is only required to print output on the screen rather than collecting and returning as an array. The order of the out put is not important. Example: A|2,5,6, 10,1,3]. 3 largest elements: 5,6,10 3.1 (5p) Solution using heaps. Design an algorithm that runs in O(n k log n) time. What is the asymptotic upper bound on k for which your algorithm is still linear in n? 3.2 (5p) Solution using a partition similar to the quickSelect problem. Write the algorithm Show time efficiency of this algorithm. Note. Remember that the algorithm running time depends on the instance. 3.3 (5p) Solution using BSTs. Write the algorithm. Show time efficiency of this algorithm 3.4 (5p) What is the most efficient solution? Think about different instances. Analyze and give examples of best- and worse- cases.Explanation / Answer
Using Heaps:
1) Build a Max Heap tree in O(n)
2) Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)
Time complexity: O(n + klogn)
A C++ implementation:
Using quickSelect:
public static int RandomizedSelect(int[] a, int p, int r, int k)
{
if (p == r)
{
return a[p];
}
int q = RandomizedPartition(a, p, r);
int length = q - p + 1;
if (k == length)
{
return a[q];
}
else if (k < length)
{
return RandomizedSelect(a, p, q - 1, k);
}
else
{
return RandomizedSelect(a, q + 1, r, k - length);
}
}
static int RandomizedPartition(int[] a, int p, int r)
{
int i = new Random(Environment.TickCount).Next(p, r + 1);
Swap(ref a[r], ref a[i]);
return Partition(a, p, r);
}
static int Partition(int[] a, int p, int r)
{
int x = a[r];
int i = p - 1;
for (int j = p; j < r; j++)
{
if (a[j] <= x)
{
i++;
Swap(ref a[i], ref a[j]);
}
}
Swap(ref a[i + 1], ref a[r]);
return i + 1;
}
static void Swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
Time Complexity: O(n logn)
Using BSTs:
For getting k largest element of a binary search tree.
1. Use inorder traversal to get the sorted elements in an array
2. Access the last K elements by starting from the last element.
Time complexity: The code first do the inorder traversal in O(h) time, then traverses k elements in O(k) time. Therefore overall time complexity is O(h + k).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.