The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.


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.

Again, we are going to traverse the deck and at each location choose another card 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.

By "remaining in the deck," I mean cards that are at or to the right of the index i.

  for (int i=0; i<cards.length(); i++) {
    // find the lowest card at or to the right of i
    // swap the ith card and the lowest card

Again, the pseudocode helps with the design of the helper functions. In this case we can use swapCards again, so we only need one new one, called findLowestCard, that takes a vector of cards and an index where it should start looking.

This process, using pseudocode to figure out what helper functions are needed, is sometimes called top-down design, in contrast to the bottom-up design I discussed in Section 10.8.

Once again, I am going to leave the implementation up to the reader.

Last Update: 2005-12-05