📄 chap08.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 8: QUICKSORT</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap09.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap07.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="0772_133f">CHAPTER 8: QUICKSORT<a name="0772_133f"></h1><P>
<a name="0772_133d"><a name="0772_133e">Quicksort is a sorting algorithm whose worst-case running time is <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) on an input array of <I>n</I> numbers. In spite of this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>), and the constant factors hidden in the <img src="../images/bound.gif">(<I>n</I> lg <I>n</I>) notation are quite small. It also has the advantage of sorting in place (see page 3), and it works well even in virtual memory environments.<P>
Section 8.1 describes the algorithm and an important subroutine used by quicksort for partitioning. Because the behavior of quicksort is complex, we start with an intuitive discussion of its performance in Section 8.2 and postpone its precise analysis to the end of the chapter. Section 8.3 presents two versions of quicksort that use a random-number generator. These "randomized" algorithms have many desirable properties. Their average-case running time is good, and no particular input elicits their worst-case behavior. One of the randomized versions of quicksort is analyzed in Section 8.4, where it is shown to run in <I>O</I>(<I>n</I><SUP>2</SUP>) time in the worst case and in <I>O</I>(<I>n </I>lg <I>n</I>) time on average.<P>
<h1><a name="0774_1342">8.1 Description of quicksort<a name="0774_1342"></h1><P>
<a name="0774_133f"><a name="0774_1340">Quicksort, like merge sort, is based on the divide-and-conquer paradigm introduced in Section 1.3.1. Here is the three-step divide-and-conquer process for sorting a typical subarray <I>A</I>[<I>p . . r</I>].<P>
<B>Divide: </B>The array <I>A</I>[<I>p . . r</I>] is partitioned (rearranged) into two nonempty subarrays <I>A</I>[<I>p . . q</I>] and <I>A</I>[<I>q</I> + 1 . . <I>r</I>] such that each element of <I>A</I>[<I>p . . q</I>] is less than or equal to each element of <I>A</I>[<I>q</I> + 1 . . <I>r</I>]. The index <I>q</I> is computed as part of this partitioning procedure.<P>
<B>Conquer: </B>The two subarrays <I>A</I>[<I>p . . q</I>] and <I>A</I>[<I>q</I> + 1 . . <I>r</I>] are sorted by recursive calls to quicksort.<P>
<B>Combine: </B>Since the subarrays are sorted in place, no work is needed to combine them: the entire array <I>A</I>[<I>p . . r</I>] is now sorted.<P>
The following procedure implements quicksort.<P>
<pre>QUICKSORT(<I>A,p,r</I>)</sub></sup></pre><P>
<pre>1 <B>if</B> <I>p</I> < <I>r</I></sub></sup></pre><P>
<pre>2 <B>then</B> <I>q</I> <img src="../images/arrlt12.gif"> PARTITION(<I>A,p,r</I>)</sub></sup></pre><P>
<pre>3 QUICKSORT(<I>A,p,q</I>)</sub></sup></pre><P>
<pre>4 QUICKSORT(<I>A,q</I> + 1,<I>r</I>)</sub></sup></pre><P>
<a name="0774_1341">To sort an entire array <I>A</I>, the initial call is <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT>(<I>A</I>, 1, <I>length</I>[<I>A</I>]).<P>
<h2>Partitioning the array</h2><P>
<a name="0775_1342"><a name="0775_1343">The key to the algorithm is the <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> procedure, which rearranges the subarray <I>A</I>[<I>p . . r</I>] in place.<P>
<pre>PARTITION(<I>A,p,r</I>)</sub></sup></pre><P>
<pre>1 <I>x</I> <img src="../images/arrlt12.gif"> <I>A</I>[<I>p</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 <I>j</I> <img src="../images/arrlt12.gif"> <I>r </I>+ 1</sub></sup></pre><P>
<pre>4 <B>while</B> TRUE</sub></sup></pre><P>
<pre>5 <B>do repeat</B> <I>j</I> <img src="../images/arrlt12.gif"> <I>j</I> - 1</sub></sup></pre><P>
<pre>6 <B>until</B> <I>A</I>[<I>j</I>] <img src="../images/lteq12.gif"> <I>x</I></sub></sup></pre><P>
<pre><I>7 </I><B>repeat</B> <I>i</I> <img src="../images/arrlt12.gif"> <I>i</I> + 1</sub></sup></pre><P>
<pre>8 <B>until</B> <I>A</I>[<I>i</I>] <img src="../images/gteq.gif"> <I>x</I></sub></sup></pre><P>
<pre>9 <B>if</B> <I>i</I> < <I>j</I></sub></sup></pre><P>
<pre>10 <B>then</B> exchange <I>A</I>[<I>i</I>] <img src="../images/dblarr12.gif"> <I>A</I>[<I>j</I>]</sub></sup></pre><P>
<pre>11 <B>else return</B> <I>j</I></sub></sup></pre><P>
Figure 8.1 shows how <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> works. It first selects an element <I>x</I> = <I>A</I>[<I>p</I>] from <I>A</I>[<I>p . . r</I>] as a "pivot" element around which to partition <I>A</I>[<I>p . . r</I>]. It then grows two regions <I>A</I>[<I>p . . i</I>] and <I>A</I>[<I>j . . r</I>] from the top and bottom of <I>A</I>[<I>p . . r</I>], respectively, such that every element in <I>A</I>[<I>p . . i</I>] is less than or equal to <I>x</I> and every element in <I>A</I>[<I>j . . r</I>] is greater than or equal to <I>x</I>. Initially, <I>i</I> = <I>p</I> - 1 and <I>j</I> = <I>r</I> + 1, so the two regions are empty.<P>
Within the body of the <B>while</B> loop, the index <I>j</I> is decremented and the index <I>i</I> is incremented, in lines 5-8, until <I>A</I>[<I>i</I>] <img src="../images/gteq.gif"> <I>x</I> <img src="../images/gteq.gif"> <I>A</I>[<I>j</I>]. Assuming that these inequalities are strict, <I>A</I>[<I>i</I>] is too large to belong to the bottom region and <I>A</I>[<I>j</I>] is too small to belong to the top region. Thus, by exchanging <I>A</I>[<I>i</I>] and <I>A</I>[<I>j</I>] as is done in line 10, we can extend the two regions. (If the inequalities are not strict, the exchange can be performed anyway.)<P>
The body of the <B>while</B> loop repeats until <I>i</I> <img src="../images/gteq.gif"> <I>j</I>, at which point the entire array <I>A</I>[<I>p . . r</I>] has been partitioned into two subarrays <I>A</I>[<I>p . . q</I>] and <I>A</I>[<I>q</I> + 1 . . <I>r</I>], where <I>p</I> <img src="../images/lteq12.gif"> <I>q</I> < <I>r</I>, such that no element of <I>A</I>[<I>p . . q</I>] is larger than any element of <I>A</I>[<I>q</I> + 1. . <I>r</I>]. The value <I>q</I> = <I>j</I> is returned at the end of the procedure.<P>
Conceptually, the partitioning procedure performs a simple function: it puts elements smaller than <I>x </I>into the bottom region of the array and elements larger than <I>x</I> into the top region. There are technicalities that make the pseudocode of <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> a little tricky, however. For example, the indices <I>i</I> and <I>j</I> never index the subarray <I>A</I>[<I>p . . r</I>] out of bounds, but this isn't entirely apparent from the code. As another example, it is important that <I>A</I>[<I>p</I>] be used as the pivot element <I>x</I>. If <I>A</I>[<I>r</I>] is used instead and it happens that <I>A</I>[<I>r</I>] is also the largest element in the subarray <I>A</I>[<I>p . . r</I>], then <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> returns to <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> the value <I>q</I> = <I>r</I>, and <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> loops forever. Problem 8-1 asks you to prove <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> correct.<P>
<img src="155_a.gif"><P>
<h4><a name="0775_1344">Figure 8.1 The operation of <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> on a sample array. Lightly shaded array elements have been placed into the correct partitions, and heavily shaded elements are not yet in their partitions. (a) The input array, with the initial values of i and j just off the left and right ends of the array. We partition around x = A[p] = 5. (b) The positions of i and j at line 9 of the first iteration of the while loop. (c) The result of exchanging the elements pointed to by i and j in line 10. (d) The positions of i and j at line 9 of the second iteration of the while loop. (e) The positions of i and j at line 9 of the third and last iteration of the while loop. The procedure terminates because i <img src="../images/gteq.gif"> j, and the value q = j is returned. Array elements up to and including A[j] are less than or equal to x = 5, and array elements after A[j] are greater than or equal to x = 5.<a name="0775_1344"></sub></sup></h4><P>
The running time of P<FONT FACE="Courier New" SIZE=2>ARTITION </FONT>on an array <I>A</I>[<I>p . . r</I>] is <img src="../images/bound.gif">(<I>n</I>), where <I>n</I> = <I>r</I> - <I>p</I> + 1 (see Exercise 8.1-3).<P>
<P>
<h2><a name="0776_0001">Exercises<a name="0776_0001"></h2><P>
<a name="0776_0002">8.1-1<a name="0776_0002"><P>
Using Figure 8.1 as a model, illustrate the operation of <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> on the array <I>A</I> = <img src="../images/lftwdchv.gif">13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21<img src="../images/wdrtchv.gif">.<P>
<a name="0776_0003">8.1-2<a name="0776_0003"><P>
What value of <I>q</I> does <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> return when all elements in the array <I>A</I>[<I>p . . r</I>] have the same value?<P>
<a name="0776_0004">8.1-3<a name="0776_0004"><P>
Give a brief argument that the running time of <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> on a subarray of size <I>n</I> is <img src="../images/bound.gif">(<I>n</I>).<P>
<a name="0776_0005">8.1-4<a name="0776_0005"><P>
How would you modify <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> to sort in nonincreasing order?<P>
<P>
<P>
<h1><a name="0777_1345">8.2 Performance of quicksort<a name="0777_1345"></h1><P>
<a name="0777_1344">The running time of quicksort depends on whether the partitioning is balanced or unbalanced, and this in turn depends on which elements are used for partitioning. If the partitioning is balanced, the algorithm runs asymptotically as fast as merge sort. If the partitioning is unbalanced, however, it can run asymptotically as slow as insertion sort. In this section, we shall informally investigate how quicksort performs under the assumptions of balanced versus unbalanced partitioning.<P>
<h2>Worst-case partitioning</h2><P>
The worst-case behavior for quicksort occurs when the partitioning routine produces one region with <I>n</I> - 1 elements and one with only l element. (This claim is proved in Section 8.4.1.) Let us assume that this unbalanced partitioning arises at every step of the algorithm. Since partitioning costs <img src="../images/bound.gif">(<I>n</I>) time and <I>T</I>(1) = <img src="../images/bound.gif">(1), the recurrence for the running time is<P>
<pre><I>T</I>(<I>n</I>) = <I>T</I>(<I>n</I> - 1) + <img src="../images/bound.gif">(<I>n</I>).</sub></sup></pre><P>
To evaluate this recurrence, we observe that <I>T</I>(1) = <img src="../images/bound.gif">(1) and then iterate:<P>
<img src="156_a.gif"><P>
We obtain the last line by observing that <img src="156_b.gif"> is the arithmetic series (3.2). Figure 8.2 shows a recursion tree for this worst-case execution of quicksort. (See Section 4.2 for a discussion of recursion trees.)<P>
Thus, if the partitioning is maximally unbalanced at every recursive step of the algorithm, the running time is <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>). Therefore the worstcase running time of quicksort is no better than that of insertion sort. Moreover, the <img src="../images/bound.gif">(<I>n</I><SUP>2</SUP>) running time occurs when the input array is already completely sorted--a common situation in which insertion sort runs in <I>O</I>(<I>n</I>) time.<P>
<img src="157_a.gif"><P>
<h4><a name="0778_0001">Figure 8.2 A recursion tree for <FONT FACE="Courier New" SIZE=2>QUICKSORT</FONT> in which the <FONT FACE="Courier New" SIZE=2>PARTITION</FONT> procedure always puts only a single element on one side of the partition (the worst case). The resulting running time is <img src="../images/bound.gif">(n<SUP>2</SUP><FONT FACE="Times New Roman" SIZE=2>).<a name="0778_0001"></FONT></sub></sup></h4><P>
<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -