page515.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 89 行
HTML
89 行
<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="tex2html7082" HREF="page516.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7080" HREF="page514.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7076" HREF="page514.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7084" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0015821000000000000000">Implementation</A></H3><P>Program <A HREF="page515.html#progradixSortera"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces the <tt>RadixSorter</tt> class.The <tt>RadixSorter</tt> class extends 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>.This radix sorter is designed to sort specifically an array of <tt>int</tt>s.<P><P><A NAME="46442"> </A><A NAME="progradixSortera"> </A> <IMG WIDTH=575 HEIGHT=218 ALIGN=BOTTOM ALT="program46274" SRC="img2133.gif" ><BR><STRONG>Program:</STRONG> <tt>RadixSorter</tt> class <tt>__init__</tt> method.<BR><P><P>Three constants are declaredin the <tt>RadixSorter</tt> class--<tt>R</tt>, <tt>r</tt>, and <tt>p</tt>.The constant <I>R</I> represents the radix and <IMG WIDTH=71 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline69901" SRC="img2134.gif" >.The constant <I>p</I> is the number sorting passes needed to sort the data.In this case <I>r</I>=8 and <IMG WIDTH=94 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline69907" SRC="img2135.gif" >.Therefore, a radix-256 sort is being done.We have chosen <I>R</I> as a power of two becausethat way the computations required to implement the radix sortcan be implemented efficiently using simple bit shift and mask operations.In order to sort <I>b</I>-bit integers,it is necessary to make <IMG WIDTH=147 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline69913" SRC="img2136.gif" >sorting passes.<P>Two instance attributes are defined in the <tt>RadixSorter</tt> class--<tt>_count</tt> and <tt>_tempArray</tt>The <tt>_count</tt> instance attribute is an array of integersused to implement the sorting passes.An array of integers of length <I>R</I> is createdand assigned to the <tt>_count</tt> array.The <tt>_tempArray</tt> instance attribute is usedfor temporary storage in the <tt>_sort</tt> method.<P>The <tt>_sort</tt> method shown in Program <A HREF="page515.html#progradixSorterb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>begins by creating a temporary array of length <I>n</I>.Each iteration of the main loop corresponds to one passof the radix sort (lines 5-21).In all <I>p</I> iterations are required.<P><P><A NAME="46445"> </A><A NAME="progradixSorterb"> </A> <IMG WIDTH=575 HEIGHT=447 ALIGN=BOTTOM ALT="program46297" SRC="img2137.gif" ><BR><STRONG>Program:</STRONG> <tt>RadixSorter</tt> class <tt>_sort</tt> method.<BR><P><P>During the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" > pass of the main loopthe following steps are done:First, the <I>R</I> counters are all set to zero (lines 6-7).This takes <I>O</I>(<I>R</I>) time.Then a pass is made through the input array during whichthe number of occurrences of each radix-<I>R</I> digit in the <IMG WIDTH=17 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57847" SRC="img77.gif" >digit position are counted (lines 8-11).This pass takes <I>O</I>(<I>n</I>) time.Notice that during this pass all the input data is copiedinto the temporary array.<P>Next,the array of counts is transformed into an array of offsetsaccording to Equation <A HREF="page514.html#eqnsortingx"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.This requires a single pass through the counter array (lines 12-16).Therefore, it takes <I>O</I>(<I>R</I>) time.Finally, the data sequence is permuted by copying the valuesfrom the temporary array back into the input array (lines 17-21).Since this requires a single pass through the data arrays,the running time is <I>O</I>(<I>n</I>).<P>After the <I>p</I> sorting passes have been done,the array of data is sorted.The running time for the <tt>_sort</tt> methodof the <tt>RadixSorter</tt> class is <IMG WIDTH=85 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline69939" SRC="img2138.gif" >.If we assume that the size of an integer is 32 bits and given that <I>R</I>=256, the number of sorting passes required is <I>p</I>=4.Therefore, the running time for the radix sort is simply <I>O</I>(<I>n</I>).That is, radix sort is a linear-time sorting algorithm.<P><HR><A NAME="tex2html7082" HREF="page516.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7080" HREF="page514.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7076" HREF="page514.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html7084" 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 + =
减小字号Ctrl + -
显示快捷键?