Question: use magic-pivot to obtain a deterministic quick-sort algorithim with the worst-case running time of O(n log n). Problem 1. Suppose we have an array A[1 : n] of n distinct numbers. For any element A[i], we define therank of A[i], denoted by rank(A[i]), as the number of elements in A that are strictly smaller than A[i] plusone; so rank(A[i]) is also the correct position of A[i] in the sorted order of A.Suppose we have an algorithm magic-pivot that given any array B[1 : m] (for any m > 0), returns an indexi such that rank(B[i]) = m/4 and has worst-case runtime of 0(n)'.Example: if B = [1,7, 6, 3, 13, 4, 5, 11], then magic-pivot(B) will return index 4 as rank of B[4] = 3 is 2which is m/4 in this case (rank of B[4] = 3 is 2 since there is only one element smaller than 3 in B).

Answered: use magic-pivot to obtain a…

7th Edition

ISBN:9780133594140

Author:James Kurose, Keith Ross

Publisher:James Kurose, Keith Ross

Chapter1: Computer Networks And The Internet

Section: Chapter Questions

Problem R1RQ: What is the difference between a host and an end system? List several different types of end...

Related questions

Question

Question: use magic-pivot to obtain a deterministic quick-sort algorithim with the worst-case running time of O(n log n).

Expert Solution

Step 1

Quick sort is a divide conquer algorithm. It selects an element as pivot and partition the whole array in right and left.

Explanation:

Include the necessary header file.
Create four functions named as swap, part, sort and print.
The swap functions will swap the elements if it is smaller than the previous element.
Part function will break the array in two parts and will compare the two elements if they are eligible for swap it will call the swap function.
Sort function is itself a recursive function and it will call the sort function itself till the elements are in ascending order.
Print function will only print the sorted array.
From main function print and sort function are called with the arguments as array and it's size.