This HTML version of Think Java is provided for convenience, but it is not the best format of the book. In particular, some of the symbols are not rendered correctly. You might prefer to read the PDF version, or you can buy a hardcopy at Amazon. Chapter 13 Objects of arraysIn the previous chapter, we defined a class to represent cards and used an array of In this chapter, we take another step toward object-oriented programming by defining a class to represent a deck of cards. And we present algorithms for shuffling and sorting arrays. The code for this chapter is in Card.java and Deck.java, which are in the directory ch13 in the repository for this book. Instructions for downloading this code are on page ??. 13.1 The Deck classThe main idea of this chapter is to create a
The constructor initializes the instance variable with an array of We’ll add a second constructor that makes a standard 52-card deck and populates it with
This method is similar to the example in Section 12.6; we just turned it into a constructor.
We can now create a standard
Now that we have a
When you transform a static method into an instance method, it usually gets shorter.
We can simply type 13.2 Shuffling decksFor most card games you need to be able to shuffle the deck; that is, put the cards in a random order. In Section 8.7 we saw how to generate random numbers, but it is not obvious how to use them to shuffle a deck. One possibility is to model the way humans shuffle, which is usually dividing the deck in two halves and then choosing alternately from each one. Since humans usually don’t shuffle perfectly, after about seven 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 very random. In fact, after eight perfect shuffles, you would find the deck back in the order you started in! (For more information, see https://en.wikipedia.org/wiki/Faro_shuffle.) A better shuffling algorithm is to traverse the deck one card at a time, and at each iteration choose two cards and swap them. Here is an outline of how this algorithm works. To sketch the program, we will use a combination of Java statements and English. This technique is sometimes called pseudocode.
The nice thing about pseudocode is that it often makes clear what methods you are going to need.
In this case, we need a method that chooses a random integer between And this process – writing pseudocode first and then writing methods to make it work – is called top-down development (see https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design). One of the exercises at the end of the chapter asks you to write the helper methods 13.3 Selection sortNow that we have messed up the deck, we need a way to put it back in order. There is an algorithm for sorting that is ironically similar to the algorithm for shuffling. It’s called selection sort, because it works by traversing the array repeatedly and selecting the lowest (or highest) remaining card each time. During the first iteration, we find the lowest card and swap it with the card in the 0th position. During the ith iteration, we find the lowest card to the right of i and swap it with the ith card. Here is pseudocode for selection sort:
Again, the pseudocode helps with the design of the helper methods.
In this algorithm we can use One of the exercises at the end of the chapter asks you to write the helper method 13.4 Merge sortSelection sort is a simple algorithm, but it is not very efficient. To sort n items, it has to traverse the array n−1 times. Each traversal takes an amount of time proportional to n. The total time, therefore, is proportional to n2. In the next two sections, we’ll develop a more efficient algorithm called merge sort. To sort n items, merge sort takes time proportional to n log2 n. That may not seem impressive, but as n gets big, the difference between n2 and n log2 n can be enormous. For example, log2 of one million is around 20. So if you had to sort a million numbers, selection sort would require one trillion steps; merge sort would require only 20 million. The idea behind merge sort is this: if you have two subdecks, each of which has already been sorted, it is easy and fast to merge them into a single, sorted deck. Try this out with a deck of cards:
The result should be a single sorted deck. In the next few sections, we’ll explain how to implement this algorithm in Java. 13.5 SubdecksThe 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,
The first line creates an unpopulated subdeck.
Inside the The length of the subdeck is Figure 13.2 is a state diagram of a subdeck with Aliasing might not be a good idea, because changes to shared cards would be reflected in multiple decks.
But since 13.6 Merging decksThe next helper method we need is
One of the exercises at the end of the chapter asks you to implement 13.7 Adding recursionOnce your
An exercise at the end of the chapter asks you to implement this algorithm. Once you get it working, the real fun begins! The magical thing about merge sort is that it is inherently recursive. At the point where you sort the subdecks, why should you invoke the slower algorithm, To make The recursive version of
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” (see Section 6.8). This example should encourage you to make the leap of faith. When you used Well, almost. You might 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. 13.8 Vocabulary
13.9 ExercisesThe code for this chapter is in the ch13 directory of ThinkJavaCode. See page ?? for instructions on how to download the repository. Before you start the exercises, we recommend that you compile and run the examples. Exercise 1
You can learn more about the sorting algorithms in this chapter, and others, at http://www.sorting-algorithms.com/.
This site includes explanations of the algorithms, animations that show how they work, and analysis of their efficiency.
Exercise 2
The goal of this exercise is to implement the shuffling algorithm from this chapter.
Exercise 3
The goal of this exercise is to implement the sorting algorithms from this chapter.
Use the Deck.java file from the previous exercise (or create a new one from scratch).
Exercise 4
The goal of this exercise is to practice top-down programming by implementing “insertion sort”.
Read about insertion sort at http://www.sorting-algorithms.com/insertion-sort.
Write a method named insertionSort that implements this algorithm.
Exercise 5
Write a
toString method for the Deck class.
It should return a single string that represents the cards in the deck.
When it’s printed, this string should display the same results as the print method in Section 13.1.Hint: You can use the |
Are you using one of our books in a class?We'd like to know about it. Please consider filling out this short survey.
|