Key Concepts

Review core concepts you need to learn to master this subject

Bubble Sort Big-O Runtime

The Bubble Sort algorithm utilizes two loops: an outer loop to iterate over each element in the input list, and an inner loop to iterate, compare and exchange a pair of values in the list. The inner loop takes (N-1) iterations while the outer loop takes N iterations. Hence, the Big-O runtime for the algorithm is the product of O(N) and O(N-1), which is O(N^2).

Python Swap Function

A Python function that swaps two adjacent values in a list can be written as follows:

Swapping Variables in Bubble Sort

In the Bubble Sort algorithm, the swap function that swaps two elements in a list can be called in a Bubble Sort function to iteratively swap an element with its adjacent neighbor whose value is smaller until all the elements are sorted in ascending order.

Chevron Left Icon
Bubble Sort: Conceptual
Lesson 1 of 2
Chevron Right Icon
  1. 1
    Bubble sort is an introductory sorting algorithm that iterates through a list and compares pairings of adjacent elements. According to the sorting criteria, the algorithm swaps elements to shift …
  2. 2
    As mentioned, the bubble sort algorithm swaps elements if the element on the left is larger than the one on the right. How does this algorithm swap these elements in practice? Let’s say we have …
  3. 3
    Given a moderately unsorted data-set, bubble sort requires multiple passes through the input before producing a sorted list. Each pass through the list will place the next largest value in its prop…
  4. 4
    Bubble sort is an algorithm to sort a list through repeated swaps of adjacent elements. It has a runtime of O(n^2). For nearly sorted lists, bubble sort performs relatively few operations since it…
  1. 1
    The Bubble Sort algorithm works by comparing a pair of neighbor elements and shifting the larger of the two to the right. Bubble Sort completes this by swapping the two elements’ positions if the f…
  2. 2
    Now that we know how to swap items in an array, we need to set up the loops which check whether a swap is necessary. Recall that Bubble Sort compares neighboring items and if they are out of orde…
  3. 3
    As you were writing Bubble Sort, you may have realized that we were doing some unnecessary iterations. Consider the first pass through the outer loop. We’re making n-1 comparisons. nums = [5, 4,…

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo