Searching and sorting algorithms

Learning objectives

Write and trace a linear search of an array or an ArrayList, starting from either end, and of a two-dimensional array row by row, stating the number of comparisons in the best and worst cases

Trace an iterative binary search, explain why the data must already be sorted, and explain why it usually needs far fewer comparisons than a linear search

Trace a selection sort, showing the contents of the array after each pass and naming the element that reaches its final position on that pass

Trace an insertion sort, showing the contents of the array after each pass and explaining how the sorted section at the front grows as larger elements shift to make room

Compare searching and sorting algorithms informally by counting the comparisons or statement executions each one performs on the same data

Use the compareTo method of String inside a search or a sort, and interpret a negative, zero or positive result