📄 chap08.htm
字号:
<P>
<h2><a name="0786_1361">Exercises<a name="0786_1361"></h2><P>
<a name="0786_1362">8.4-1<a name="0786_1362"><P>
Show that quicksort's best-case running time is <img src="../images/omega12.gif">(<I>n</I>1g<I>n</I>).<P>
<a name="0786_1363">8.4-2<a name="0786_1363"><P>
Show that <I>q</I><SUP>2</SUP> + (<I>n </I>- <I>q</I>)<SUP>2</SUP> achieves a maximum over <I>q</I> = 1, 2, . . . , <I>n </I>- 1 when <I>q</I> = 1 or <I>q</I> = <I>n </I>- 1.<P>
<a name="0786_1364">8.4-3<a name="0786_1364"><P>
Show that <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-Q<FONT FACE="Courier New" SIZE=2>UICKSORT'</FONT>s expected running time is <img src="../images/omega12.gif">(<I>n </I>1g <I>n</I>).<P>
<a name="0786_1365">8.4-4<a name="0786_1365"><P>
<a name="0786_135b"><a name="0786_135c">The running time of quicksort can be improved in practice by taking advantage of the fast running time of insertion sort when its input is "nearly" sorted. When quicksort is called on a subarray with fewer than <I>k</I> elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm runs in <I>O</I>(<I>nk + n</I> 1g(<I>n</I>/<I>k</I>)) expected time. How should <I>k</I> be picked, both in theory and in practice?<P>
<a name="0786_1366">8.4-5<a name="0786_1366"><P>
Prove the identity<P>
<img src="167_c.gif"><P>
and then use the integral approximation method to give a tighter upper bound than (8.5) on the summation <img src="167_d.gif">.<P>
<a name="0786_1367">8.4-6<a name="0786_1367"><P>
<a name="0786_135d"><a name="0786_135e"><a name="0786_135f"><a name="0786_1360">Consider modifying the <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> procedure by randomly picking three elements from array <I>A</I> and partitioning about their median. Approximate the probability of getting at worst an <img src="../images/alpha12.gif"><I>-to-(1 - <img src="../images/alpha12.gif"></I>) split, as a function of <img src="../images/alpha12.gif"><I> in the range 0 < <img src="../images/alpha12.gif"></I> < 1.<P>
<P>
<P>
<h1><a name="0787_1377">Problems<a name="0787_1377"></h1><P>
<a name="0787_1378">8-1 Partition correctness<a name="0787_1378"><P>
<a name="0787_1361"><a name="0787_1362"><a name="0787_1363"><a name="0787_1364"><a name="0787_1365"><a name="0787_1366"><a name="0787_1367">Give a careful argument that the procedure <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> in Section 8.1 is correct. Prove the following:<P>
<I><B>a</I>. </B>The indices <I>i</I> and <I>j</I> never reference an element of <I>A</I> outside the interval [<I>p </I>. . <I>r</I>].<P>
<I><B>b</I>.</B> The index <I>j</I> is not equal to <I>r</I> when <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> terminates (so that the split is always nontrivial).<P>
<I><B>c</I>. </B>Every element of <I>A</I>[<I>p </I>. . <I>j</I>] is less than or equal to every element of <I>A</I>[<I>j</I>+ 1 . . <I>r</I>] when <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> terminates.<P>
<a name="0787_1379">8-2 Lomuto's partitioning algorithm<a name="0787_1379"><P>
<a name="0787_1368"><a name="0787_1369">Consider the following variation of <FONT FACE="Courier New" SIZE=2>PARTITION</FONT>, due to N. Lomuto. To partition <I>A</I>[<I>p </I>. . <I>r</I>], this version grows two regions, <I>A</I>[<I>p</I> . . <I>i</I>] and <I>A</I>[<I>i</I> + 1 . . <I>j</I>], such that every element in the first region is less than or equal to <I>x</I> = <I>A</I> [<I>r</I>] and every element in the second region is greater than <I>x</I>.<P>
<pre>LOMUTO-PARTITION(<I>A, p, r</I>)</sub></sup></pre><P>
<pre>1 <I>x</I> <img src="../images/arrlt12.gif"> <I>A</I>[<I>r</I>]</sub></sup></pre><P>
<pre>2 <I>i</I> <img src="../images/arrlt12.gif"> <I>p </I>- 1</sub></sup></pre><P>
<pre>3 <B>for</B> <I>j</I> <img src="../images/arrlt12.gif"> <I>p</I> <B>to</B> <I>r</I></sub></sup></pre><P>
<pre>4 <B>do if</B> <I>A</I>[<I>j</I>] <img src="../images/lteq12.gif"> <I>x</I></sub></sup></pre><P>
<pre>5 <B>then</B> <I>i </I><img src="../images/arrlt12.gif"> <I>i </I>+ 1</sub></sup></pre><P>
<pre>6 exchange <I>A</I>[<I>i</I>] <img src="../images/dblarr12.gif"> <I>A</I>[<I>j</I>]</sub></sup></pre><P>
<pre>7 <B>if</B> <I>i </I>< <I>r</I></sub></sup></pre><P>
<pre>8 <B>then return</B> <I>i</I></sub></sup></pre><P>
<pre>9 <B>else return</B> <I>i </I>- 1</sub></sup></pre><P>
<I><B>a. </I></B>Argue that <FONT FACE="Courier New" SIZE=2>LOMUTO</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT> is correct.<P>
<I><B>b</I>. </B>What are the maximum numbers of times that an element can be moved by <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> and by <FONT FACE="Courier New" SIZE=2>LOMUTO</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT>?<P>
<I><B>c</I>.</B> Argue that <FONT FACE="Courier New" SIZE=2>LOMUTO</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT>, like <FONT FACE="Courier New" SIZE=2>PARTITION</FONT>, runs in <img src="../images/bound.gif">(<I>n</I>) time on an <I>n</I>-element subarray.<P>
<I><B>d</I>.</B> How does replacing <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> by <FONT FACE="Courier New" SIZE=2>LOMUTO</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT> affect the running time of <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> when all input values are equal?<P>
<I><B>e</I>. </B>Define a procedure <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>LOMUTO</FONT>-P<FONT FACE="Courier New" SIZE=2>ARTITION </FONT>that exchanges <I>A</I>[<I>r</I>] with a randomly chosen element in <I>A</I>[<I>p </I>. . <I>r</I>] and then calls <FONT FACE="Courier New" SIZE=2>LOMUTO</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT>. Show that the probability that a given value <I>q</I> is returned by <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>LOMUTO</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT> is equal to the probability that <I>p</I> + <I>r</I> - <I>q</I> is returned by <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-<FONT FACE="Courier New" SIZE=2>PARTITION</FONT>.<P>
<a name="0787_137a">8-3 Stooge sort<a name="0787_137a"><P>
<a name="0787_136a">Professors Howard, Fine, and Howard have proposed the following "elegan" sorting algorithm:<P>
<img src="169_a.gif"><P>
<I><B>a. </I></B>Argue that <FONT FACE="Courier New" SIZE=2>STOOGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT>(<I>A</I>, 1, <I>length</I>[<I>A</I>]) correctly sorts the input array <I>A</I>[1 . . <I>n</I>], where <I>n</I> = <I>length</I>[<I>A</I>].<P>
<I><B>b</I>. </B>Give a recurrence for the worst-case running time of <FONT FACE="Courier New" SIZE=2>STOOGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> and a tight asymptotic (<img src="../images/bound.gif">-notation) bound on the worst-case running time.<P>
<I><B>c</I>.</B> Compare the worst-case running time of <FONT FACE="Courier New" SIZE=2>STOOGE</FONT>-<FONT FACE="Courier New" SIZE=2>SORT</FONT> with that of insertion sort, merge sort, heapsort, and quicksort. Do the professors deserve tenure?<P>
<a name="0787_137b">8-4 Stack depth for quicksort<a name="0787_137b"><P>
<a name="0787_136b"><a name="0787_136c"><a name="0787_136d"><a name="0787_136e"><a name="0787_136f">The <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> algorithm of Section 8.1 contains two recursive calls to itself. After the call to <FONT FACE="Courier New" SIZE=2>PARTITION</FONT>, the left subarray is recursively sorted and then the right subarray is recursively sorted. The second recursive call in <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> is not really necessary; it can be avoided by using an iterative control structure. This technique, called<I> <B>tail recursion</I></B>, is provided automatically by good compilers. Consider the following version of quicksort, which simulates tail recursion.<P>
<pre><a name="0787_1370">QUICKSORT'(<I>A,p,r</I>)</sub></sup></pre><P>
<pre>1 <B>while</B> <I>p</I> < <I>r</I></sub></sup></pre><P>
<pre>2 <B>do</B> <img src="170_a.gif"> Partition and sort left subarray</sub></sup></pre><P>
<pre>3 <I>q</I> <img src="../images/arrlt12.gif"> PARTITION(<I>A,p,r</I>)</sub></sup></pre><P>
<pre>4 QUICKSORT'(<I>A,p,q</I>)</sub></sup></pre><P>
<pre>5 <I>p</I> <img src="../images/arrlt12.gif"> <I>q</I> + 1</sub></sup></pre><P>
<I><B>a</I>. </B>Argue that <FONT FACE="Courier New" SIZE=2>QUICKSORT'</FONT>(<I>A</I>, 1, <I>length</I>[<I>A</I>]) correctly sorts the array <I>A</I>.<P>
Compilers usually execute recursive procedures by using a <I><B>stack</I></B> that contains pertinent information, including the parameter values, for each recursive call. The information for the most recent call is at the top of the stack, and the information for the initial call is at the bottom. When a procedure is invoked, its information is <I><B>pushed</I></B> onto the stack; when it terminates, its information is <I><B>popped</I></B>. Since we assume that array parameters are actually represented by pointers, the information for each procedure call on the stack requires <I>O</I>(1) stack space. The <I><B>stack depth</I></B> is the maximum amount of stack space used at any time during a computation.<P>
<I><B>b.</I></B> Describe a scenario in which the stack depth of <FONT FACE="Courier New" SIZE=2>QUICKSORT'</FONT> is <img src="../images/bound.gif">(<I>n</I>) on an <I>n</I>-element input array.<P>
<I><B>c</I>. </B>Modify the code for <FONT FACE="Courier New" SIZE=2>QUICKSORT'</FONT> so that the worst-case stack depth is <img src="../images/bound.gif">(1g <I>n</I>).<P>
<a name="0787_137c">8-5 Median-of-3 partition<a name="0787_137c"><P>
<a name="0787_1371"><a name="0787_1372"><a name="0787_1373"><a name="0787_1374"><a name="0787_1375"><a name="0787_1376">One way to improve the <FONT FACE="Courier New" SIZE=2>RANDOMIZED</FONT>-Q<FONT FACE="Courier New" SIZE=2>UICKSORT </FONT>procedure is to partition around an element <I>x</I> that is chosen more carefully than by picking a random element from the subarray. One common approach is the <I><B>median-of-3</I></B> method: choose <I>x</I> as the median (middle element) of a set of 3 elements randomly selected from the subarray. For this problem, let us assume that the elements in the input array <I>A</I>[1 . . <I>n</I>] are distinct and that <I>n</I> <img src="../images/gteq.gif"> 3. We denote the sorted output array by <I>A</I>'[1 . . <I>n</I>]. Using the median-of-3 method to choose the pivot element <I>x</I>, define <I>p<SUB>i</I></SUB> = Pr{<I>x</I> = <I>A</I>'[<I>i</I>]}.<P>
<I><B>a</I>. </B>Give an exact formula for <I>p<SUB>i</I></SUB> as a function of <I>n</I> and <I>i</I> for <I>i</I> = 2, 3, . . . , <I>n</I> - 1 . (Note that <I>p</I><SUB>1</SUB> = <I>p<SUB>n</I></SUB> = 0.)<P>
<I><B>b</I>. </B>By what amount have we increased the likelihood of choosing <I>x</I> = A'[<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdl12.gif"></FONT>(<I>n</I> + 1)/2<FONT FACE="Courier New" SIZE=2><img src="../images/hfbrdr12.gif"></FONT>], the median of <I>A</I>[1 . . <I>n</I>], compared to the ordinary implementation? Assume that <I>n</I> <img src="../images/arrow12.gif"> <img src="../images/infin.gif">, and give the limiting ratio of these probabilities.<P>
<I><B>c</I>. </B>If we define a "good" split to mean choosing <I>x = A</I>'[<I>i</I>], where <I>n</I>/3 <img src="../images/lteq12.gif"> <I>i</I> <img src="../images/lteq12.gif"> 2<I>n</I>/3, by what amount have we increased the likelihood of getting a good split compared to the ordinary implementation? (<I>Hint</I>: Approximate the sum by an integral.)<P>
<I><B>d</I>. </B>Argue that the median-of-3 method affects only the constant factor in the <img src="../images/omega12.gif">(<I>n</I> 1g <I>n</I>) running time of quicksort.<P>
<P>
<h1>Chapter notes</h1><P>
The quicksort procedure was invented by Hoare [98]. Sedgewick [174] provides a good reference on the details of implementation and how they matter. The advantages of randomized algorithms were articulated by Rabin [165].<P>
<P>
<P>
<P>
<center>Go to <a href="chap09.htm">Chapter 9</A> Back to <a href="toc.htm">Table of Contents</A>
</P>
</center>
</BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -