Sorting

We now know that sorting can be useful in some algorithms -- for example, if a list is sorted, then binary search can be used to make a search more efficient. But sorting is actually a much more general topic with many applications in the world around us. Watch the following video, which provides an overview of the goal of sorting and compares a few sorting algorithms:

As mentioned by the video, books are a great example of an item that can be sorted. In this class, for simplicity we will primarily focus on sorting integers, but the techniques that we will cover generalize to sorting other types of data as well (for example, strings).

Why sorting?

There are a few reasons why we're focusing on sorting algorithms for the rest of the lessons in this week, including:

  1. Sorting algorithms are all around us in our daily lives.
  2. Sorting algorithms are relatively easy to understand when learning how to analyze the efficiency of algorithms.
  3. There are multiple simple algorithms that take different approaches to sorting lists, which enables us to compare and contrast their techniques and efficiencies. For example, some algorithms (like selection sort and insertion sort) order the numbers in a list by comparing the numbers of the list directly to each other. Other algorithms (like radix sort) don't compare the numbers of the list at all, but rather distribute the numbers to buckets based on the value of the numbers themselves.

Our discussion of sorting algorithms is in part motivated by our desire to learn about how to analyze the efficiency of algorithms. Let's talk more about how to analyze the efficiency of sorting algorithms next.

Comparisons and moves

We learned in an earlier lesson that big-O notation represents an approximate upper bound on the number of operations that a computer program will execute in terms of the input size n. For sorting algorithms specifically, the number of overall operations is dominated by two tasks: (1) comparing elements of the list and (2) moving elements of the list around to different positions. Therefore, we will focus our time analysis on the number of comparisons and moves that a sorting algorithm performs.

For example, this would be considered a comparison between two elements of a list:

if lst[i] < lst[i - 1]:

And the following would be considered a move into one of the positions of the list:

lst[i] = lst[i + 1]

In the next lesson, we will learn the selection sort algorithm, count the number of comparisons and moves it performs, and use those metrics to derive its big-O running time.