A Visual Introduction to Basic Sorting Techniques: Bubble, Selection, and Insertion Sort

Table of Contents

1. What is Sorting?
2. Bubble Sort
   • Intuition
   • Step-by-Step Example
   • Pseudocode
   • Complexity Analysis
   • Pros and Cons
3. Selection Sort
   • Intuition
   • Step-by-Step Example
   • Pseudocode
   • Complexity Analysis
   • Pros and Cons
4. Insertion Sort
   • Intuition
   • Step-by-Step Example
   • Pseudocode
   • Complexity Analysis
   • Pros and Cons
5. Comparison of Bubble, Selection, and Insertion Sort
6. When to Use Each Algorithm
7. Conclusion
8. References

What is Sorting?

At its core, sorting is the process of arranging elements in a specific order (e.g., numerical, alphabetical) to make data easier to search, analyze, or interpret. Common orders include:

• Ascending: Smallest to largest (e.g., [1, 2, 3]).
• Descending: Largest to smallest (e.g., [3, 2, 1]).

Key Terms:

• In-Place Sorting: Uses constant extra memory (no additional arrays). All three algorithms discussed here are in-place.
• Stability: A stable sort preserves the relative order of equal elements. For example, if sorting [(2, "apple"), (1, "banana"), (2, "cherry")] by the first value, a stable sort ensures (2, "apple") comes before (2, "cherry").
• Time Complexity: Measures how runtime scales with input size (e.g., O(n²) for “quadratic” algorithms).

Bubble Sort

Intuition

Bubble Sort gets its name because larger elements “bubble” to the end of the array with each pass, like air bubbles rising in water. It repeatedly steps through the list, compares adjacent elements, and swaps them if they’re in the wrong order.

Step-by-Step Example

Let’s sort the array [5, 3, 8, 4, 2] in ascending order using Bubble Sort.

Pass 1:

• Compare 5 and 3: 5 > 3 → swap → [3, 5, 8, 4, 2]
• Compare 5 and 8: 5 < 8 → no swap → [3, 5, 8, 4, 2]
• Compare 8 and 4: 8 > 4 → swap → [3, 5, 4, 8, 2]
• Compare 8 and 2: 8 > 2 → swap → [3, 5, 4, 2, 8]
• Result: Largest element (8) is now at the end.

Pass 2:

• Compare 3 and 5: No swap → [3, 5, 4, 2, 8]
• Compare 5 and 4: Swap → [3, 4, 5, 2, 8]
• Compare 5 and 2: Swap → [3, 4, 2, 5, 8]
• Result: Second-largest element (5) is in place.

Pass 3:

• Compare 3 and 4: No swap → [3, 4, 2, 5, 8]
• Compare 4 and 2: Swap → [3, 2, 4, 5, 8]
• Result: Third-largest element (4) is in place.

Pass 4:

• Compare 3 and 2: Swap → [2, 3, 4, 5, 8]
• Result: Array is sorted!

Optimized Bubble Sort

A naive Bubble Sort runs n-1 passes even if the array becomes sorted early. We can optimize it by adding a swapped flag: if no swaps occur in a pass, the array is sorted, and we exit early.

Pseudocode

function bubbleSort(arr):
    n = length(arr)
    for i from 0 to n-1:
        swapped = false
        # Last i elements are already sorted
        for j from 0 to n-i-2:
            if arr[j] > arr[j+1]:
                swap arr[j] and arr[j+1]
                swapped = true
        # If no swaps, array is sorted
        if not swapped:
            break
    return arr

Complexity Analysis

• Time Complexity:
  • Best Case: O(n) (array is already sorted; optimized with swapped flag).
  • Average/Worst Case: O(n²) (reverse-sorted array requires maximum swaps).
• Space Complexity: O(1) (in-place sorting).
• Stability: Stable (equal elements are not swapped, preserving order).

Pros and Cons

• Pros: Simple to implement; works well for very small or nearly sorted datasets.
• Cons: Extremely inefficient for large datasets (O(n²) complexity); rarely used in practice.

Selection Sort

Intuition

Selection Sort works by repeatedly finding the smallest (or largest) element from the unsorted portion and swapping it with the first unsorted element. Unlike Bubble Sort, it minimizes the number of swaps.

Step-by-Step Example

Sort [5, 3, 8, 4, 2] in ascending order with Selection Sort.

Pass 1:

• Find the smallest element in [5, 3, 8, 4, 2] → 2 (index 4).
• Swap with the first unsorted element (index 0: 5) → [2, 3, 8, 4, 5].

Pass 2:

• Find the smallest element in the remaining unsorted portion [3, 8, 4, 5] → 3 (index 1, already in place).
• No swap → [2, 3, 8, 4, 5].

Pass 3:

• Find the smallest element in [8, 4, 5] → 4 (index 3).
• Swap with index 2 (8) → [2, 3, 4, 8, 5].

Pass 4:

• Find the smallest element in [8, 5] → 5 (index 4).
• Swap with index 3 (8) → [2, 3, 4, 5, 8].
• Result: Array is sorted!

Pseudocode

function selectionSort(arr):
    n = length(arr)
    for i from 0 to n-2:
        # Find index of minimum element in unsorted portion
        min_index = i
        for j from i+1 to n-1:
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap min element with first unsorted element
        swap arr[i] and arr[min_index]
    return arr

Complexity Analysis

• Time Complexity: O(n²) for all cases (must scan the unsorted portion n-1 times, regardless of input order).
• Space Complexity: O(1) (in-place sorting).
• Stability: Unstable (swapping can disrupt the order of equal elements).
  Example: Sorting [2a, 2b, 1] (where 2a and 2b are equal) swaps 1 with 2a, resulting in [1, 2b, 2a]—breaking stability.

Pros and Cons

• Pros: Minimal swaps (only n-1 swaps total); simple to implement.
• Cons: Poor performance for large datasets (O(n²) complexity); unstable.

Insertion Sort

Intuition

Insertion Sort builds the final sorted array one element at a time by inserting each element into its correct position within the sorted portion. Think of it like sorting a hand of playing cards: you pick a card and insert it where it belongs relative to the cards already sorted.

Step-by-Step Example

Sort [5, 3, 8, 4, 2] in ascending order with Insertion Sort.

Step 1: Start with the first element as the sorted portion → [5].

Step 2: Insert 3 into the sorted portion:

• Compare 3 with 5: 3 < 5 → shift 5 right → insert 3 at index 0 → [3, 5].

Step 3: Insert 8 into the sorted portion:

• 8 > 5 → no shift needed → insert at index 2 → [3, 5, 8].

Step 4: Insert 4 into the sorted portion:

• Compare 4 with 8: 4 < 8 → shift 8 right → [3, 5, _, 8].
• Compare 4 with 5: 4 < 5 → shift 5 right → [3, _, 5, 8].
• Insert 4 at index 2 → [3, 4, 5, 8].

Step 5: Insert 2 into the sorted portion:

• Compare 2 with 8 → shift right → [3, 4, 5, _, 8].
• Compare 2 with 5 → shift right → [3, 4, _, 5, 8].
• Compare 2 with 4 → shift right → [3, _, 4, 5, 8].
• Compare 2 with 3 → shift right → [_, 3, 4, 5, 8].
• Insert 2 at index 0 → [2, 3, 4, 5, 8].
• Result: Array is sorted!

Pseudocode

function insertionSort(arr):
    n = length(arr)
    for i from 1 to n-1:
        key = arr[i]  # Element to insert
        j = i - 1     # Last index of sorted portion
        # Shift elements of sorted portion > key to the right
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j = j - 1
        arr[j+1] = key  # Insert key in correct position
    return arr

Complexity Analysis

• Time Complexity:
  • Best Case: O(n) (array is already sorted; no shifts needed).
  • Average/Worst Case: O(n²) (reverse-sorted array requires maximum shifts).
• Space Complexity: O(1) (in-place sorting).
• Stability: Stable (equal elements are shifted right but not swapped, preserving order).

Pros and Cons

• Pros: Efficient for small or nearly sorted datasets (O(n) best case); simple to implement; stable.
• Cons: Inefficient for large datasets (O(n²) complexity).

Comparison of the Three Algorithms

When to Use Each Algorithm

• Bubble Sort: Only for educational purposes or toy projects. Avoid in production.
• Selection Sort: When memory writes are costly (minimizes swaps) or for small datasets.
• Insertion Sort: For small datasets, nearly sorted data (e.g., updating a sorted list with new elements), or as a subroutine in advanced algorithms (e.g., Timsort, used in Python’s sorted()).

Conclusion

Bubble, Selection, and Insertion Sort are foundational sorting algorithms with O(n²) time complexity, making them suitable only for small or specialized datasets. While they’re rarely used in production for large-scale applications, understanding their mechanics is critical for mastering more advanced algorithms like Merge Sort or QuickSort.

• Bubble Sort is the simplest but most inefficient.
• Selection Sort minimizes swaps but is unstable.
• Insertion Sort shines with nearly sorted data and is stable.

By grasping these basics, you’ll build a stronger intuition for how sorting works—and be better prepared to tackle more complex algorithms.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• Wikipedia. (2023). Bubble Sort, Selection Sort, Insertion Sort.
• GeeksforGeeks. (2023). Sorting Algorithms.