Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 771

Chapter 13

Searching and Sorting

Introduction

13.1 Searching and Sorting in
the Java Class Libraries

When you are dealing with large amounts of data, you'll often want to
search the data for particular values. For example, you might want to
search the Internet for a web page that contains a certain keyword, or
you might want to search a phone book for a person's phone number.

Binary Search

Sorting

Shuffling

Custom Ordering with
Comparators

It's also useful to be able to rearrange a collection of data into sorted
order. For example, you might want to sort a list of students' course
grade data by name, student ID, or grade.

13.2 Program Complexity

Empirical Analysis

Complexity Classes

13.3 Implementing Searching
and Sorting Algorithms

In this chapter we'll look at ways to use Java's class libraries to search and
sort data.We'll practice implementing some searching and sorting algo-
rithms and talk more generally about how to observe and analyze the
runtimes of algorithms.

Sequential Search

Binary Search

Recursive Binary Search

Searching Objects

Selection Sort

13.4 Case Study: Implementing
Merge Sort

Splitting and Merging Arrays

Recursive Merge Sort

Complete Program

774