All Questions

8 questions
Filter by
Sorted by
Tagged with
29 views

What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element?

Consider the recursive quick sort with random pivoting i.e. each time a random pivot element is chosen uniformly. When this ...
639 views

Randomized quicksort expected running time analysis

I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis. Setting in CLRS First let $Z = \{z_1, ..., z_n\}$ be the set of elements of ...
506 views

how to bound the probability that quicksort takes greater than n lg n time?

I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed) Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > ...
62 views

Quick sort analysis confusion

Is randomized quick sort runtime is independent of the sequence of input? but depends on the numbers in the input? Let say A1 = [1,2,3,4,5] , A2 = [5,2,3,4,1] A3 = [5,4,3,2,1] , Will the randomized ...
119 views

Finding the expected total number of comparison for a Randomized Quick Sort

Let A = {2, 8, 11, 3, 12, 7, 10, 4, 15} Want to find $E_4$. Little unsure how to do this question. Would this be similar to finding the probability of the number of comparison 2/(j -i +1)?
2k views

Optimal pivot selection for quick-sort

The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots. It is well known that picking a random pivot does not work as good as taking the median of three, ...