13.7. Sorting

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 (size_t i = 0; i < cards.size(); 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.

Note

Helper functions do exactly what it seems like they would do. They are shorter, simpler functions that help the bigger functions accomplish a task. As a result, they shorten the code used in the bigger functions, and they make the debugging process easier.

In this case we can use swapCards again, so we only need one new one, called findLowestCard, that takes an index where it should start looking in the vector of cards.

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.10.

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

Try writing the findLowestCard function in the commented section of the active code below. Once you’re done with findLowestCard, try using it along with swapCards to implement the Deck member function sortDeck. If done correctly, the program should output a sorted deck of cards. If you get stuck, you can reveal the extra problems at the end for help.

You have attempted of activities on this page