4.9: Exercises

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.

1. 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.
2. Add a Deck method called randomInt that takes two integers, low and high, and returns a random integer between low and high, including both. You can use the nextInt provided by java.util.Random, which we saw in Section 8.7. But you should avoid creating a Random object every time randomInt is invoked.
3. Write a method called swapCards that takes two indexes and swaps the cards at the given locations.
4. 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).

1. Write a method called indexLowest that uses the compareCard method to find the lowest card in a given range of the deck (from lowIndex to highIndex, including both).
2. Write a method called selectionSort that implements the selection sort algorithm in Section 13.3.
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 use subdeck to form two small subdecks, and use selection sort to sort them. Then you can pass the two halves to merge to see if it works.
4. Write the simple version of mergeSort, the one that divides the deck in half, uses selectionSort to sort the two halves, and uses merge to create a new, sorted deck.
5. Write a recursive version of mergeSort. Remember that selectionSort is a modifier and mergeSort 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 using java.lang.StringBuilder; you can find the documentation by doing a web search for “Java StringBuilder”.