4.9: Exercises
- Page ID
- 21112
The code for this chapter is in the ch13
directory of ThinkJavaCode
. See [Section 0.4] for instructions on how to download the repository. Before you start the exercises, we recommend that you compile and run the examples.
Exercise \(\PageIndex{1}\)
You can learn more about the sorting algorithms in this chapter, and others, at www.sorting-algorithms.com/. This site includes explanations of the algorithms, animations that show how they work, and analysis of their efficiency.
Exercise \(\PageIndex{2}\)
The goal of this exercise is to implement the shuffling algorithm from this chapter.
- In the repository for this book, you should find a file called Deck.java that contains the code in this chapter. Check that you can compile it in your environment.
- Add a
Deck
method calledrandomInt
that takes two integers,low
andhigh
, and returns a random integer betweenlow
andhigh
, including both. You can use thenextInt
provided byjava.util.Random
, which we saw in Section 8.7. But you should avoid creating aRandom
object every timerandomInt
is invoked. - Write a method called
swapCards
that takes two indexes and swaps the cards at the given locations. - Write a method called
shuffle
that uses the algorithm in Section 13.2.
Exercise \(\PageIndex{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).
- Write a method called
indexLowest
that uses thecompareCard
method to find the lowest card in a given range of the deck (fromlowIndex
tohighIndex
, including both). - Write a method called
selectionSort
that implements the selection sort algorithm in Section 13.3. - Using the pseudocode in Section 13.4, write the method called
merge
. The best way to test it is to build and shuffle a deck. Then usesubdeck
to form two small subdecks, and use selection sort to sort them. Then you can pass the two halves tomerge
to see if it works. - Write the simple version of
mergeSort
, the one that divides the deck in half, usesselectionSort
to sort the two halves, and usesmerge
to create a new, sorted deck. - Write a recursive version of
mergeSort
. Remember thatselectionSort
is a modifier andmergeSort
is a pure method, which means that they get invoked differently:deck.selectionSort(); // modifies an existing deck deck = deck.mergeSort(); // replaces old deck with new
Exercise \(\PageIndex{4}\)
The goal of this exercise is to practice top-down programming by implementing “insertion sort”. Read about insertion sort at www.sorting-algorithms.com/insertion-sort. Write a method named insertionSort
that implements this algorithm.
Exercise \(\PageIndex{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
+
operator to concatenate strings, but it is not very efficient. Consider usingjava.lang.StringBuilder
; you can find the documentation by doing a web search for “Java StringBuilder”.