Skip to main content
Library homepage
 
Engineering LibreTexts

4.5: Subdecks

  • Page ID
    15295
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    The first step of merge sort is to split the deck into two subdecks, each with about half the cards. So we might want a method, subdeck, that takes a deck and a range of indexes. It returns a new deck that contains the specified subset of the cards:

    public Deck subdeck(int low, int high) {
        Deck sub = new Deck(high - low + 1);
        for (int i = 0; i < sub.cards.length; i++) {
            sub.cards[i] = this.cards[low + i];
        }
        return sub;
    }
    

    The first line creates an unpopulated subdeck. Inside the for loop, the subdeck gets populated with copies of references from the deck.

    The length of the subdeck is high - low + 1, because both the low card and the high card are included. This sort of computation can be confusing, and forgetting the + 1 often leads to “off-by-one” errors. Drawing a picture is usually the best way to avoid them.

    Figure 13.5.1 is a state diagram of a subdeck with low = 0 and high = 4. The result is a hand with five cards that are shared with the original deck; that is, they are aliased.

    State diagram showing the effect of subdeck.
    Figure \(\PageIndex{1}\): State diagram showing the effect of subdeck.

    Aliasing might not be a good idea, because changes to shared cards would be reflected in multiple decks. But since Card objects are immutable, this kind of aliasing is not a problem at all.


    This page titled 4.5: Subdecks is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press) .

    • Was this article helpful?