Sorting and SearchingLesson 1

Bubble Sort and Selection Sort

Two simple O(n²) sorting algorithms. Bubble sort repeatedly swaps adjacent elements. Selection sort finds the minimum and places it.

What Is It?

Bubble Sort and Selection Sort are the two simplest sorting algorithms. Both run in O(n²) time in the worst case.

Bubble Sort compares pairs of adjacent items and swaps them if they are in the wrong order. Repeat until nothing needs swapping. The largest items "bubble" to the end one by one.

Selection Sort finds the smallest item in the unsorted part and moves it to the front. Repeat. After each pass, one more item is locked into its correct position at the beginning.

Neither is used in production for large datasets, but understanding them builds the foundation for faster algorithms.

Analogy

Bubble Sort: A teacher walks along a line of students sorted by height. She compares each pair standing next to each other. If the taller student is on the left, they swap. She walks the entire line, then starts over. After the first walk, the tallest student has "bubbled" to the far right. After the second walk, the second tallest is in place. She stops when she does a full walk with zero swaps.

Selection Sort: You have a pile of unsorted playing cards on the table. Scan all the cards, find the smallest one, put it at the far left. Scan the remaining cards, find the next smallest, put it second from left. Repeat until the pile is empty.

Try It Yourself

How It Works

Bubble Sort

  1. Walk through the array from left to right.
  2. Compare each pair of neighboring elements.
  3. If they are out of order, swap them.
  4. After one full walk, the largest element is at the end.
  5. Repeat for the rest of the array.
  6. Stop early if a full walk happens with no swaps — the array is already sorted.
pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr):
    n = length(arr)
​
    for i from 0 to n - 2:              // at most n-1 passes
        swapped = false
​
        for j from 0 to n - 2 - i:      // last i elements are already sorted
            if arr[j] > arr[j + 1]:
                swap(arr[j], arr[j + 1])
                swapped = true
​
        if not swapped:                  // nothing swapped = sorted, stop early
            break

Step-by-Step Trace on [5, 3, 8, 1, 2]:

Bubble Sort Trace— Sorting [5, 3, 8, 1, 2] — largest element bubbles to the end each pass
1 / 5
Initial
5
3
8
1
2
[0]
[1]
[2]
[3]
[4]

Selection Sort

  1. Find the smallest element in the entire unsorted part.
  2. Swap it into the first unsorted position.
  3. That position is now sorted. Move on to the next.
  4. Repeat until done.
pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
function selectionSort(arr):
    n = length(arr)
​
    for i from 0 to n - 2:
        minIndex = i
​
        for j from i + 1 to n - 1:
            if arr[j] < arr[minIndex]:
                minIndex = j
​
        if minIndex != i:
            swap(arr[i], arr[minIndex])

Step-by-Step Trace on [5, 3, 8, 1, 2]:

Selection Sort Trace— Sorting [5, 3, 8, 1, 2] — find minimum, place it at the front each pass
1 / 5
Initial
5
3
8
1
2
[0]
[1]
[2]
[3]
[4]

How They Compare

Bubble Sort

  • Worst/avg: O(n²), Best: O(n)
  • Space: O(1) | Stable: Yes
  • Swaps: O(n²) worst
  • Adaptive: Yes (early exit)

swap adjacent pairs

Selection Sort

  • All cases: O(n²)
  • Space: O(1) | Stable: No
  • Swaps: O(n) always
  • Adaptive: No

select minimum each pass

Key differences:

  • Bubble Sort can stop early if the array becomes sorted during a pass. Selection Sort always does all its comparisons no matter what.
  • Selection Sort does at most n-1 swaps total — one per pass. Bubble Sort can do many more swaps.
  • Bubble Sort is stable — equal elements stay in their original order. Selection Sort is not stable — swapping can move equal elements past each other.

Examples

Bubble Sort on Nearly Sorted Data

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
Input: [1, 2, 4, 3, 5]
​
Pass 0:
  1 > 2? No. 2 > 4? No. 4 > 3? Yes, swap. -> [1, 2, 3, 4, 5]
  3 > 5? Wait, we have 4 > 5? No.
  (swapped = true)
​
Pass 1:
  1 > 2? No. 2 > 3? No. 3 > 4? No.
  (swapped = false -> EARLY EXIT)
​
Only 2 passes and 1 swap!

Bubble Sort shines when data is nearly sorted.

Why Selection Sort Does Fewer Swaps

Selection Sort finds the minimum first, then does a single swap per pass. Bubble Sort might swap many times per pass. If swapping is expensive (like writing to a slow disk), Selection Sort is better because it minimizes writes.

Common Mistakes

  1. Off-by-one in Bubble Sort's inner loop. The inner loop goes to n - 2 - i, not n - 1. Each pass, the last i elements are already sorted — no need to compare them.
  1. Forgetting the early exit in Bubble Sort. Without it, the algorithm always runs O(n²) even on already-sorted data. The swapped flag is a simple improvement that matters.
  1. Thinking Selection Sort is stable. It is not. When you swap the minimum to position i, you may move equal elements past each other.
  1. Confusing which end grows. In Bubble Sort, the sorted part grows from the RIGHT. In Selection Sort, it grows from the LEFT.

Best Practices

  • Always include the early exit flag in Bubble Sort. It turns best-case performance from O(n²) to O(n) with almost no extra code.
  • Use Selection Sort when you need to minimize swaps. It guarantees at most n-1 swaps regardless of input.
  • Trace through a small array by hand before coding. This catches off-by-one errors immediately.
  • Know both for interviews. They are simple to explain and demonstrate understanding of sorting fundamentals.
Writing Recursive FunctionsInsertion Sort