Searching and Sorting

About this unit

Searching means finding whether, and where, a value is present in a collection; sorting means arranging values in order. This unit compares linear search, binary search and search by hashing, and studies three simple sorting algorithms: bubble sort, selection sort and insertion sort. For each algorithm you learn the steps, how to dry-run it on a small list, and how the number of comparisons grows with the size of the input.

Key ideas

• Linear search checks elements one by one and works on any list.
• Binary search repeatedly halves a sorted list.
• Hashing computes the position of a key directly, using a hash function.
• A collision occurs when two keys map to the same position.
• Bubble, selection and insertion sort each make a series of passes.
• Best, worst and average cases describe how much work an algorithm does.

How to prepare

Practise dry runs: write the list after each pass of every sorting method, and the low, high and mid values in each step of binary search. Learn the conditions each method needs (binary search needs sorted data). Questions often ask for the list after a given pass or the number of comparisons needed.