Question

What is Randomized Quicksort? Analyse the expected running time of

Randomized Quicksort, with the help of a suitable example.

03 Nov 2017
Answer :
Word Count : 598

In Randomized quick sort a random element is choose as a pivot element.

In very early versions of quicksort, the leftmost element of the partition would often be chosen as the pivot element. Unfortunately, this causes worst-case behavior on already sorted arrays, which is a rather common use-case. The problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot.

Consider a zero-sum game between player A, whose strategies are deterministic algorithms, and player B, who’s strategies are inputs for A’s algorithms. The cost of a strategy profile is the running time of A’s chosen algorithm on B’s chosen input. Therefore, player A tries to minimize the cost, and player B tries to maximize it. In the world of pure strategies, for every algorithm that A chooses, B may choose the most costly input – this is the worst case scenario, and can be found using standard complexity analysis.

But in the real world, inputs are normally not selected by an ‘evil opponent’ – rather, they come from some distribution over inputs. Since this is the case, if we allow the algorithms to also be drawn from some distribution, we may look at the game as one that allows mixed strategies. That is,

_______ _____ ________ ______ _____ ______ _________ ___ ________.
____ ________ ______ _____ __________ ___ ____ ___ __________ _________.
_________ ___ _______ ___ _____ ______ _______ _________ ______ _____ _____ __________.
_______ __________ __________ ______ ________ _____ ____.
__________ _______ ______ ______ _________ ______ __________ _____.
_________ ________ _________ _________ _____ ______ _______ _____ ______ __________.
_______ ______ _______ ______ __________ ____ ____ ____ _____ _______ ____.
_______ ______ _____ ________ ______ _______ _________ _____ ____ _______ __________ ____.
_______ ________ ________ __________ ___ _______ _____ __________ _______ ____ _________ ____.
______ ________ _______ ____ ____ ___.
_________ _________ ______ _________ ______ _______ _______ ______ _________ ____ ____ _____.
_________ ______ _____ _______ ________ __________ ______ ____ _______ __________ ___.
__________ _________ ___ ___ ___ _________ ________ _________ ___ _________ __________.
____ _____ ______ __________ ____ ________ __________.
_________ _________ ____ __________ ________ _____ __________ ______ __________ ___.
___ ________ ___ ______ ____ ____ _____ _____.
___ _________ ____ ___ ______ ____ _____ _____ ________ _________ ____ ___.
____ ____ _______ _________ _____ _____ ____ __________.
___ ______ ______ ___ _________ ________ ________ _____ ________ _______.
________ _________ ____ _________ ____ ________ _______ __________ ____ _____ ___ _________.
__________ _________ ___ ___ _____ ______ ___ ____.
_______ _____ ___ ____ ______.
____ ___ ____ ___ _______ _____ __________ _____.
______ ________ ______ _______ ______.
__________ _____ _____ ________ ____.
__________ ____ _____ _______ _________ __________ _________ __________.
________ ________ __________ _______ _______.
_______ ________ _______ _____ ____.
_____ ________ _____ ___ ____ __________ __________ ____ ___ _______.
_____ _______ ___ _______ _______ _________.
_________ _______ __________ __________ _______ _________.
____ ____ ____ _________ ______ _________ ________ _______ _______ __________ _________.
___ ________ ___ _____ ____ _______.
__________ __________ ____ _____ ________ ______ _______ ______ ______.
______ ____ ____ _____ ___ _________ ________.
______ _____ _____ ________ _____ ______ ________.
____ ______ _______ _____ __________ ____ _____ __________ __________ ________.
______ ________ ________ _________ ____ ____ _________ ______ __________ ___ ________.
_____ __________ _______ _________ _____ _________ ____ ____.
_____ ______ _________ _____ ________ ____ ______ ________.
_____ _____ _____ _________ ______ ___ _______ _________ ______ _______.
__________ ________ ____ __________ ______ ________ ____ ____ ____.
IGNOU ACADEMY
Your IGNOU journey, made easier.
  • Solved Assignments
  • Study Notes
  • Guess Papers
  • Question Papers
Skip in 10
Top
📞
Call Support Instant phone assistance IGNOU MCS 31 2011 - What is Randomized Quicksort? Analyse the expected running time of | IGNOU Academy
→
🟢
WhatsApp Chat Fast live messaging
→
Email Us Business enquiries & support
→