chap09.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

<h1><a name="0793_1396">9.4 Bucket sort<a name="0793_1396"></h1><P>
<a name="0793_1390"><a name="0793_1391"><I><B>Bucket sort</I></B> runs in linear time on the average. Like counting sort, bucket sort is fast because it assumes something about the input. Whereas counting sort assumes that the input consists of integers in a small range, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval [0,1). (See Section 6.2 for a definition of uniform distribution.)<P>
<a name="0793_1392">The idea of bucket sort is to divide the interval [0, 1) into<I> n</I> equal-sized subintervals, or <I><B>buckets,</I></B> and then distribute the<I> n</I> input numbers into the buckets. Since the inputs are uniformly distributed over [0, 1), we don't expect many numbers to fall into each bucket. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing the elements in each.<P>
Our code for bucket sort assumes that the input is an <I>n</I>-element array <I>A</I> and that each element <I>A</I>[<I>i</I>] in the array satisfies 0 <img src="../images/lteq12.gif"> <I>A</I>[<I>i</I>] &lt; 1. The code requires an auxiliary array <I>B</I>[0<I>..n</I> - 1] of linked lists (buckets) and assumes that there is a mechanism for maintaining such lists. (Section 11.2 describes how to implement basic operations on linked lists.)<P>
<img src="181_a.gif"><P>
<h4><a name="0793_1397">Figure 9.4 The operation of <FONT FACE="Courier New" SIZE=2>BUCKET<FONT FACE="Times New Roman" SIZE=2>-<FONT FACE="Courier New" SIZE=2>SORT</FONT></FONT></FONT>. (a) The input array A[1 . .10]. (b) The array B[0 . . 9] of sorted lists (buckets) after line 5 of the algorithm. Bucket i holds values in the interval [i/10,(i + 1)/10). The sorted output consists of a concatenation in order of the lists B[0], B[1], . . . , B[9].<a name="0793_1397"></sub></sup></h4><P>
<pre><a name="0793_1393">BUCKET-SORT(<I>A</I>)</sub></sup></pre><P>
<pre>1  <I>n</I> <img src="../images/arrlt12.gif"> <I>length</I> [<I>A</I>]</sub></sup></pre><P>
<pre>2  <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 1 <B>to</B> <I>n</I></sub></sup></pre><P>
<pre>3       <B>do</B> insert <I>A</I>[ <I>i</I>] into list <I>B</I> [<img src="../images/hfbrdl12.gif"><I>nA</I>[<I>i</I>]<img src="../images/hfbrdr12.gif">]</sub></sup></pre><P>
<pre>4  <B>for</B> <I>i</I> <img src="../images/arrlt12.gif"> 0 <B>to</B> <I>n</I> -1</sub></sup></pre><P>
<pre>5       <B>do</B> sort list <I>B</I>[<I>i</I>] with insertion sort</sub></sup></pre><P>
<pre>6  concatenate the lists <I>B</I>[0], <I>B</I>[1], . . . , <I>B</I>[<I>n</I> - 1] together in order</sub></sup></pre><P>
<a name="0793_1394">Figure 9.4 shows the operation of bucket sort on an input array of 10 numbers.<P>
<a name="0793_1395">To see that this algorithm works, consider two elements <I>A</I>[<I>i</I>] and <I>A</I>[<I>j</I>]. If these elements fall in the same bucket, they appear in the proper relative order in the output sequence because their bucket is sorted by insertion sort. Suppose they fall into different buckets, however. Let these buckets be <I>B</I>[<I>i</I>'] and <I>B</I>[<I>j</I><I>'</I>], respectively, and assume without loss of generality that <I>i</I>' &lt; <I>j</I>'. When the lists of <I>B</I> are concatenated in line 6, elements of bucket <I>B</I>[<I>i</I>'] come before elements of <I>B</I>[<I>j</I>'], and thus <I>A</I>[<I>i</I>] precedes <I>A</I>[<I>j</I>] in the output sequence. Hence, we must show that <I>A</I>[<I>i</I>] <img src="../images/lteq12.gif"> <I>A</I>[<I>j</I>]. Assuming the contrary, we have<P>
<pre><I>i</I>'  =  <img src="../images/hfbrdl12.gif"><I>nA</I>[<I>i</I>]<img src="../images/hfbrdr12.gif"></sub></sup></pre><P>
<pre><img src="../images/gteq.gif">  <img src="../images/hfbrdl12.gif"><I>nA</I>[<I>j</I>]<img src="../images/hfbrdr12.gif"></sub></sup></pre><P>
<pre>=  <I>j</I>',</sub></sup></pre><P>
which is a contradiction, since i' &lt; j'. Thus, bucket sort works.<P>
To analyze the running time, observe that all lines except line 5 take <I>O</I>(<I>n</I>) time in the worst case. The total time to examine all buckets in line 5 is <I>O</I>(<I>n</I>), and so the only interesting part of the analysis is the time taken by the insertion sorts in line 5.<P>
To analyze the cost of the insertion sorts, let <I>n<SUB>i</I></SUB> be the random variable denoting the number of elements placed in bucket <I>B</I>[<I>i</I>]. Since insertion sort runs in quadratic time (see Section 1.2), the expected time to sort the elements in bucket <img src="182_a.gif">. The total expected time to sort all the elements in all the buckets is therefore<P>
<img src="182_b.gif"><P>
<h4><a name="0793_1398">(9.1)<a name="0793_1398"></sub></sup></h4><P>
In order to evaluate this summation, we must determine the distribution of each random variable <I>n<SUB>i</I></SUB>. We have <I>n</I> elements and <I>n</I> buckets. The probability that a given element falls into bucket <I>B</I>[<I>i</I>] is 1/<I>n</I>, since each bucket is responsible for 1/<I>n</I> of the interval [0,1). Thus, the situation is analogous to the ball-tossing example of Section 6.6.2: we have <I>n</I> balls (elements) and <I>n</I> bins (buckets), and each ball is thrown independently with probability <I>p</I> = 1 /<I>n</I> of falling into any particular bucket. Thus, the probability that <I>n<SUB>i</I></SUB> = <I>k</I> follows the binomial distribution <I>b</I>(<I>k; n, p</I>), which has mean E[<I>n<SUB>i</I></SUB>]<I> = np</I> = 1 and variance Var[<I>n<SUB>i</I></SUB>]<I> = np</I>(1 - <I>p</I>) = 1- 1/<I>n</I>. For any random variable <I>X</I>, equation (6.30) gives<P>
<img src="182_c.gif"><P>
Using this bound in equation (9.1), we conclude that the expected time for insertion sorting is <I>O</I>(<I>n</I>). Thus, the entire bucket sort algorithm runs in linear expected time.<P>





