Introduction to Algorithms, 2021-2
Week 6: Notes

Some of the topics we discussed today are covered in these sections of Problem Solving with Algorithms:

Here are some more notes:

binary search for a boundary

Suppose that we know that a given array consists of a sequence of values with some property P followed by some sequence of values that do not have that property. Then we can use a binary search to find the boundary point dividing the values with property P from those without it.

For example, suppose that we know that an array contains a sequence of non-decreasing integers. Given a value k, we want to find the index of the first value in the array that is greater than or equal to k. Because the array is non-decreasing, it must contain a sequence of values that are less than k, followed by a sequence of values that are at least k. We want to find the boundary point between these sequences.

# Given an array a of non-decreasing values, find the first one that is >= k.

lo = 0
hi = len(a) - 1

while lo <= hi:
  mid = (lo + hi) // 2
  if a[mid] < k:
    lo = mid + 1
  else:   # a[mid] >= k
    hi = mid - 1

print('The first value that is at least', k, 'is', a[lo])

At every moment as the function runs:

for i < lo: a[i] < k
for lo ≤ i ≤ hi: we don't know whether a[i] is less than or greater than k
for i > hi: a[i] ≥ k

When the while loop finishes, lo and hi have crossed, so lo = hi + 1. A this point there are no unknown elements, and the boundary we are seeking lies between hi and lo. Specifically:

For all i ≤ hi, a[i] < k
For all i ≥ hi + 1, a[i] ≥ k

And so lo = hi + 1 is the index of the first value greater than or equal to k.

As mentioned above, we can use this form of binary search with any property P, not just the property of being less than k. As another example, if we have an array that consists of a sequence of even integers followed by a sequence of odd integers, we can find the first odd integer using this algorithm.

sorting

Sorting is a fundamental task in computer science. Sorting an array means rearranging its elements so that they are in order from left to right.

We will study a variety of sorting algorithms in this class. Most of these algorithms will work on sequences of any ordered data type: integer, real, string and so on.

bubble sort

Our first sorting algorithm is bubble sort. Bubble sort is not terribly efficient, but it is simple to write.

Bubble sort works by making a number of passes over the input. On each pass, it compares pairs of elements: first elements 1 and 2, then elements 2 and 3, and so on. After each comparison, it swaps the elements if they are out of order. Here is an animation of bubble sort in action.

Suppose that an array has N elements. Then the first pass of a bubble sort makes N – 1 comparisons, and always brings the largest element into the last position. So the second pass does not need to go as far: it makes only N – 2 comparisons, and brings the second-largest element into the second-to-last position. And so on. After N – 1 passes, the sort is complete and the array is in order.

Here's an implementation of bubble sort in Python:

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1, 0, -1):   # n - 1 .. 1
        for j in range(i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

What's the running time of bubble sort? Suppose that the input array has N elements. As mentioned above, on the first pass we make (N – 1) comparisons; on the second pass we make (N – 2) comparisons, and so on. The total number of comparisons is

(N – 1) + (N – 2) + … + 2 + 1 = N(N – 1) / 2 = O(N²)

The number of element swaps may also be O(N²), though it will be as low as 0 if the array is already sorted. In any case, the total running time is O(N²) in the best and worst case due to the cost of the comparisons.

selection sort

Our next sorting algorithm is selection sort. In a selection sort, we start by finding the smallest value in the array and exchanging it with the first element. We then find the second smallest value and exchange it with the second element, and so on. Here is an animation of selection sort in action.

Here's an implementation in Python:

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        min_index = i
        min_val = a[i]
        for j in range(i + 1, n):
            if a[j] < min_val:
                min_val = a[j]
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]

We can analyze selection sort's running time similarly to bubble sort. Just as in bubble sort, the total number of comparisons is

(N – 1) + (N – 2) + … + 2 + 1 = N(N – 1) / 2 = O(N²)

and the running time is O(N²) in the best and worst case. However, selection sort will usually outperform bubble sort by as much as a factor of 3. That's because it performs many fewer swaps as it rearranges the data.

insertion sort

Insertion sort is another fundamental sorting algorithm. Insertion sort loops through array elements from left to right. For each element a[i], we first "lift" the element out of the array by saving it in a temporary variable t. We then walk leftward from i; as we go, we find all elements to the left of a[i] that are greater than a[i] and shift them rightward one position. This makes room so that we can insert a[i] to the left of those elements. And now the subarray a[0..i] is in sorted order. After we repeat this for all in turn, the entire array is sorted.

Here is an animation of insertion sort in action.

Here is a Python implementation of insertion sort:

def insertion_sort(a):
    n = len(a)
    for i in range(n):
        t = a[i]
        j = i - 1
        while j >= 0 and a[j] > t:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = t

What is the running time of insertion sort? In the best case, the input array is already sorted. Then no elements are shifted or modified at all and the algorithm runs in time O(n).

The worst case is when the input array is in reverse order. Then to insert each value we must shift elements to its left, so the total number of shifts is 1 + 2 + … + (n – 1) = O(n²). If the input array is ordered randomly, then on average we will shift half of the subarray elements on each iteration. Then the time is still O(n²).