Transcript Algorithms-Ch8&9

Ch. 8 & 9 – Linear Sorting
and
Order Statistics
What do you trade for speed?
Ch.8 – Linear Sorting
Sorting by Comparisons
Up to this point, all the sorting algorithms we examined
depended on comparing elements of a given set, in
order to sort the set. All the algorithms we came up with,
were either O(n lg n) or Q(n lg n) or O(n2).
One can ask: can we sort a set S, consisting of elements
from a totally ordered universe, in time O(|S|)?
The answer, as we might expect, is “yes, but…”
First of all, the negative result: sorting by comparisons is
(worst case) W(n lg n).
3/26/2016
91.404
2
Ch.8 – Linear Sorting
..
3/26/2016
91.404
3
Ch.8 – Linear Sorting
The main ideas are:
1.Every time you try to determine the relative positions of
two element you must make a comparison (decision).
2.The input (n elements) can come in any order.
3.There are n! ways in which n different elements can be
arranged.
4.A “sort” is equivalent to finding (by a sequence of
comparisons between two elements) the permutation of the
input that leaves the input set ordered.
5.Each such permutation corresponds to a leaf of the
“binary decision tree” generated by the comparisons.
6.The binary decision tree has n! leaves.
3/26/2016
91.404
4
Ch.8 – Linear Sorting
Theorem 8.1: Any comparison sort algorithm requires
W(n lg n) comparisons in the worst case.
Proof: by the previous discussion, the binary decision tree
has at least n! leaves, and height h. Since such a binary
tree cannot have more than 2h leaves, we have n! ≤ 2h.
Taking the logarithm (base 2) of both sides:
h ≥ lg (n!) = W(n lg n),
This means that there is at least ONE path of length h
connecting the root to a leaf.
Corollary 8.2: HEAPSORT and MERGESORT
asymptotically optimal comparison sorts.
3/26/2016
91.404
are
5
Ch.8 – Linear Sorting
Sorting NOT by comparisons
How do we do it?
• We must make some further assumptions.
• For example, we need to assume more than “the set to
be sorted is a set of integers”.
• More specifically, we assume the integers fall in some
range, say [1..k], where k = O(n).
• This is the idea behind Counting Sort. How do we use
it?
3/26/2016
91.404
6
Ch.8 – Linear Sorting
..
3/26/2016
91.404
7
Ch.8 – Linear Sorting
..
3/26/2016
91.404
8
Ch.8 – Linear Sorting
Counting Sort: Time Complexity
How much time?
• The for loop of l. 2-3 takes time Q(k).
• The for loop of l. 4-5 takes time Q(n).
• The for loop of l. 7-8 takes time Q(k).
• The for loop of l. 10-12 takes time Q(n).
• The overall time is Q(k + n).
• The assumption on k gives that the overall time is Q(n).
3/26/2016
91.404
9
Ch.8 – Linear Sorting
Radix Sort – or Hollerith’s Sort
http://www.columbia.edu/acis/history/hollerith.html
What else can we use?
Assume all your integers (we are sorting sets of integers)
have d or fewer digits. Pad the ones with fewer than d
digits with leading 0s, for uniformity.
Assume the digits are on cards with 80 or so vertical
columns, each column with room for 10 (or more) distinct
holes (one for each of 0..9).
Use columns 1..d to store each integer.
Take a deck of such cards (with integers) and sort it.
3/26/2016
91.404
10
Ch.8 – Linear Sorting
Radix Sort
3/26/2016
91.404
11
Ch.8 – Linear Sorting
Radix Sort
Lemma 8.3. Given n d-digit numbers in which each digit
can take up to k possible values, RADIXSORT correctly sorts
these numbers in Q(d(n + k)) time if the stable sort it uses
takes Q(n + k) time.
Proof: the correctness follows by induction on the column
being sorted. Sort the first column (using a stable sort).
Assume the set is sorted on the first i columns (starting
from the back); prove it remains sorted when we use a
stable sort on the i+1st column (see Ex. 8.3-3).
COUNTINGSORT on each digit will give the result (details?).
3/26/2016
91.404
12
Ch.8 – Linear Sorting
Bucket Sort
Assume all the values have equal (independent) probability
of appearing as elements of [0, 1).
• Divide the interval [0, 1) into n equal sized subintervals
(buckets) and distribute the n input numbers into the
buckets.
• Sort the numbers in each bucket (your choice of sort).
• Go through the buckets in order, listing the contents.
3/26/2016
91.404
13
Ch.8 – Linear Sorting
Bucket Sort
3/26/2016
91.404
14
Ch.8 – Linear Sorting
Bucket Sort
We observe that both of the for loops in l. 3-4 and 5-6 take
time O(n) to execute. We need to analyze the cost of the n
calls to INSERTIONSORT on l. 8.
3/26/2016
91.404
15
Ch.8 – Linear Sorting
Bucket Sort
Let ni be the random variable denoting the number of
elements in bucket B[i]. Since INSERTIONSORT runs in
quadratic time, the running time for BUCKETSORT is
n 1
T n  Qn  Oni2 .
The expected time is given by
i0
n 1
n 1
n 1


E T n  E Qn   On i2  Qn    E On i2   Qn   O E n i2  .


i0
i0
i0





