All Questions

Filter by
Sorted by
Tagged with
0
votes
1answer
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 ...
5
votes
1answer
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 ...
3
votes
2answers
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 > ...
0
votes
2answers
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 ...
0
votes
0answers
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)?
4
votes
2answers
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, ...
2
votes
1answer
84 views

Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?

So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring ...
4
votes
2answers
479 views

From Whence the Randomization in Randomized Quicksort

Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph): Using a random number generator to choose the positions is ...