Sorting CS Thinking Example 1

Follow the full solution, then compare it with the other examples linked below.

Example 1

medium
Sort the list [5, 2, 8, 1, 9] using bubble sort. Show the first two passes.

Solution

  1. 1
    Step 1: Pass 1 — compare adjacent pairs and swap if needed: (5,2)→swap→[2,5,8,1,9], (5,8)→ok, (8,1)→swap→[2,5,1,8,9], (8,9)→ok. After pass 1: [2,5,1,8,9].
  2. 2
    Step 2: Pass 2: (2,5)→ok, (5,1)→swap→[2,1,5,8,9], (5,8)→ok, (8,9)→ok. After pass 2: [2,1,5,8,9].
  3. 3
    Step 3: Continue until no swaps occur. Bubble sort has O(n2)O(n^2) time complexity.

Answer

After pass 1: [2,5,1,8,9]. After pass 2: [2,1,5,8,9]. Final: [1,2,5,8,9].
Bubble sort repeatedly passes through the list, swapping adjacent elements that are in the wrong order. The largest unsorted element 'bubbles' to its correct position each pass.

About Sorting

Rearranging items in a collection into a defined order, such as smallest to largest or alphabetical. Sorting is one of the most studied problems in computer science, with algorithms ranging from simple (bubble sort, O(n2)O(n^2)) to efficient (merge sort, O(nlog⁡n)O(n \log n)).

Learn more about Sorting →

More Sorting Examples

Example 2 hard

Compare bubble sort and merge sort in terms of time complexity. When would you choose one over the o

Example 3 medium

Sort [4, 1, 3] using insertion sort. Show each step.

Example 4 medium

You have a list of exam scores that is already sorted except one new score was added at the end. Wou

← All Sorting Examples Sorting Concept