📄 page487.html
字号:
<HTML><HEAD><TITLE>Binary Insertion Sort</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="tex2html6773" HREF="page488.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6771" HREF="page483.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6767" HREF="page486.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6775" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0015330000000000000000">Binary Insertion Sort</A></H2><P>The straight insertion algorithm presented in the preceding sectiondoes a linear search to find the position in which to do the insertion.However, since the element is inserted into a sequence that is already sorted,we can use a binary search instead of a linear search.Whereas a linear search requires <I>O</I>(<I>n</I>) comparisons in the worst case,a binary search only requires <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" > comparisons.Therefore, if the cost of a comparison is significant,the binary search may be preferred.<P>Program <A HREF="page487.html#progbinaryInsertionSortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> definesthe <tt>BinaryInsertionSorter</tt> class.The <tt>BinaryInsertionSorter</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>.The framework of the <tt>_sort</tt> methodis essentially the same as that ofthe <tt>StraightInsertionSorter</tt> class.<P><P><A NAME="35301"> </A><A NAME="progbinaryInsertionSortera"> </A> <IMG WIDTH=575 HEIGHT=393 ALIGN=BOTTOM ALT="program35122" SRC="img2014.gif" ><BR><STRONG>Program:</STRONG> <tt>BinaryInsertionSorter</tt> class <tt>__init__</tt> and <tt>_sort</tt> methods.<BR><P><P>Exactly, <I>n</I>-1 iterations of the outer loop are done (lines 7-20).In each iteration, a binary search search is done to determinethe position at which to do the insertion (lines 9-16).In the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > iteration of the outer loop,the binary search considers array positions 0 to <I>i</I> (for <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69187" SRC="img2015.gif" >).The running time for the binary search in the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" >iteration is <IMG WIDTH=185 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69191" SRC="img2016.gif" >.Once the correct position is found,at most <I>i</I> swaps are needed to insert the element in its place (lines 17-20).<P>The worst-case running time of the binary insertion sortis dominated by the <I>i</I> swaps needed to do the insertion.Therefore, the worst-case running time is <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" >.Furthermore, since the algorithm only swaps adjacent array elements,the average running time is also <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > (see Section <A HREF="page486.html#secsortingavg"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).Asymptotically, the binary insertion sort is no better than straight insertion.<P>However, the binary insertion sort doesfewer array element comparisons than insertion sort.In the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > iteration of the outer loop,the binary search requires <IMG WIDTH=83 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69203" SRC="img2017.gif" > comparisons,for <IMG WIDTH=64 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69187" SRC="img2015.gif" >.Therefore, the total number of comparisons is<P> <IMG WIDTH=500 HEIGHT=97 ALIGN=BOTTOM ALT="eqnarray35139" SRC="img2018.gif" ><P>(This result follows directly from Theorem <A HREF="page354.html#theorempqueuesiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P>The number of comparisons required bythe straight insertion sort is <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > in the worst caseas well as on average.Therefore on average, the binary insertion sortuses fewer comparisons than straight insertion sort.On the other hand, the previous section shows that in the best casethe running time for straight insertion is <I>O</I>(<I>n</I>).Since the binary insertion sort method <em>always</em> does the binary search,its best case running time is <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" >.Table <A HREF="page487.html#tblsortinginsertion"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> summarizes the asymptotic running timesfor the two insertion sorts.<P><P><A NAME="35150"> </A><P> <A NAME="tblsortinginsertion"> </A> <DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=4 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=3> running time</TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP><P> algorithm </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> best case </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> average case </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> worst case </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>straight insertion sort </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> binary insertion sort </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline58629" SRC="img258.gif" > </TD></TR></TBODY><CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Running times for insertion sorting.</CAPTION></TABLE></P></DIV><P><HR><A NAME="tex2html6773" HREF="page488.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html6771" HREF="page483.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html6767" HREF="page486.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html6775" 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 + -