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.

Linear Search

Part I: Object-Oriented Programming




Part II: Linear Structures

Stacks and Queues

Array-Based Structures

Linked Structures

Part III: Algorithms

Analysis of Algorithms

Searching and Sorting


Part IV: Trees and Sets



Part V: Advanced Topics

Advanced Linear Structures


Advanced Trees


Memory Management

Out to the Disk

Part VI: Appendices

A. Review of Java

B. Unified Modeling Language

C. Summation Formulae

D. Further Reading


show all menu

Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
ISBN: 0131469142
EAN: 2147483647
Year: 2004
Pages: 216
Authors: Peter Drake
Similar book on Amazon

Flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net