📄 page490.html
字号:
<HTML><HEAD><TITLE>Quicksort</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html6811" HREF="page491.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6809" HREF="page488.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6803" HREF="page489.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6813" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0015420000000000000000">Quicksort</A></H2><P>The second exchange sort we consideris the <em>quicksort</em><A NAME=36380> </A> algorithm.Quicksort is a <em>divide-and-conquer</em> style algorithm.A divide-and-conquer algorithm solves a given problemby splitting it into two or more smaller subproblems,recursively solving each of the subproblems,and then combining the solutions to the smaller problemsto obtain a solution to the original one.<P>To sort the sequence <IMG WIDTH=156 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68897" SRC="img1975.gif" >,quicksort performs the following steps:<OL><LI> Select one of the elements of <I>S</I>. The selected element, <I>p</I>, is called the <em>pivot</em><A NAME=36384> </A>.<LI> Remove <I>p</I> from <I>S</I> and then partition the remaining elements of <I>S</I> into two distinct sequences, <I>L</I> and <I>G</I>, such that every element in <I>L</I> is less than or equal to the pivot and every element in <I>G</I> is greater than or equal to the pivot. In general, both <I>L</I> and <I>G</I> are <em>unsorted</em>.<LI> Rearrange the elements of the sequence as follows: <P> <IMG WIDTH=389 HEIGHT=42 ALIGN=BOTTOM ALT="displaymath69279" SRC="img2026.gif" ><P> Notice that the pivot is now in the position in which it belongs in the sorted sequence, since all the elements to the left of the pivot are less than or equal to the pivot and all the elements to the right are greater than or equal to it.<LI> Recursively quicksort the unsorted sequences <I>L</I> and <I>G</I>.</OL><P>The first step of the algorithm is a crucial one.We have not specified how to select the pivot.Fortunately, the sorting algorithm works no matter whichelement is chosen to be the pivot.However, the pivot selection affects directlythe running time of the algorithm.If we choose poorly the running time will be poor.<P>Figure <A HREF="page490.html#figsort3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the detailed operation of quicksortas it sorts the sequence <IMG WIDTH=159 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69309" SRC="img2027.gif" >.To begin the sort, we select a pivot.In this example, the value 4 in the last array position is chosen.Next, the remaining elements are partitioned into two sequences,one which contains values less than or equal to 4 ( <IMG WIDTH=101 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69315" SRC="img2028.gif" >)and one which contains values greater than or equal to 4( <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69319" SRC="img2029.gif" >).Notice that the partitioning is accomplished by exchanging elements.This is why quicksort is considered to be an exchange sort.<P><P><A NAME="37551"> </A><A NAME="figsort3"> </A> <IMG WIDTH=578 HEIGHT=587 ALIGN=BOTTOM ALT="figure36394" SRC="img2030.gif" ><BR><STRONG>Figure:</STRONG> ``Quick'' sorting.<BR><P><P>After the partitioning, the pivot is inserted between the two sequences.This is called <em>restoring</em> the pivot.To restore the pivot, we simply exchange it with the first element of <I>G</I>.Notice that the 4 is in its correct position in the sorted sequenceand it is not considered any further.<P>Now the quicksort algorithm calls itself recursively,first to sort the sequence <IMG WIDTH=101 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69315" SRC="img2028.gif" >;second to sort the sequence <IMG WIDTH=118 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69339" SRC="img2031.gif" >.The quicksort of <I>L</I> selects 1 as the pivot,and creates the two subsequences <IMG WIDTH=60 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline69345" SRC="img2032.gif" > and <IMG WIDTH=77 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline69347" SRC="img2033.gif" >.Similarly, the quicksort of <I>G</I> uses 5 as the pivotand creates the two subsequences <IMG WIDTH=78 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline69353" SRC="img2034.gif" > and <IMG WIDTH=81 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline69355" SRC="img2035.gif" >.<P>At this point in the example the recursion has been stopped.It turns out that to keep the code simple,quicksort algorithms usually stop the recursion when the lengthof a subsequence falls below a critical value called the <em>cut-off</em>.In this example, the cut-off is two(i.e., a subsequence of two or fewer elements is not sorted).This means that when the algorithm terminates,the sequence is not yet sorted.However as Figure <A HREF="page490.html#figsort3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows,the sequence is <em>almost</em> sorted.In fact, every element is guaranteed to be less than two positionsaway from its final resting place.<P>We can complete the sorting of the sequence by using a straight insertion sort.In Section <A HREF="page484.html#secsortinginsertion"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> it is shown thatstraight insertion is quite good at sorting sequences that are almost sorted.In fact, if we know that every element of the sequence is at most <I>d</I>positions from its final resting place,the running time of straight insertion is <I>O</I>(<I>dn</I>) andsince <I>d</I>=2 is a constant, the running time is <I>O</I>(<I>n</I>).<P><BR> <HR><UL> <LI> <A NAME="tex2html6814" HREF="page491.html#SECTION0015421000000000000000">Implementation</A></UL><HR><A NAME="tex2html6811" HREF="page491.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6809" HREF="page488.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6803" HREF="page489.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6813" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -