📄 page499.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="tex2html6909" HREF="page500.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6907" HREF="page498.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6903" HREF="page498.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6911" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0015511000000000000000">Implementation</A></H3><P>Program <A HREF="page499.html#progstraightSelectionSortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> definesthe <tt>StraightSelectionSorter</tt> class.This class is derived from the abstract <tt>Sorter</tt> classdefined in Program <A HREF="page481.html#progsortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>and it provides an implementation for the <tt>_sort</tt> method.The <tt>_sort</tt> method follows directly from the algorithm discussed above.In each iteration of the main loop (lines 8-14),exactly one element is selected from the unsorted elementsand moved into the correct position.A linear search of the unsorted elements is done in orderto determine the position of the largest remaining element (lines 9-12).That element is then moved into the correct position (line 13).<P><P><A NAME="39195"> </A><A NAME="progstraightSelectionSortera"> </A> <IMG WIDTH=575 HEIGHT=275 ALIGN=BOTTOM ALT="program39052" SRC="img2069.gif" ><BR><STRONG>Program:</STRONG> <tt>StraightSelectionSorter</tt> class <tt>__init__</tt> and <tt>_sort</tt> methods.<BR><P><P>In all <I>n</I>-1 iterations of the outer loop are needed to sort the array.Notice that exactly one swap is done in each iteration of the outer loop.Therefore, <I>n</I>-1 data exchanges are needed to sort the list.<P>Furthermore, in the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > iteration of the outer loop,<I>i</I>-1 iterations of the inner loop are requiredand each iteration of the inner loop does one data comparison.Therefore, <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > data comparisons are needed to sort the list.<P>The total running time of the straight selection<tt>_sort</tt> method is <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >.Because the same number of comparisons and swaps are always done,this running time bound applies in all cases.That is, the best-case, average-case and worst-caserunning times are all <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >.<P><HR><A NAME="tex2html6909" HREF="page500.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6907" HREF="page498.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6903" HREF="page498.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6911" 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 + -