We will show that E[ni2] = 2 – 1/n, for i = 0, 1, ..., n - 1.
It should be clear that the expected number of items in
each bucket is the same: by the uniform distribution.
3/26/2016
91.404
16
Ch.8 – Linear Sorting
Bucket Sort
Define the indicator random variables
Xij = I{A[j] nfalls in bucket i}, for i = 0, …, n - 1, j = 1, …, n.
Thus n i   X ij .
j 1
To compute E[ni2], we expand, square and regroup:

 n

2 
 n
 n n




E n i2   E  X ij   E   X ij X ik  E  X ij2    X ij X ik 



j 1 k 1

j 1
1 j n 1k n
i1  



k j


n
    E X
  E X ij2 
j 1
3/26/2016
1 j n 1k n
k j
ij
X ik

91.404
17
Ch.8 – Linear Sorting
Bucket Sort
We now compute the two sums.
The indicator random variable Xij takes the value 1 with
probability 1/n and 0 with probability 1 – 1/n. The same is
true of Xij2:
E[Xij2] = 12*(1/n) + 02*(1 – 1/n) = 1/n.
We observe that, with k ≠ j, Xij and Xik are independent.
This leads to:
E[XijXik] = E[Xij]*E[Xik] = (1/n)*(1/n) = 1/n2.
3/26/2016
91.404
18
Ch.8 – Linear Sorting
Bucket Sort
Substitute in the last equation two slides ago:
n
1
1
1
1
n 1
1
2
E n i       2  n  n n 1 2  1
2
n
n
n
n
j 1 n
1 j n 1k n n
k j
It follows that
E[T(n)] = Q(n) + n*O(2 – 1/n) = Q(n).
Note: the same result holds as long as the distribution
implies that the sum of the bucket sizes is linear in the
total number of elements.
3/26/2016
91.404
19
Ch.9 – Order Statistics
Question: what is the time complexity for the extraction of
the ith element in a totally ordered set of n
elements?Answer: we first have to find an algorithm…
We can find a minimum or a maximum in (deterministic)
time Q(n) - how?
To find the ith element, we can partition the set into two
parts (as in QUICKSORT), if the pivot is the ith element, we
are done; if not, we can decide which side of the pivot will
contain the ith element and partition that subset further.
3/26/2016
91.404
20
Ch.9 – Order Statistics
The algorithm: we use randomization to offset the
probability of receiving the worst possible input sequence.
3/26/2016
91.404
21
Ch.9 – Order Statistics
Note that the recursive call is only on one side of the
partition. That is what will allow us to conclude an
expected time complexity that is linear in n. Obviously,
the worst case is Q(n2).
• Let T(n) be the random variable that denotes the running
time of the algorithm on an input array A[p..r] of n elements.
We obtain an upper bound on E[T(n)].
1.RANDOMIZED-PARTITION is equally likely to return any
element as the pivot.
2.Therefore, for each k  [1, …, n], the subarray A[p..q] has
k elements (all ≤ the pivot) with probability 1/n.
3/26/2016
91.404
22
Ch.9 – Order Statistics
3. For k  [1, …, n], define the indicator random variable
Xk = I{the subarray A[p..q] has exactly k elements}.
4. If the elements of A are distinct, E[Xk] = 1/n.
5. When we call RANDOMIZE-SELECT and choose A[q]
as the pivot element, we do not know a priori, if we will
terminate immediately, recurse on the left subarray A[p,
…, q-1] or recurse on the right subarray A[q+1, …, r].
6. The decision depends on where the ith smallest element
falls w.r.t. A[q]. Since we are looking for an upper
bound, we will assume the desired element is always in
the larger of the two partition subarrays – and we’ll
assume T(n) to be monotone increasing.
3/26/2016
91.404
23
Ch.9 – Order Statistics
7. For a given call of Randomized-Select, the indicator
random variable Xk has the value 1 for exactly one value
of k, and has the value 0 for all oher values of k.
8. When Xk = 1, the two subarrays available for the
recursion have sizes k - 1 and n - k.
9. Then recurrence is
n
T n   X k  T max k 1,n  k  On  X k  T max k 1,n  k On.
k 1
k 1
7. Taking Expected values (Xk & T(max(k-1, n-k)) indep.):
 n
 n
E T n   E  X k  T max k 1,n  k  On    E X k  T max k 1,n  k   On 
k 1
 k 1

n




n



1
  E X k  E T max k 1,n  k   On     E T max k 1,n  k   On 
k 1
k 1 n
3/26/2016
91.404
24
Ch.9 – Order Statistics
11. We now need to simplify the last expression: observe that
k 1 if k  n 

2
max k 1,n  k   
n

n  k if k   2
12. If n is even, each term from T(ceil(n/2)) up to T(n-1) appears
exactly twice in the summation;
13. If 
n is odd, each term from T(ceil(n/2)) up to T(n-1) appears
exactly twice in the summation along with one appearance
of T(floor(n/2)). This leads to the estimate:
n 1
2
E T n  
E T k  On .

n k n 2
The rest of the proof uses this estimate and induction on the
substitution E[T(n)] ≤ c n, for some c > 0 and large enough
3/26/2016
91.404
n.
25
Ch.9 – Order Statistics
Note: with a more complex algorithm, one can compute order
statistics in deterministic time Q(n). See the text.
3/26/2016
91.404
26