from each deck. Since humans usually don't shuffle perfectly, after about 7 iterations the order of the deck is pretty well randomized. But a computer program would have the annoying property of doing a perfect shuffle every time,which is not really very random. In fact, after 8 perfect shuffles, you would find the deck back in the same order you started in.  For a discussion of thatclaim, see <A HREF="javascript:if(confirm('http://www.wiskit.com/marilyn/craig.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://www.wiskit.com/marilyn/craig.html'" tppabs="http://www.wiskit.com/marilyn/craig.html"><TT>http://www.wiskit.com/marilyn/craig.html</TT></A> or do a web search with the keywords ``perfect shuffle.''</P><P>A better shuffling algorithm is to traverse the deck one card at a time, andat each iteration choose two cards and swap them.</P><P>Here is an outline of how this algorithm works. To sketch the program, I am using a combination of C++ statements and English words that is sometimes called <B>pseudocode</B>:</P><PRE>  for (int i=0; i&lt;cards.length(); i++) {    // choose a random number between i and cards.length()    // swap the ith card and the randomly-chosen card  }</PRE><P>The nice thing about using pseudocode is that it often makes it clear what functions you are going to need. In this case, we need something like <TT>randomInt</TT>, which chooses a random integer between the parameters <TT>low</TT> and <TT>high</TT>, and <TT>swapCards</TT> which takes two indices and switches the cards at the indicated positions.</P><P>You can probably figure out how to write <TT>randomInt</TT> by looking at Section 10.5, although you will have to be careful about possibly generating indices that are out of range.</P><P>You can also figure out <TT>swapCards</TT> yourself. I will leave the remaining implementation of these functions as an exercise to the reader.</P><BR><BR><H3>13.7 Sorting</H3><P>Now that we have messed up the deck, we need a way to put it back in order.Ironically, there is an algorithm for sorting that is very similar to the algorithm for shuffling.</P><P>Again, we are going to traverse the deck and at each location choose anothercard and swap. The only difference is that this time instead of choosing the other card at random, we are going to find the lowest card remaining in the deck.</P><P>By ``remaining in the deck,'' I mean cards that are at or to the right of the index <TT>i</TT>.</P><PRE>  for (int i=0; i&lt;cards.length(); i++) {    // find the lowest card at or to the right of i    // swap the ith card and the lowest card  }</PRE><P>Again, the pseudocode helps with the design of the <B>helper functions</B>.In this case we can use <TT>swapCards</TT> again, so we only need one new one, called <TT>findLowestCard</TT>, that takes a vector of cards and an index whereit should start looking.</P><P>This process, using pseudocode to figure out what helper functions are needed, is sometimes called <B>top-down design</B>, in contrast to the bottom-up design I discussed in Section 10.8.</P><P>Once again, I am going to leave the implementation up to the reader.</P><BR><BR><H3>13.8 Subdecks</H3><P>How should we represent a hand or some other subset of a full deck? One easychoice is to make a <TT>Deck</TT> object that has fewer than 52 cards.</P><P>We might want a function, <TT>subdeck</TT>, that takes a vector of cards anda range of indices, and that returns a new vector of cards that contains the specified subset of the deck:</P><PRE>Deck Deck::subdeck (int low, int high) const {  Deck sub (high-low+1);	  for (int i = 0; i&lt;sub.cards.length(); i++) {    sub.cards[i] = cards[low+i];  }  return sub;}</PRE><P>To create the local variable named <TT>subdeck</TT> we are using the <TT>Deck</TT> constructor that takes the size of the deck as an argument and that does not initialize the cards. The cards get initialized when they are copied from the original deck.</P><P>The length of the subdeck is <TT>high-low+1</TT> because both the low card and high card are included. This sort of computation can be confusing, and leadto ``off-by-one'' errors. Drawing a picture is usually the best way to avoid them.</P><P>As an exercise, write a version of <TT>findBisect</TT> that takes a subdeck as an argument, rather than a deck and an index range.  Which version is more error-prone?  Which version do you think is more efficient?</P><BR><BR><H3>13.9 Shuffling and dealing</H3><P>In Section 13.6 I wrote pseudocode for a shuffling algorithm. Assuming that we have a function called <TT>shuffleDeck</TT> that takes a deck as an argument and shuffles it, we can create and shuffle a deck:</P><PRE>  Deck deck;               // create a standard 52-card deck  deck.shuffle ();         // shuffle it</PRE><P>Then, to deal out several hands, we can use <TT>subdeck</TT>:</P><PRE>  Deck hand1 = deck.subdeck (0, 4);  Deck hand2 = deck.subdeck (5, 9);  Deck pack = deck.subdeck (10, 51);</PRE><P>This code puts the first 5 cards in one hand, the next 5 cards in the other,and the rest into the pack.</P><P>When you thought about dealing, did you think we should give out one card ata time to each player in the round-robin style that is common in real card games? I thought about it, but then realized that it is unnecessary for a computer program. The round-robin convention is intended to mitigate imperfect shuffling and make it more difficult for the dealer to cheat. Neither of these is an issue for a computer.</P><P>This example is a useful reminder of one of the dangers of engineering metaphors: sometimes we impose restrictions on computers that are unnecessary, or expect capabilities that are lacking, because we unthinkingly extend a metaphor past its breaking point. Beware of misleading analogies.</P><BR><BR><H3>13.10 Mergesort</H3>In Section 13.7, we saw a simple sorting algorithm that turns out not to be very efficient. In order to sort $n$ items, it has to traverse the vector <TT>n</TT> times, and each traversal takes an amount of time that is proportional to <TT>n</TT>. The total time, therefore, is proportional to <TT>n<SUP>2</SUP></TT>.</P><P>In this section I will sketch a more efficient algorithm called <B>mergesort</B>. To sort <TT>n</TT> items, mergesort takes time proportional to <TT>n log n</TT>. That may not seem impressive, but as <TT>n</TT> gets big, the difference between <TT>n<SUP>2</SUP></TT> and <TT>n log n</TT> can be enormous. Try out a few values of $n$ and see.</P><P>The basic idea behind mergesort is this: if you have two subdecks, each of which has been sorted, it is easy (and fast) to merge them into a single, sorted deck. Try this out with a deck of cards:</P><OL>  <LI>Form two subdecks with about 10 cards each and sort them so that when   they are face up the lowest cards are on top. Place both decks face up in   front of you.</LI><BR><BR>  <LI>Compare the top card from each deck and choose the lower one. Flip it   over and add it to the merged deck.</LI><BR><BR>  <LI>Repeat step two until one of the decks is empty. Then take the remaining   cards and add them to the merged deck.</LI></OL><P>The result should be a single sorted deck. Here's what this looks like in pseudocode:</P><PRE>  Deck merge (const Deck& d1, const Deck& d2) {    // create a new deck big enough for all the cards    Deck result (d1.cards.length() + d2.cards.length());    // use the index i to keep track of where we are in    // the first deck, and the index j for the second deck    int i = 0;    int j = 0;		    // the index k traverses the result deck    for (int k = 0; k&lt;result.cards.length(); k++) {			      // if d1 is empty, d2 wins; if d2 is empty, d1 wins;      // otherwise, compare the two cards			      // add the winner to the new deck    }    return result;  }</PRE><P>I chose to make <TT>merge</TT> a nonmember function becausethe two arguments are symmetric.</P> <P>The best way to test <TT>merge</TT> is to build and shuffle a deck, use subdeck to form two (small) hands, and then use the sort routine from the previous chapter to sort the two halves. Then you can pass the two halves to <TT>merge</TT> to see if it works.</P><P>If you can get that working, try a simple implementation of<TT>mergeSort</TT>:</P><PRE>Deck Deck::mergeSort () const {  // find the midpoint of the deck  // divide the deck into two subdecks  // sort the subdecks using sort  // merge the two halves and return the result}</PRE><P>Notice that the current object is declared <TT>const</TT> because <TT>mergeSort</TT> does not modify it. Instead, it creates and returns a new <TT>Deck</TT> object.</P><P>If you get that version working, the real fun begins!  The magical thing about mergesort is that it is recursive. At the point where you sort the subdecks, why should you invoke the old, slow version of <TT>sort</TT>? Why notinvoke the spiffy new <TT>mergeSort</TT> you are in the process of writing?</P>Not only is that a good idea, it is <I>necessary</I> in order toachieve the performance advantage I promised.  In order to make itwork, though, you have to add a base case so that it doesn't recurseforever.  A simple base case is a subdeck with 0 or 1 cards.  If {\ttmergesort} receives such a small subdeck, it can return itunmodified, since it is already sorted.<P>The recursive version of <TT>mergesort</TT> should look something like this:</P><PRE>Deck Deck::mergeSort (Deck deck) const {  // if the deck is 0 or 1 cards, return it  // find the midpoint of the deck  // divide the deck into two subdecks  // sort the subdecks using mergesort  // merge the two halves and return the result}</PRE><P>As usual, there are two ways to think about recursive programs: you can think through the entire flow of execution, or you can make the ``leap of faith.'' I have deliberately constructed this example to encourage you to make the leap of faith.</P><P>When you were using <TT>sort</TT> to sort the subdecks, you didn't feel compelled to follow the flow of execution, right?  You just assumed that the <TT>sort</TT> function would work because you already debugged it. Well, all you did to make <TT>mergeSort</TT> recursive was replace one sort algorithm with another. There is no reason to read the program differently.</P><P>Well, actually you have to give some thought to getting the base case right and making sure that you reach it eventually, but other than that, writing the recursive version should be no problem.  Good luck!</P><BR><BR><H3>13.11 Glossary</H3><DL>  <DT>pseudocode:</DT><DD> A way of designing programs by writing rough drafts   in a combination of English and C++.</DD>  <DT>helper function:</DT><DD> Often a small function that does not do anything  enormously useful by itself, but which helps another, more useful, function.  </DD>  <DT>bottom-up design:</DT><DD> A method of program development that uses   pseudocode to sketch solutions to large problems and design the interfaces of  helper functions.</DD>  <DT>mergesort:</DT><DD> An algorithm for sorting a collection of values.   Mergesort is faster than the simple algorithm in the previous chapter,   especially for large collections.</DD></DL><BR><DIV CLASS=navigation><HR>  <TABLE ALIGN=center WIDTH="100%" CELLPADDING=0 CELLSPACING=2>  <TR>    <TD><A HREF="chapter14.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter14.html">      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="next"       SRC="images/next.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/next.gif"></A>    </TD>    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="up"       SRC="images/up.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/up.gif"></A>    </TD>    <TD><A HREF="chapter12.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter12.html">      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="previous"      SRC="images/previous.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/previous.gif"></A>    </TD>    <TD ALIGN=center BGCOLOR="#99CCFF" WIDTH="100%">      <B CLASS=title>How to Think Like a Computer Scientist: Chapter 13</B>    </TD>    <TD><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT="contents"      SRC="images/contents.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/contents.gif"></A>    </TD>    <TD>      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">    </TD>    <TD>      <IMG WIDTH=32 HEIGHT=32 ALIGN=bottom BORDER=0 ALT=""      SRC="images/blank.gif" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/blank.gif">    </TD>  </TR>  </TABLE>  <B CLASS=navlabel>Next:</B>  <SPAN CLASS=sectref><A HREF="chapter14.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter14.html">Chapter 14</A></SPAN>  <B CLASS=navlabel>Up:</B>  <SPAN CLASS=sectref><A HREF="index.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/index.html">Index</A></SPAN>  <B CLASS=navlabel>Previous:</B>  <SPAN CLASS=sectref><A HREF="chapter12.html" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/chapter12.html">Chapter 12</A></SPAN>  <HR></DIV></BODY></HTML>