Introduction
Searching data involves determining whether a value (referred to as the search key) is present in the data and, if so, finding the value's location. Two popular search algorithms are the simple linear search and the faster but more complex binary search. Sorting places data in order, typically ascending or descending, based on one or more sort keys. A list of names could be sorted alphabetically, bank accounts could be sorted by account number, employee payroll records could be sorted by social security number, and so on. This chapter introduces two simple sorting algorithms, the selection sort and the insertion sort, along with the more efficient but more complex merge sort. Figure 16.1 summarizes the searching and sorting algorithms discussed in this book.
Chapter |
Algorithm |
Location |
---|---|---|
Searching Algorithms: |
||
16 |
Linear Search |
Section 16.2.1 |
Binary Search |
Section 16.2.2 |
|
Recursive Linear Search |
Exercise 16.8 |
|
Recursive Binary Search |
Exercise 16.9 |
|
17 |
Linear search of a List |
Exercise 17.21 |
Binary tree search |
Exercise 17.23 |
|
19 |
binarySearch method of class Collections |
Fig. 19.14 |
Sorting Algorithms: |
||
16 |
Selection Sort |
Section 16.3.1 |
Insertion Sort |
Section 16.3.2 |
|
Recursive Merge Sort |
Section 16.3.3 |
|
Bubble Sort |
Exercises 16.3 and 16.4 |
|
Bucket Sort |
Exercise 16.7 |
|
Recursive Quicksort |
Exercise 16.10 |
|
17 |
Binary tree sort |
Section 17.9 |
19 |
sort method of class Collections |
Fig. 19.8Fig. 19.11 |
SortedSet collection |
Fig. 19.19 |