Java Reference
In-Depth Information
627
Chapter 14 Sorting and Searching
C
HAPTER
G
OALS
ȗ 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
One of the most common tasks in data processing is sorting. For example, a
collection of employees may need to be printed out in alphabetical order or sorted by
salary. We will study several sorting methods in this chapter and compare their
performance. This is by no means an exhaustive treatment of the subject of sorting.
You will likely revisit this topic at a later time in your computer science studies. A
good overview of the many sorting methods available can be found in [
1
].
Once a sequence of objects is sorted, one can locate individual objects rapidly. We
will study the binary search algorithm, which carries out this fast lookup.
627
628
14.1 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
:
