Algorithms: Searching, Sorting and Big O

Same problem, different speeds

Every program you have written so far was judged on one question: does it work? From this week there is a second question that matters just as much in the real world: how fast does it work, and how does that change when the input grows? Two correct programs can differ by a factor of a million on the same laptop. This week gives you a way to see that difference before you run anything.

The programs on this page are from CS50’s Week 3 lecture, plus a few written for this course where CS50 shows only pseudocode (binary search and the three sorts in C). Each orange box is a program we open in VS Code; the full, copyable source follows each box.

Linear search

Remember the lockers from the lecture: an array of seven numbers behind seven closed doors. The computer cannot see all of them at once the way you can; it opens one door at a time. The simplest strategy is to start at the left and open doors until you find what you are looking for or run out of doors.

For i from 0 to n-1
    If 50 is behind doors[i]
        Return true
Return false

Notice where the Return false sits: after the loop, not inside an else. If you put it inside the loop, the program gives up after the very first door that is not 50. This is the most common mistake in the first search students write, and the pseudocode makes it visible before any C is typed.

// Implements linear search for integers

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // An array of integers
    int numbers[] = {20, 500, 10, 5, 100, 1, 50};

    // Search for number
    int n = get_int("Number: ");
    for (int i = 0; i < 7; i++)
    {
        if (numbers[i] == n)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

// Implements linear search for strings

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // An array of strings
    string strings[] = {"battleship", "boot", "cannon", "iron", "thimble", "top hat"};

    // Search for string
    string s = get_string("String: ");
    for (int i = 0; i < 6; i++)
    {
        if (strcmp(strings[i], s) == 0)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

Binary search

If the doors are sorted, you can do much better. Open the middle door. If the number you want is smaller, everything to the right is useless; if larger, everything to the left is. Either way you have thrown away half the problem with one comparison.

If no doors left
    Return false
If 50 is behind doors[middle]
    Return true
Else if 50 < doors[middle]
    Search doors[0] through doors[middle - 1]
Else if 50 > doors[middle]
    Search doors[middle + 1] through doors[n - 1]

// Implements binary search for integers (the array must be sorted)

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // A sorted array of integers
    int numbers[] = {1, 5, 10, 20, 50, 100, 500};
    int size = 7;

    // Search for number
    int n = get_int("Number: ");
    int low = 0;
    int high = size - 1;
    int steps = 0;
    while (low <= high)
    {
        int middle = (low + high) / 2;
        steps++;
        printf("step %i: looking at index %i (%i)\n", steps, middle, numbers[middle]);
        if (numbers[middle] == n)
        {
            printf("Found after %i step(s)\n", steps);
            return 0;
        }
        else if (numbers[middle] < n)
        {
            low = middle + 1;
        }
        else
        {
            high = middle - 1;
        }
    }
    printf("Not found after %i step(s)\n", steps);
    return 1;
}

Running time

We need a way to talk about speed that does not depend on whose laptop is faster. Computer scientists count steps as a function of the input size n and keep only the shape of the curve, not the constants. That notation is Big O, and it describes the upper bound, the worst case.

Three symbols, one idea each. O is the worst case: linear search is O(n) because the number might be behind the last door. Ω (omega) is the best case: linear search is Ω(1) because the number might be behind the first door. When the best and worst case have the same shape, we write Θ (theta): selection sort is Θ(n²), it does the same work whether the list is already sorted or not.

Why do constants not matter? Because for large n they are drowned out. An algorithm that takes 3n steps and one that takes n steps are both O(n); an algorithm that takes n²/100 steps still loses to one that takes 1000·n steps once n passes 100 000. Big O is a statement about scaling, and scaling is what decides whether a program survives contact with real data.

A phone book and a struct

Suppose you want to search a phone book, names and numbers, by name.

// Implements a phone book without structs

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // Arrays of strings
    string names[] = {"Yuliia", "David", "John"};
    string numbers[] = {"+1-617-495-1000", "+1-617-495-1000", "+1-949-468-2750"};

    // Search for name
    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
        if (strcmp(names[i], name) == 0)
        {
            printf("Found %s\n", numbers[i]);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

// Implements a phone book with structs

#include <cs50.h>
#include <stdio.h>
#include <string.h>

typedef struct
{
    string name;
    string number;
} person;

int main(void)
{
    person people[3];

    people[0].name = "Yuliia";
    people[0].number = "+1-617-495-1000";

    people[1].name = "David";
    people[1].number = "+1-617-495-1000";

    people[2].name = "John";
    people[2].number = "+1-949-468-2750";

    // Search for name
    string name = get_string("Name: ");
    for (int i = 0; i < 3; i++)
    {
        if (strcmp(people[i].name, name) == 0)
        {
            printf("Found %s\n", people[i].number);
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

A struct is the first time you design your own type rather than using C’s. It is a small moment with a long shadow: a struct in C is a row in a database table, an object in JavaScript, a class in Python. Every program that manages real information is built from them.

Sorting

Sorting is the price of binary search, and it turns out to be one of the richest problems in computer science. Three algorithms, from the most obvious to the one that actually gets used.

Selection sort

Look through the whole list for the smallest number and swap it to the front. Then look through what is left for the next smallest, and so on. On the first pass you look at n numbers, on the second n − 1, then n − 2, down to 1. That sum is n(n − 1)/2, and the shape of that is n²: selection sort is Θ(n²).

// Selection sort: find the smallest of what is left, swap it to the front

#include <stdio.h>

void print_array(int n, int a[]);

int main(void)
{
    int numbers[] = {6, 3, 8, 5, 2, 7, 4, 1};
    int n = 8;
    print_array(n, numbers);

    for (int i = 0; i < n - 1; i++)
    {
        // Find the smallest element from i to the end
        int smallest = i;
        for (int j = i + 1; j < n; j++)
        {
            if (numbers[j] < numbers[smallest])
            {
                smallest = j;
            }
        }

        // Swap it into position i
        int tmp = numbers[i];
        numbers[i] = numbers[smallest];
        numbers[smallest] = tmp;

        print_array(n, numbers);
    }
}

void print_array(int n, int a[])
{
    for (int i = 0; i < n; i++)
    {
        printf("%i ", a[i]);
    }
    printf("\n");
}

Bubble sort

Walk along the list comparing each pair of neighbors and swap them if they are in the wrong order. After one pass the largest number has bubbled to the end; after two passes the two largest are in place. In the worst case that is also n² steps, but bubble sort has one trick selection sort lacks: if a whole pass makes no swap, the list is sorted and you can stop. On an already sorted list bubble sort finishes in one pass, so it is O(n²) but Ω(n).

// Bubble sort: compare neighbors, swap if out of order, stop early if a pass makes no swap

#include <stdbool.h>
#include <stdio.h>

void print_array(int n, int a[]);

int main(void)
{
    int numbers[] = {6, 3, 8, 5, 2, 7, 4, 1};
    int n = 8;
    print_array(n, numbers);

    for (int pass = 0; pass < n - 1; pass++)
    {
        bool swapped = false;
        for (int j = 0; j < n - 1 - pass; j++)
        {
            if (numbers[j] > numbers[j + 1])
            {
                int tmp = numbers[j];
                numbers[j] = numbers[j + 1];
                numbers[j + 1] = tmp;
                swapped = true;
            }
        }
        print_array(n, numbers);
        if (!swapped)
        {
            break;   // already sorted: nothing moved in this pass
        }
    }
}

void print_array(int n, int a[])
{
    for (int i = 0; i < n; i++)
    {
        printf("%i ", a[i]);
    }
    printf("\n");
}

Merge sort

Both sorts so far are quadratic. Doubling the input quadruples the time; a million numbers take a trillion steps. Merge sort breaks the pattern with one idea: sorting a list is easy if you already have two sorted halves, because merging two sorted lists is a single pass. So sort the left half, sort the right half, merge. How do you sort the halves? The same way. The recursion stops at lists of one element, which are sorted by definition.

If only one number
    Quit
Else
    Sort left half of numbers
    Sort right half of numbers
    Merge sorted halves

Each level of halving costs n steps to merge, and there are log₂ n levels, so merge sort is Θ(n log n). For a million numbers that is twenty million steps instead of a trillion: the difference between a blink and twelve days. The cost is memory: merging needs a second array to merge into.

// Merge sort: sort the left half, sort the right half, merge the two sorted halves

#include <stdio.h>

void merge_sort(int a[], int left, int right, int depth);
void merge(int a[], int left, int middle, int right);
void print_range(int a[], int left, int right, int depth);

int main(void)
{
    int numbers[] = {6, 3, 8, 5, 2, 7, 4, 1};
    int n = 8;
    merge_sort(numbers, 0, n - 1, 0);
}

void merge_sort(int a[], int left, int right, int depth)
{
    // Base case: one element is already sorted
    if (left >= right)
    {
        return;
    }
    int middle = (left + right) / 2;
    merge_sort(a, left, middle, depth + 1);
    merge_sort(a, middle + 1, right, depth + 1);
    merge(a, left, middle, right);
    print_range(a, left, right, depth);
}

void merge(int a[], int left, int middle, int right)
{
    int tmp[right - left + 1];
    int i = left, j = middle + 1, k = 0;
    while (i <= middle && j <= right)
    {
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    }
    while (i <= middle)
    {
        tmp[k++] = a[i++];
    }
    while (j <= right)
    {
        tmp[k++] = a[j++];
    }
    for (k = 0; k < right - left + 1; k++)
    {
        a[left + k] = tmp[k];
    }
}

void print_range(int a[], int left, int right, int depth)
{
    for (int d = 0; d < depth; d++)
    {
        printf("  ");
    }
    printf("merged [%i..%i]: ", left, right);
    for (int i = left; i <= right; i++)
    {
        printf("%i ", a[i]);
    }
    printf("\n");
}

Recursion

Merge sort was defined in terms of itself, and that deserves a closer look. A function that calls itself is recursive. It sounds circular, and it would be, except that every recursive function has a base case, an input so small that the answer is known without any further calls. Everything else is reduced one step towards that base case.

// Draws a pyramid using iteration

#include <cs50.h>
#include <stdio.h>

void draw(int n);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int n)
{
    // Draw pyramid of height n
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            printf("#");
        }
        printf("\n");
    }
}

// Draws a pyramid using recursion

#include <cs50.h>
#include <stdio.h>

void draw(int n);

int main(void)
{
    // Get height of pyramid
    int height = get_int("Height: ");

    // Draw pyramid
    draw(height);
}

void draw(int n)
{
    // If nothing to draw
    if (n <= 0)
    {
        return;
    }

    // Draw pyramid of height n - 1
    draw(n - 1);

    // Draw one more row of width n
    for (int i = 0; i < n; i++)
    {
        printf("#");
    }
    printf("\n");
}

Recursion is not a trick for pyramids. It is the natural way to express anything that is defined in terms of a smaller version of itself: file systems inside folders inside folders, the structure of a sentence, a chess game, and, in two weeks, the data structures that make databases fast.

Summary

• Linear search looks at every element: O(n). Binary search halves the range each step: O(log n), but the array must be sorted.
• Big O describes how steps grow with n, ignoring constants. O is the worst case, Ω the best, Θ when they match.
• strcmp(a, b) == 0 is how you ask whether two strings are the same text; == compares something else.
• A struct bundles related data into a type of your own; . reaches inside it.
• Selection sort and bubble sort are Θ(n²) and O(n²) respectively; bubble sort can stop early. Merge sort is Θ(n log n) and uses recursion.
• A recursive function calls itself on a smaller input and stops at a base case.
• The lab, Lab 4: Search and Sort, has you write both searches with a comparison counter, both quadratic sorts chosen from the command line, and a recursive pyramid and factorial.

Tags:linear searchbinary searchselection sortbubble sortmerge sortBig Orecursionstruct