Transcript quicksort

Xi = indicator random variable of the event that i-th person
gets his hat back.
X=X1+…+X20
E[Xi]=1/20
E[X] = E[X1] +…+ E[X20] = 1
derangement = permutation with no fixed points
number =  n! / e 
permutations with 1 fixed point
derangement = permutation with no fixed points
number =  n! / e 
permutations with 1 fixed point
n  (n-1)! / e 
n  (n-1)! / e 
n!
 0.3678  0.368
Claim: Alice wins only on HHH game.
1/8
7/8
- Alice wins, gets $6
- Alice loses, pays $1= gets -$1
Alice’s expected payoff:
(1/8)* 6 + (7/8) * (-1) = - 1/8
Bob has the advantage.
Heap
MIN-HEAP-INSERT
HEAP-EXTRACT-MIN
O(log k)
O(log k)
P1
…
Pk
We will find the array Ai whose first element e is the smallest,
output e to B, remove e from Ai, and repeat. We will use a
heap H as follows: we find e using Heap-Extract-Min
procedure and then add the next element from Ai to H
using Min-Heap-Insert procedure. We make n calls to
Min-Heap-Insert and n calls to Heap-Extract-Min. Hence
the running time is O(n.log k). To simplify the exposition
we add  at the end
of each array.
for i from 1 to k do
Pi  1;
Max-Heap-Insert( H,[Ai[1],i] );
for j from 1 to n do
[e,i]  Heap-Extract-Max (H);
Pi  Pi + 1;
Max-Heap-Insert( H, [Ai [Pi],i] );
add e to B
<
<
LA1,RAn,LB1,RBn
while LA<RA do
MA  (LA + RA)/2 
MB  (LB + RB)/2 
if A[MA]<B[MB] then
LA MA + 1, RB MB - 1
else
RA MA, LB MB
output smaller of A[LA],B[LB]
Randomized algorithm for “median”
SELECT k-th element
for random x
1)
<x
L
=x
>x
R
2) recurse on the appropriate part
Quick-sort
PARTITION
for random x
1)
<x
=x
L
2) recurse on both parts
>x
R
Quick-sort
R-QUICK-SORT (A, l, r)
x  random element of A[l,r];
q  PARTITION(A,x,l,r);
R-QUICK-SORT(A,l,q-1);
R-QUICK-SORT(A,q+1,r);
Quick-sort
R-QUICK-SORT (A, l, r)
x  random element of A[l,r];
q  PARTITION(A,x,l,r);
R-QUICK-SORT(A,l,q-1);
R-QUICK-SORT(A,q+1,r);
How many times is R-QUICK-SORT called?
Quick-sort
R-QUICK-SORT (A, l, r)
x  random element of A[l,r];
q  PARTITION(A,x,l,r);
R-QUICK-SORT(A,l,q-1);
R-QUICK-SORT(A,q+1,r);
Time spent in PARTITION?
Quick-sort
R-QUICK-SORT (A, l, r)
x  random element of A[l,r];
q  PARTITION(A,x,l,r);
R-QUICK-SORT(A,l,q-1);
R-QUICK-SORT(A,q+1,r);
Time spent in PARTITION?
compare x with all elements in A[l,r]
we will count the number of comparisons
Quick-sort
R-QUICK-SORT (A, l, r)
x  random element of A[l,r];
q  PARTITION(A,x,l,r);
R-QUICK-SORT(A,l,q-1);
R-QUICK-SORT(A,q+1,r);
Time spent in PARTITION?
Let the elements of A after sorting be
b1 < b2 < … < bn
Let Xi,j be the indicator random variable
for the event bi is compared to bj.
Quick-sort
Time spent in PARTITION?
Let the elements of A after sorting be
b1 < b2 < … < bn
Let Xi,j be the indicator random variable
for the event bi is compared to bj.
What is the probability that bi and bj are
compared in the first round ?
Quick-sort
Time spent in PARTITION?
Let the elements of A after sorting be
b1 < b2 < … < bn
Let Xi,j be the indicator random variable
for the event bi is compared to bj.
What is the probability that bi and bj are
compared in the first round ?
2/n
(the pivot has to be bi or bj)
Quick-sort
Time spent in PARTITION?
What is the probability that bi and bj are
compared ?
2/(j-i+1)
Let bk be the first pivot such that ik j.
bi, bj get compared  k=i or k=j
k is uniformly random in {i,…,j}
Quick-sort
Time spent in PARTITION?
What is the probability that bi and bj are
compared ?
X=  Xi,j
2/(j-i+1)
1i<j n
E[Xi,j] = 2/(j-i+1)
E[X]=
n
2

j-i+1
1i<j n
k=2
2
k
n = O(n ln n)