Searching, Sorting and Big O - Java: How to Program Early Objects - page 811

19.1 Introduction
19.2 Linear Search
19.3 Big O Notation
19.3.1 O(1) Algorithms
19.3.2 O( n ) Algorithms
19.3.3 O( n 2 ) Algorithms
19.3.4 Big O of the Linear Search
19.4 Binary Search
19.4.1 Binary Search Implementation
19.4.2 Efficiency of the Binary Search
19.5 Sorting Algorithms
19.6 Selection Sort
19.6.1 Selection Sort Implementation
19.6.2 Efficiency of the Selection Sort

19.7 Insertion Sort
19.7.1 Insertion Sort Implementation
19.7.2 Efficiency of the Insertion Sort
19.8 Merge Sort
19.8.1 Merge Sort Implementation
19.8.2 Efficiency of the Merge Sort
19.9 Big O Summary for This Chapter's
Searching and Sorting Algorithms
19.10 Wrap-Up

Summary | Self-Review Exercises | Answers to Self-Review Exercises | Exercises

19.1 Introduction
Searching data involves determining whether a value (referred to as the search key ) is pres-
ent in the data and, if so, finding its location. Two popular search algorithms are the sim-
ple linear search and the faster but more complex binary search. Sorting places data in
ascending or descending order, 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 19.1 summarizes the searching and sorting
algorithms discussed in the examples and exercises of this topic.

Software Engineering Observation 19.1
In apps that require searching and sorting, use the pre-defined capabilities of the Java
Collections API (Chapter 16). The techniques presented in this chapter are provided to
introduce students to the concepts behind searching and sorting algorithms—upper-level
computer science courses typically discuss such algorithms in detail.

Chapter Algorithm Location

Searching Algorithms:
16

binarySearch method of class
Collections

Fig. 16.12

19 Linear search

Binary search
Recursive linear search
Recursive binary search

Section 19.2
Section 19.4
Exercise 19.8
Exercise 19.9

Fig. 19.1 | Searching and sorting algorithms covered in this text. (Part 1 of 2.)