<h2><a name="0794_1399">Exercises<a name="0794_1399"></h2><P>
<a name="0794_139a">9.4-1<a name="0794_139a"><P>
Using Figure 9.4 as a model, illustrate the operation of <FONT FACE="Courier New" SIZE=2>BUCKET</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> on the array <I>A</I> = <img src="../images/lftwdchv.gif">.79, .13, .16, .64, .39, .20, .89, .53, .71, .42<img src="../images/wdrtchv.gif">.<P>
<a name="0794_139b">9.4-2<a name="0794_139b"><P>
What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time <I>O</I>(<I>n </I>lg <I>n</I>)?<P>
<a name="0794_139c">9.4-3<a name="0794_139c"><P>
<a name="0794_1396"><a name="0794_1397">We are given <I>n</I> points in the unit circle, <I>p<SUB>i</I></SUB> = (<I>x<SUB>i</I></SUB>, <I>y<SUB>i</I></SUB>), such that <img src="183_a.gif">. Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the area of that region. Design a <img src="../images/bound.gif">(<I>n</I>) expected-time algorithm to sort the <I>n</I> points by their distances <img src="183_b.gif"> from the origin. (<I>Hint:</I> Design the bucket sizes in <FONT FACE="Courier New" SIZE=2>BUCKET</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> to reflect the uniform distribution of the points in the unit circle.)<P>
<a name="0794_139d">9.4-4<a name="0794_139d"><P>
<a name="0794_1398">A<I><B> probability distribution function P</I></B>(<I>x</I>) for a random variable <I>X</I> is defined by <I>P</I>(<I>x</I>) = Pr{<I>X</I> <img src="../images/lteq12.gif"> <I>x</I>}. Suppose a list of <I>n</I> numbers has a continuous probability distribution function <I>P</I> that is computable in <I>O</I>(1) time. Show how to sort the numbers in linear expected time.<P>
<P>


<P>







