Sorting and Searching

In this chapter, we will be looking at sorting and searching, two important operations on a list. These operations have been exhaustively studied by computer scientists over the year, and they have some interesting characteristics. So, although we study them partially because they are useful, we also will study them because they are educational.

Simple Sorting

data = [5, 4, 9, 7, 3, 6]

in_order = sorted(data)

print(in_order)

One of the most fundamental operations to perform on a list is to sort the elements. For a list of numbers like the in the following example, this puts them into ascending order. You can sort elements of any type if they support ordering comparisons; this includes strings and floats, but does not include lists or dataclasses (at least not normally.) Sorting is so useful that Python provides a built-in sorted function to make it easy to sort a given list. Before we talk about how the sorted function works, let’s study a different problem: searching.

def linear_search(target: int, data: list[int]) -> int:
    for number in data:
        print(number, target, data)
        if target == number:
            return target
    return None

print(linear_search(3, [1, 2, 9, 5, 7, 8, 3]))

Previously, we learned how the find pattern would let us determine if an element was in a list. That pattern had us use a for loop to walk through each number in the list and check if it was the target. If we find the target, we can immediately return. But in the worst possible case, the element could be at the very end or not even in the list. In that case, we would have to go check every single element. If there were a million elements, we would potentially need to do a million checks! This is known as linear search, or sometimes iterative search, and it is easy to understand but can be unfortunately slow. Fortunately, there is a faster way to search that we can use if we have a sorted list.

def binary_search(target: int, data: list[int]) -> int:
    midpoint = len(data)//2
    while target != data[midpoint]:
        print(midpoint, target, data)
        if target < data[midpoint]:
            data = data[:midpoint]
        else:
            data = data[midpoint+1:]
        midpoint = len(data)//2
        if not data:
            return None
    return target

print(binary_search(3, [1, 2, 5, 7, 8, 9]))

Shown here is the classic binary search algorithm that can find an element in a list more quickly than a linear search if the list is already sorted. The algorithm works by repeatedly dividing the list in half to find a target.

First, the function calculates the midpoint of the list using the len function. If the target is equal to the value at the middle index of the list, then we stop looping and return the target. However, if not, then instead we check whether the target is less or greater than the value at the midpoint. If less than, we trim data to be only the first half of the list. If it is greater than, we trim data to be the second half of the list, skipping over the midpoint element. Then, we recalculate the new midpoint of this smaller, half-sized list. If we run out of list, then we stop the function and return None. Otherwise, we loop back and check whether we have found our target. Try experimenting with different values for target and data to see the effect on the iteration.

Binary Search Time Complexity

This binary search algorithm, which repeatedly divides a search space in half, is one of the most remarkable algorithms in computer science. You will see that its approach is much faster than a simple iterative search. The time complexity of binary search is said to be “logarithmic on the size of the input”. Logarithmic refers to how we repeatedly divide the input into two. The logarithm of a number is the number of times that number can be divided by a given base until you reach 1. Shown here are some examples of base-2 logarithm (log₂) for different sized lists. Logarithmic relationships are significantly better than linear relationships (doing 20 checks instead of a million!), although they do not beat constant time. Still, being faster than linear is a wonderful accomplishment and we should be proud of this little algorithm. Keep in mind, however, that this faster search is only possible because we knew the list was sorted.

Some Sorting Algorithms

So, since sorting is so useful, we need to understand how it works. In the rest of this section, we will quickly go over the code of two different sorting algorithms just to give you an idea of what is possible. This may not be sufficient to help you learn how the algorithms work, but we will provide some links at the end of this lesson to good websites that have helpful visualizations of these sorting algorithms in more depth.

Bubble Sort

def bubble_sort(data: list[int]) -> list[int]:
    length = len(data)
    # Iterate through each list index
    for i in range(length):
        # Iterate through all remaining indexes at this point
        for j in range(length - i - 1):
            # If right element is bigger than left element
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
    return data

print(bubble_sort([5, 4, 9, 7, 3, 6]))

One of the simplest classic sorting algorithms is bubble sort, which operates by repeatedly swapping pairs of adjacent elements until all elements are in the right order. Note the most-indented line of the function, which does a swap of two adjacent list elements, but only if the first element is greater than the second element. That conditional swap is inside of a nested for loop. The outer loop is guaranteed to run a linear number of times, once for each element of the list. Every inner loop requires an additional linear number of steps. Although we do one fewer step each time, we are still going to have to do a linear number in total. Nesting a linear loop inside of a linear loop actually causes quadratic growth, which is very slow indeed. Bubble sort is fairly easy to code but does not work very well in practice.

Insertion Sort

def insertion_sort(data: list[int]) -> list[int]:
    # Iterate through each list index
    for i, current in enumerate(data):
        j = i - 1
        # Go back through the list to find next smallest
        while j >= 0 and data[j] > current:
            # Swap element backwards
            data[j+1] = data[j]
            j -= 1
        # Swap that element into the target index
        data[j+1] = current
    return data

print(insertion_sort([5, 4, 9, 7, 3, 6]))

An improvement to bubble sort is insertion sort, which also works by swapping adjacent elements. However, the difference is in the inner loop, which no longer iterates through all of the elements. Instead, the inner loop is a while loop that swaps the current element backwards through the list until it encounters a smaller element. At any given point in time, the elements prior to the current element are in sorted order. We are merely dragging elements from the back of the list to the front and placing them in the appropriate spot. In the best case, the list is already sorted, and we only must walk through to confirm this. But in the worst case, we may be dragging each element all the way from the back to our current position as we walk through the list. This makes insertion sort an even more interesting sorting algorithm because suddenly the runtime depends on more than just the size of the input: the value of the input also affects the time complexity. Still, the fact that sometimes when the sorting algorithm performs poorly, it just means we should find a better one.

Other Sorts

There are a huge number of other sorting algorithms out there, each with their own advantages and disadvantages. We have only looked at two simple ones, bubble sort and insertion sort. If you would like to learn more sorting algorithms, we recommend you check out a website like VisualGo for interactive visualizations. There are many more resources on the web for learning about sorting algorithms. You might go and learn more about other sorting algorithms like selection sort, merge sort, or quick sort.

Summary