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 (std::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 swap_cards again, so we only need one new one, called find_lowest_card, 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 Counting.

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

If I'm writing a long, complex function with many steps, a(n) would help me condense the function's code and make it easier to understand.

Try writing the find_lowest_card function in the commented section of the active code below. Once you're done with find_lowest_card, try using it along with swap_cards to implement the card_deck member function sort_deck. 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.

Example c192_sorting_deck_2
 1#include <cstddef>
 2#include <random>
 3#include <iostream>
 4#include <string>
 5#include <vector>
 6#include <cstdlib>
 7
 8enum card_suit { clubs, diamonds, hearts, spades };
 9
10enum card_rank { ace=1, two, three, four, five, six, seven, eight, nine,
11ten, jack, queen, king };
12
13std::size_t random_int(std::size_t low, std::size_t high);
14
15struct playing_card {
16    card_rank rank;
17    card_suit suit;
18    playing_card ();
19    playing_card (card_suit s, card_rank r);
20    void print () const;
21    bool is_greater (const playing_card& c2) const;
22};
23
24struct card_deck {
25    std::vector<playing_card> cards;
26    card_deck ();
27    void print () const;
28    void swap_cards (std::size_t index1, std::size_t index2);
29    std::size_t find_lowest_card (std::size_t index);
30    void shuffle_deck ();
31    void sort_deck ();
32};
33
34std::size_t card_deck::find_lowest_card (std::size_t index) {
35    // ``find_lowest_card`` should search through the vector of cards
36    // starting at index and return the index of the smallest card.
37    // Delete the return 0 and write your implementation here.
38    return 0;
39}
40
41void card_deck::sort_deck () {
42    // Follow the pseudocode from above and use ``find_lowest_card`` and
43    // ``swap_cards`` to write the ``sort`` member function.
44    // Write your implementation here.
45}
46
47int main() {
48    card_deck deck;
49    deck.shuffle_deck ();
50    deck.sort_deck ();
51    deck.print ();
52}
find_lowest_card Help

Let's write the code for the find_lowest_card function. find_lowest_card should take an index as a parameter and return an int.

  1.   min = i;
 }
}
  2.  return cards[min];
}
  3.  return min;
}
  4. for (std::size_t i = 0; i < cards.size(); ++i) {
  5. for (std::size_t i = index; i < cards.size(); ++i) {
  6. if (cards[i].is_greater(cards[min])) {
  7. if (cards[min].is_greater(cards[i])) {
  8. std::size_t card_deck::find_lowest_card (std::size_t index) {
  9. std::size_t min = index;
  10. void card_deck::find_lowest_card (std::size_t index) {
sort_deck Help

Let's write the code for the sort_deck function. We'll use find_lowest_card and swap_cards in our implementation of sort_deck.

  1.   swap_cards (i, x);
 }
}
  2. card_deck::sort_deck () {
  3. for (std::size_t i = 0; i < cards.size(); i++) {
  4. std::size_t x = find_lowest_card (cards.size());
  5. std::size_t x = find_lowest_card (i);
  6. void card_deck::sort_deck () {