📄 page491.html
字号:
<HTML><HEAD><TITLE>Implementation</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="tex2html6821" HREF="page492.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6819" HREF="page490.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6815" HREF="page490.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6823" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0015421000000000000000">Implementation</A></H3><P>Program <A HREF="page491.html#progquickSortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces the <tt>QuickSorter</tt> class.The abstract <tt>QuickSorter</tt> class extendsthe abstract <tt>Sorter</tt> classdefined in Program <A HREF="page481.html#progsortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.It declares the abstract method <tt>selectPivot</tt>the implementation of which is provided by a derived class.<P><P><A NAME="38005"> </A><A NAME="progquickSortera"> </A> <IMG WIDTH=575 HEIGHT=199 ALIGN=BOTTOM ALT="program37566" SRC="img2036.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>QuickSorter</tt> class <tt>__init__</tt> and <tt>selectPivot</tt> methods.<BR><P><P>Program <A HREF="page491.html#progquickSorterb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>quicksort</tt> methodof the <tt>QuickSorter</tt> class.In addition to <tt>self</tt>,the <tt>quicksort</tt> method takes two integer arguments,<tt>left</tt> and <tt>right</tt>,which denote left and right ends, respectively,of the section of the array to be sorted.That is, this <tt>quicksort</tt> method sorts<P> <IMG WIDTH=414 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath69365" SRC="img2037.gif" ><P>.<P><P><A NAME="38009"> </A><A NAME="progquickSorterb"> </A> <IMG WIDTH=575 HEIGHT=562 ALIGN=BOTTOM ALT="program37593" SRC="img2038.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>QuickSorter</tt> class <tt>quicksort</tt> method.<BR><P><P>As discussed above,the <tt>QuickSorter</tt> only sorts sequenceswhose length exceeds the <em>cut-off</em> value.Since the implementation shown only works correctlywhen the number of elements inthe sequence to be sorted is three or more,the <tt>CUTOFF</tt> value of two is used (line 3).<P>The algorithm begins by calling the method <tt>selectPivot</tt> whichchooses one of the elements to be the pivot (line 7).The implementation of <tt>selectPivot</tt> is discussed below.All that we require here is that the value <I>p</I> returned by <tt>selectPivot</tt>satisfies <IMG WIDTH=124 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline69369" SRC="img2039.gif" >.Having selected an element to be the pivot,we <em>hide</em> the pivot by swapping it with the right-most elementof the sequence (line 8).The pivot is <em>hidden</em> in orderto get it out of the way of the next step.<P>The next step partitions the remaining elements into two sequences--one comprised of values less than or equal to the pivot,the other comprised of values greater than or equal to the pivot.The partitioning is done using two array indices, <tt>i</tt> and <tt>j</tt>.The first, <tt>i</tt>, starts at the left end and moves to the right;the second, <tt>j</tt>, starts at the right end and moves to the left.<P>The variable <tt>i</tt> is increasedas long as <tt>array[i]</tt> is less than the pivot (lines 13-14).Then the variable <tt>j</tt> is decreasedas long as <tt>array[j]</tt> is greater than the pivot (lines 15-16).When <tt>i</tt> and <tt>j</tt> meet (or pass each other),the partitioning is done (lines 17-18).Otherwise, <IMG WIDTH=35 HEIGHT=21 ALIGN=MIDDLE ALT="tex2html_wrap_inline69371" SRC="img2040.gif" >but <IMG WIDTH=215 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline69373" SRC="img2041.gif" >.This situation is remediedby swapping <tt>array[i]</tt> and <tt>array[j]</tt> (line 19).<P>When the partitioning loop terminates,the pivot is still in <tt>array[right]</tt>;the value in <tt>array[i]</tt> is greater than or equal to the pivot;everything to the left is less than or equal to the pivot; andeverything to the right is greater than or equal to the pivot.We can now put the pivot in its proper placeby swapping it with <tt>array[i]</tt> (lines 22-23).This is called <em>restoring</em> the pivot.With the pivot in its final resting place,all we need to do is sort the subsequenceson either side of the pivot (lines 24-27).<P>Program <A HREF="page491.html#progquickSorterc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> defines the <tt>_sort</tt> methodof the abstract <tt>QuickSorter</tt> class.The <tt>_sort</tt> acts as the front endto the recursive <tt>quicksort</tt> method given in Program <A HREF="page491.html#progquickSorterb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.It calls the <tt>quicksort</tt> methodwith <tt>left</tt> set to zeroand <tt>right</tt> set to <I>n</I>-1,where <I>n</I> is the length of the array to be sorted.Finally, it uses a <tt>StraightInsertionSorter</tt>to finish sorting the list.<P><P><A NAME="38011"> </A><A NAME="progquickSorterc"> </A> <IMG WIDTH=575 HEIGHT=161 ALIGN=BOTTOM ALT="program37643" SRC="img2042.gif" ><BR><STRONG>Program:</STRONG> Abstract <tt>QuickSorter</tt> class <tt>_sort</tt> method.<BR><P><HR><A NAME="tex2html6821" HREF="page492.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6819" HREF="page490.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6815" HREF="page490.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6823" 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 + -