📄 page74.html
字号:
<HTML>
<HEAD>
<TITLE>Example-Bucket Sort</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html2813" HREF="page75.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page75.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2811" HREF="page70.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page70.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2805" HREF="page73.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2815" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2816" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION004440000000000000000">Example-Bucket Sort</A></H2>
<P>
So far all of the asymptotic running time analyses presented
in this chapter have resulted in tight big oh bounds.
In this section we consider an example which illustrates
that a cursory big oh analysis does not always result in a tight bound
on the running time of the algorithm.
<P>
In this section we consider an algorithm to solve the following problem:
Sort an array of <I>n</I> integers <IMG WIDTH=15 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline60559" SRC="img509.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img509.gif" >, <IMG WIDTH=14 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline60561" SRC="img510.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img510.gif" >, ..., <IMG WIDTH=33 HEIGHT=13 ALIGN=MIDDLE ALT="tex2html_wrap_inline60563" SRC="img511.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img511.gif" >,
each of which is known to be between 0 and <I>m</I>-1 for some fixed <I>m</I>.
I.e., <IMG WIDTH=225 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60571" SRC="img512.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img512.gif" >.
An algorithm for solving this problem,
called a <em>bucket sort</em><A NAME=2215> </A><A NAME=2216> </A>,
is given in Program <A HREF="page74.html#progbucketsortc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#progbucketsortc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
<P>
<P><A NAME="2221"> </A><A NAME="progbucketsortc"> </A> <IMG WIDTH=575 HEIGHT=275 ALIGN=BOTTOM ALT="program2218" SRC="img513.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img513.gif" ><BR>
<STRONG>Program:</STRONG> Bucket Sort<BR>
<P>
<P>
A bucket sort works as follows:
An array of <I>m</I> counters, or <em>buckets</em><A NAME=2226> </A>, is used.
Each of the counters is set initially to zero.
Then, a pass is made through the input array,
during which the buckets are used to keep a count of the
number of occurrences of each value between 0 and <I>m</I>-1.
Finally, the sorted result is produced by first placing
the required number of zeroes in the array,
then the required number of ones, followed by the twos,
and so on, up to <I>m</I>-1.
<P>
The analysis of the running time of Program <A HREF="page74.html#progbucketsortc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#progbucketsortc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
is summarized in Table <A HREF="page74.html#tblbucketsortc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#tblbucketsortc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
Clearly, the worst-case running time of the
first loop (lines 7-8) is <I>O</I>(<I>m</I>)
and that of the second loop (lines 9-10) is <I>O</I>(<I>n</I>).
<P>
<P><A NAME="2423"> </A>
<P>
<A NAME="tblbucketsortc"> </A>
<DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=3 BORDER FRAME=HSIDES RULES=GROUPS>
<COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER>
<TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
</TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=2> time</TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
<P>
statement </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> cursory analysis </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> careful analysis </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>7-8 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>m</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>m</I>) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
9-10 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>n</I>) </TD></TR>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>
11-13 </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>mn</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>m</I>+<I>n</I>) </TD></TR>
</TBODY><TBODY>
<TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP>TOTAL </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>mn</I>) </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>O</I>(<I>m</I>+<I>n</I>) </TD></TR>
</TBODY>
<CAPTION ALIGN=BOTTOM><STRONG>Table:</STRONG> Computing the running time
of Program <A HREF="page74.html#progbucketsortc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#progbucketsortc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A></CAPTION></TABLE>
</P></DIV><P>
<P>
Consider nested loops on lines 11-13.
Exactly <I>m</I> iterations of the outer loop are done--the number of iterations of the outer loop is fixed.
But the number of iterations of the inner loop depends
on <code>bucket [j]</code>--the value of the counter.
Since there are <I>n</I> numbers in the input array,
in the worst case a counter may have the value <I>n</I>.
Therefore, the running time of lines 11-13 is <I>O</I>(<I>mn</I>)
and this running time dominates all the others,
so the running time of Program <A HREF="page74.html#progbucketsortc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#progbucketsortc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> is <I>O</I>(<I>mn</I>).
(This is the <em>cursory analysis</em> column of Table <A HREF="page74.html#tblbucketsortc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#tblbucketsortc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
<P>
Unfortunately, this time our analysis has not produced a tight bound.
To see why this is the case,
we must consider the operation of Program <A HREF="page74.html#progbucketsortc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#progbucketsortc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> more carefully.
In particular, since we are sorting <I>n</I> items,
the final answer will only contain <I>n</I> items.
Therefore, line 13 will be executed exactly <I>n</I> times--not <I>mn</I> times as the cursory result suggests.
<P>
Consider the inner loop at line 12.
During the <IMG WIDTH=19 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline60619" SRC="img514.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img514.gif" > iteration of the outer loop,
the inner loop does <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60621" SRC="img515.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img515.gif" > iterations.
Therefore, the conditional test at line 12b
is done <IMG WIDTH=93 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60623" SRC="img516.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img516.gif" > times.
Therefore, the total number of times the conditional test is done is
<P> <IMG WIDTH=500 HEIGHT=67 ALIGN=BOTTOM ALT="eqnarray2249" SRC="img517.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img517.gif" ><P>
So, the running time of lines 11-13 is <I>O</I>(<I>m</I>+<I>n</I>)
and therefore running time of Program <A HREF="page74.html#progbucketsortc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#progbucketsortc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> is <I>O</I>(<I>m</I>+<I>n</I>).
(This is the <em>careful analysis</em> column of Table <A HREF="page74.html#tblbucketsortc" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page74.html#tblbucketsortc"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>).
<P>
<HR><A NAME="tex2html2813" HREF="page75.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page75.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html2811" HREF="page70.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page70.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html2805" HREF="page73.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page73.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html2815" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html2816" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -