Introduction to Algorithms: Sorting Techniques (Bubble Sort vs. Insertion Sort)

Introduction to Algorithms: Sorting Techniques (Bubble Sort vs. Insertion Sort)

1. Introduction

In our previous guides, we explored software systems, logic gates, and the basics of Python programming. Now, let us examine how programs organize and manipulate data efficiently.

Imagine walking into a school library where thousands of books are piled in random heaps across the floor. Finding a specific textbook would require checking every single title one by one. However, if the books are sorted alphabetically by title or chronologically by class grade, you can locate the exact volume in seconds.

Computers face this exact challenge when handling student rolls, examination results, and databases. To organize disordered data into ascending or descending sequence, computers execute Sorting Algorithms. Understanding foundational sorting methods—specifically Bubble Sort and Insertion Sort—is a vital milestone in developing computational thinking.

2. Visual Sketchnote: Comparing Sorting Strategies

 ╔══════════════════════════════════════════════════════════════════════════════╗

 ║ SORTING ALGORITHMS SKETCHNOTE ║

 ╚══════════════════════════════════════════════════════════════════════════════╝

  [ BUBBLE SORT: "Sinking & Floating" ]

   • Compares adjacent side-by-side elements

   • Largest values "bubble up" to the right end on each pass

    Pass 1: [ 5 , 2 , 8 , 1 ]

               └───┘

              (5 > 2 ? Yes -> Swap)

             [ 2 , 5 , 8 , 1 ]

                   └───┘

                  (5 > 8 ? No -> Keep)

             [ 2 , 5 , 8 , 1 ]

                       └───┘

                      (8 > 1 ? Yes -> Swap)

             [ 2 , 5 , 1 | 8 ] <── 8 is locked into its final position!

 ────────────────────────────────────────────────────────────────────────────────

  [ INSERTION SORT: "Sorting Playing Cards" ]

   • Builds a sorted sub-list on the left

   • Takes one item at a time and inserts it into its correct left position

    State: [ 2 , 5 | 1 , 8 ] (Left side is sorted, item to insert is 1)

                       │

              1 moves left: (1 < 5 -> shift 5 right)

                            (1 < 2 -> shift 2 right)

              1 inserts at index 0

    Result: [ 1 , 2 , 5 | 8 ]

 ════════════════════════════════════════════════════════════════════════════════

3. How Bubble Sort Works

Bubble Sort is one of the simplest sorting techniques. It systematically traverses an array multiple times, comparing adjacent elements and swapping them if they appear in the wrong order.

Step-by-Step Logic:

 * Start at index 0 and compare the first two adjacent numbers.

 * If the left number is greater than the right number, swap them.

 * Move to the next pair (index 1 and 2) and repeat the comparison.

 * Continue through to the end of the list. By the end of Pass 1, the largest item has migrated ("bubbled up") to the far right.

 * Repeat the process for the remaining unsorted section until a full pass completes with zero swaps.

Operational Characteristics:

 * Best-Case Time Complexity: O(n) (when the list is already completely sorted).

 * Worst/Average-Case Time Complexity: O(n^2).

 * Space Complexity: O(1) (in-place sort; uses no additional memory).

4. How Insertion Sort Works

Insertion Sort mimics the way most people arrange playing cards in their hands. The array is conceptually divided into two parts: a sorted partition on the left and an unsorted partition on the right.

Step-by-Step Logic:

 * Assume the first element (index 0) is already sorted by itself.

 * Pick the first element from the unsorted segment (the "key").

 * Compare the key with elements in the sorted partition from right to left.

 * Shift all elements greater than the key one position to the right to make space.

 * Drop the key into its correct sorted location.

 * Advance to the next unsorted element and repeat until the array is fully arranged.

Operational Characteristics:

 * Best-Case Time Complexity: O(n) (linear scan with no shifts).

 * Worst/Average-Case Time Complexity: O(n^2).

 * Key Advantage: Significantly faster and more efficient on small or nearly sorted datasets than Bubble Sort.

5. Direct Comparison: Bubble Sort vs. Insertion Sort

| Parameter | Bubble Sort | Insertion Sort |

|---|---|---|

| Primary Mechanism | Swapping adjacent pairs repeatedly | Shifting elements to insert the key into place |

| Pass Target | Places the largest item at the end | Places the next item into its correct relative position |

| Number of Swaps | High (swaps repeatedly during passes) | Low (shifts items, writing the key once per pass) |

| Real-World Suitability | Educational conceptualization only | Practical for small arrays and streaming real-time data |

| Memory Overhead | In-place (O(1) auxiliary space) | In-place (O(1) auxiliary space) |

6. Hands-on Lab Activity: Implementing Both in Python

Students can test and verify both algorithms on their lab workstations using the Python IDLE environment:

# ==========================================

# ICT Lab Exercise: Sorting Algorithms

# ==========================================

# 1. Bubble Sort Implementation

def bubble_sort(arr):

    n = len(arr)

    data = arr.copy()

    for i in range(n):

        swapped = False

        for j in range(0, n - i - 1):

            if data[j] > data[j + 1]:

                # Swap adjacent elements

                data[j], data[j + 1] = data[j + 1], data[j]

                swapped = True

        # If no elements were swapped in this pass, array is sorted

        if not swapped:

            break

    return data

# 2. Insertion Sort Implementation

def insertion_sort(arr):

    data = arr.copy()

    for i in range(1, len(data)):

        key = data[i]

        j = i - 1

        # Shift elements of data[0..i-1] that are greater than key

        while j >= 0 and data[j] > key:

            data[j + 1] = data[j]

            j -= 1

        data[j + 1] = key

    return data

# Test with unorganized student test scores

raw_scores = [78, 45, 92, 63, 88, 54]

print("Original Scores :", raw_scores)

print("Bubble Sorted :", bubble_sort(raw_scores))

print("Insertion Sorted:", insertion_sort(raw_scores))

Lab Verification Steps:

 * Save the script as sorting_lab.py and run it (F5).

 * Trace the output to confirm that both functions yield the identical sorted sequence: [45, 54, 63, 78, 88, 92].

 * Try passing an already sorted list ([10, 20, 30]) and observe that Bubble Sort exits after a single pass due to the swapped flag optimization.

7. Review Questions & Key Answers

Q1: Why is Insertion Sort generally preferred over Bubble Sort for small datasets?

 * Answer: While both have a worst-case time complexity of O(n^2), Insertion Sort performs fewer operations because it shifts elements in memory rather than performing repeated read-write variable swaps at every comparison.

Q2: What optimization prevents Bubble Sort from continuing unnecessary loops if the list is already sorted?

 * Answer: Introducing a boolean flag (such as swapped = False). If an entire pass completes without a single swap occurring, the algorithm breaks early because the elements are already in order.

Q3: What does it mean that both Bubble Sort and Insertion Sort are "in-place" algorithms?

 * Answer: They rearrange elements directly within the original list without allocating additional auxiliary arrays, requiring O(1) extra memory space.