Searching and Sorting

This chapter introduces the simplest algorithms for searching and sorting arrays. We will see more sophisticated algorithms for these tasks in Chapters 9, 12, and 14.

Searching is the task of determining whether a collection contains some particular element. The contains() method from the List interface (Chapter 5) performs searching. In this chapter, we will see a couple of ways to do this more efficiently if the collection is already in order from smallest to largest. Linear search is covered in Section 8.1, binary search in Section 8.2.

Sorting is the task of putting a collection in increasing order. We will not bother to write a game involving sorting, but it should be clear that this is a useful operation to perform in many situations. In many card games, for example, sorting one's hand makes it easier to decide which play to make. We might also wish to print a list of mailing addresses or book titles in sorted order. Section 8.3 presents the insertion sort algorithm.

For simplicity, we introduce the searching and sorting algorithms as static methods operating on arrays of ints. In Section 8.4, we introduce an interface that allows us to search and sort arrays of other things. Section 8.5 closes out the chapter with some thoughts on sorting linked lists.