Searching, Sorting, and Timing

Agenda

  1. Timing
  2. Prelude: Timing list indexing
  3. Linear search
  4. Binary search
  5. Insertion sort

1. Timing

2. Prelude: Timing list indexing

Observation: accessing an element in a list by index takes a constant amount of time, regardless of position.

How? A Python list uses an array as its underlying data storage mechanism. To access an element in an array, the interpreter:

  1. Computes an offset into the array by multiplying the element's index by the size of each array entry (which are uniformly sized, since they are merely references to the actual elements)
  2. Adds the offset to the base address of the array

Task: to locate an element with a given value in a list (array).

Task: to locate an element with a given value in a list (array) whose contents are sorted in ascending order.

5. Insertion sort

Task: to sort the values in a given list (array) in ascending order.