Chapter 14. Sorting and Searching
CHAPTER GOALS
To study several sorting and searching algorithms
To appreciate that algorithms for the same task can differ widely in performance
To understand the big-Oh notation
To learn how to estimate and compare the performance of algorithms
To learn how to measure the running time of a program
Sorting and searching are among the most common tasks in data processing. Of course, the Java library contains methods for carrying out these operations. Nevertheless, studying algorithms for sorting and searching is fruitful because you will learn how to analyze the performance of algorithms and how to choose the best algorithm for a particular task. Sorting and searching are an excellent entry point into the study of algorithm analysis because the tasks themselves are simple to understand. As you will see in this chapter, the most straightforward algorithms do not perform very well, and we can achieve dramatic improvements with more sophisticated algorithms.
Selection Sort
In this section, we show you the first of several sorting algorithms. A sorting algorithm rearranges the elements of a collection so that they are stored in sorted order. To keep the examples simple, we will discuss how to sort an array of integers before going on to sorting strings or more complex data. Consider the following array a:
An obvious first step is to find the smallest element. In ...
Get Big Java, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
