Bubble Sort

Notes

Bubble sort is one way to sort an array of numbers. Adjacent values are swapped until the array is completely sorted. This algorithm gets its name from the way values eventually "bubble" up to their proper position in the sorted array.

While stepping through the data, if two adjacent values are not in sorted order, then swap them. After a full scan of the array, repeat from step 1 if any changes have been made.

The algorithm can be used to sort a list in either ascending or descending order.

Let's sort the elements of this array in ascending order.

During our first pass through the array, we've swapped (8,6), (8,4), and (8,2). The value 8 has "bubbled" up to its correct position.

During our second pass, we've swapped (6,4) and (6,2). The value 6 has "bubbled" up to its correct position.

During our third pass, we've swapped (4,2). The value 4 has "bubbled" up to its correct position.

On this final pass through the list no swaps were made, signalling that the array has been completely sorted.

And this is how you can implement bubble sort in C to sort an array in ascending order.

What change would you make to this pseudocode if you wanted to sort a list in descending order instead?

Bubble sort is O(n2) in the worst case (numbers start out in descending order, as in the example we just saw) because we must take n steps on each of n iterations through the numbers. The largest number bubbles up to its correct place in the first iteration, the second largest in the second iteration, and so on.

Bubble sort is Ω(n) in the best case, which occurs when the list is already sorted. There will be no swaps on the first pass through the list, so the algorithm will have completed after only n comparisons.

What would the best case runtime of bubble sort be if we didn't optimize by keeping track of the number of swaps that were made?

n2

As you can see, O(n2) is far from efficient. Maybe we can do better with other sorting algorithms?

Here's a comparison of the runtimes of bubble sort to the runtimes of other sorting algorithms covered in CS50.

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

(Bubble) Sort the Array

Prerequisites:

Use bubble sort to sort the array.

jharvard@run.cs50.net (~): ./a.out
4 15 16 50 8 23 42 108
4 8 15 16 23 42 50 108

Try out some pseudocode here!
#include <stdio.h>

#define SIZE 8

void sort(int array[], int size)
{
    // TODO: sort array using bubble sort
}

int main(void)
{
    int numbers[SIZE] = { 4, 15, 16, 50, 8, 23, 42, 108 };
    for (int i = 0; i < SIZE; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
    sort(numbers, SIZE);
    for (int i = 0; i < SIZE; i++)
    {
        printf("%i ", numbers[i]);
    }
    printf("\n");
}

Videos

study50 video thumbnail

Wednesday, Week 3

An introduction to sorting algorithms
study50 video thumbnail

Jackson on Bubble Sort

Jackson gives a general overview