<h1><a name="0795_139c">Problems<a name="0795_139c"></h1><P>
<a name="0795_139d">9-1     Average-case lower bounds on comparison sorting<a name="0795_139d"><P>
<a name="0795_1399"><a name="0795_139a">In this problem, we prove an <img src="../images/omega12.gif"> (<I>n</I> lg <I>n</I>) lower bound on the expected running time of any deterministic or randomized comparison sort on <I>n</I> inputs. We begin by examining a deterministic comparison sort <I>A</I> with decision tree <I>T<SUB>A</I></SUB>. We assume that every permutation of <I>A</I>'s inputs is equally likely.<P>
<I><B>a.     </I></B>Suppose that each leaf of <I>T<SUB>A</I></SUB> is labeled with the probability that it is reached given a random input. Prove that exactly <I>n</I>! leaves are labeled 1/<I>n</I>! and that the rest are labeled 0.<P>
<I><B>b.</I></B>     Let <I>D</I>(<I>T)</I> denote the external path length of a tree <I>T</I>; that is, <I>D(T)</I> is the sum of the depths of all the leaves of <I>T</I>. Let <I>T</I> be a tree with <I>k</I> &gt; 1 leaves, and let <I>RT</I> and <I>LT</I> be the right and left subtr&eacute;es of <I>T</I>. Show that <I>D</I>(<I>T</I>) = <I>D</I>(<I>RT</I>) + <I>D</I>(<I>LT</I>) + <I>k.</I><P>
<I><B>c.     </I></B>Let <I>d</I>(<I>m</I>) be the minimum value of <I>D</I>(<I>T</I>) over all trees <I>T</I> with <I>m</I> leaves. Show that <I>d</I>(<I>k</I>) = min<SUB>1</SUB><img src="../images/lteq12.gif"><I>i</I><SUB><img src="../images/lteq12.gif"><I>k</I> </SUB>{<I>d</I> (<I>i</I>)+<I>d</I>(<I>k </I>- <I>i</I>)+<I>k</I>}. (<I>Hint:</I> Consider a tree <I>T</I> with <I>k</I> leaves that achieves the minimum. Let <I>i</I> be the number of leaves in <I>RT</I> and <I>k</I> - <I>i</I> the number of leaves in <I>LT.</I>)<P>
<I><B>d.</I></B>     Prove that for a given value of <I>k</I>, the function <I>i</I> lg <I>i</I> + (<I>k</I> - <I>i</I>) lg(<I>k</I> - <I>i</I>) is minimized at <I>i</I> = <I>k</I>/2. Conclude that <I>d</I>(<I>k</I>) = <img src="../images/omega12.gif">(<I>k </I>lg <I>k</I>).<P>
<I><B>e.</I></B>     Prove that <I>D</I>(<I>T<SUB>A</I></SUB>) = <img src="../images/omega12.gif">(<I>n</I>! lg(<I>n</I>!)) for <I>T<SUB>A,</I></SUB> and conclude that the expected time to sort <I>n</I> elements is <img src="../images/omega12.gif">(<I>n </I>lg <I>n</I>).<P>
Now, consider a <I>randomized</I> comparison sort <I>B</I>. We can extend the decision-tree model to handle randomization by incorporating two kinds of nodes: ordinary comparison nodes and "randomization" nodes. A randomization node models a random choice of the form <FONT FACE="Courier New" SIZE=2>RANDOM</FONT>( 1, <I>r</I>) made by algorithm <I>B</I>; the node has <I>r</I> children, each of which is equally likely to be chosen during an execution of the algorithm.<P>
<I><B>f.</I></B>     Show that for any randomized comparison sort <I>B</I>, there exists a deterministic comparison sort <I>A</I> that makes no more comparisons on the average than <I>B</I> does.<P>
<a name="0795_139e">9-2     Sorting in place in linear time<a name="0795_139e"><P>
<a name="0795_139b"><I><B>a.     </I></B>Suppose that we have an array of <I>n</I> data records to sort and that the key of each record has the value 0 or 1. Give a simple, linear-time algorithm for sorting the <I>n</I> data records in place. Use no storage of more than constant size in addition to the storage provided by the array.<P>
<I><B>b.</I></B>     Can your sort from part (a) be used to radix sort <I>n</I> records with <I>b</I>-bit keys in <I>O</I>(<I>bn</I>) time? Explain how or why not.<P>
<I><B>c.     </I></B>Suppose that the<I> n</I> records have keys in the range from 1 to <I>k</I>. Show how to modify counting sort so that the records can be sorted in place in <I>O</I>(<I>n</I> + <I>k</I>) time. You may use <I>O</I>(<I>k</I>) storage outside the input array. (<I>Hint:</I> How would you do it for <I>k</I> = 3?)<P>
<P>







<h1>Chapter notes</h1><P>
The decision-tree model for studying comparison sorts was introduced by Ford and Johnson [72]. Knuth's comprehensive treatise on sorting [123] covers many variations on the sorting problem, including the information- theoretic lower bound on the complexity of sorting given here. Lower bounds for sorting using generalizations of the decision-tree model were studied comprehensively by Ben-Or [23].<P>
Knuth credits H. H. Seward with inventing counting sort in 1954, and also with the idea of combining counting sort with radix sort. Radix sorting by the least-significant digit first appears to be a folk algorithm widely used by operators of mechanical card-sorting machines. According to Knuth, the first published reference to the method is a 1929 document by L. J. Comrie describing punched-card equipment. Bucket sorting has been in use since 1956, when the basic idea was proposed by E. J. Isaac and R. C. Singleton.<P>
<P>


<P>
<P>
<center>Go to <a href="chap10.htm">Chapter 10</A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>


</BODY></HTML>