B2.4.3 Construct and trace algorithms to implement bubble sort and selection sort, evaluating their time and space complexities.

📚 You can find additional information in the course companion pages 385 to 396

The Big Idea

Sorting is one of the most fundamental operations in computer science. Two of the most well-known algorithms for sorting are Bubble Sort and Selection Sort. Both are comparison-based sorting algorithms that illustrate basic algorithmic design and can be implemented with simple loops and conditionals. While inefficient on large data sets, they are invaluable for introducing core concepts such as iteration, array indexing, and most importantly, time and space complexity expressed using Big O notation.

 

Bubble Sort and Selection Sort: Algorithm Construction and Tracing

Bubble Sort

Algorithm Concept:
Bubble sort repeatedly compares adjacent pairs of elements in a list and swaps them if they are in the wrong order. This process "bubbles" the largest unsorted value to its correct position with each full pass through the list.

Pseudocode:

for i from 0 to n - 1:
    for j from 0 to n - i - 2:
        if array[j] > array[j + 1]:
            swap array[j] and array[j + 1]

 

The reason it’s nested is because the algorithm needs two passes:

1. Outer loop (for i in range(n-1)):

   • Controls how many times we go through the list.

   • Each full pass guarantees that the largest unsorted element "bubbles up" to the end.

   • After i passes, the last i elements are already sorted, so we don’t need to check them again.

2. Inner loop (<strong data-start="445" data-end="486">for j in range(n-i-1)</strong>:

   • Actually compares adjacent elements.

   • If mylist[j] > mylist[j+1], they are swapped.

   • This gradually pushes the largest value in the unsorted portion to the right.

So the inner loop does the swapping, while the outer loop repeats the process until the whole list is sorted.

 

Worked Example:
Given [5, 3, 8, 4, 2]

• After Pass 1 → [3, 5, 4, 2, 8]
• After Pass 2 → [3, 4, 2, 5, 8]
• After Pass 3 → [3, 2, 4, 5, 8]
• After Pass 4 → [2, 3, 4, 5, 8]

Trace Table Format (partial):

Pass	i	j	Comparison	Array State
1	0	0	5 > 3 → swap	[3, 5, 8, 4, 2]
1	0	1	5 > 8 → no swap	[3, 5, 8, 4, 2]
...			...	...

 

Selection Sort

Algorithm Concept:
Selection sort divides the list into a sorted and an unsorted region. It repeatedly selects the smallest remaining element and swaps it with the leftmost unsorted element.

Pseudocode:

for i from 0 to n - 1:
    min_index = i
    for j from i + 1 to n - 1:
        if array[j] < array[min_index]:
            min_index = j
    swap array[i] and array[min_index]

Worked Example:
Given [5, 3, 8, 4, 2]

• After Pass 1 → [2, 3, 8, 4, 5]
• After Pass 2 → [2, 3, 8, 4, 5]
• After Pass 3 → [2, 3, 4, 8, 5]
• After Pass 4 → [2, 3, 4, 5, 8]

 

Time and Space Complexity

Algorithm	Best Case	Average Case	Worst Case	Space Complexity	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No

Details:

• Bubble Sort
  • Best case (already sorted list): O(n), when optimized with a swap flag.
  • Worst and average case: O(n²), due to nested iterations.
  • Performs unnecessary comparisons even when no swaps are needed unless optimized.
• Selection Sort
  • Always O(n²) comparisons, regardless of list state.
  • More consistent than bubble sort but performs fewer swaps.
  • Not stable because swapping might reorder equal elements.

 

Evaluation of Advantages and Disadvantages

Algorithm	Advantages	Disadvantages
Bubble Sort	Simple to implement; detects already sorted list early (with optimization)	Very inefficient on large lists due to O(n²) time complexity
Selection Sort	Fewer swaps than bubble sort; simple logic	Still O(n²); no performance gain on nearly sorted input; not stable

 

Educational Value

While both algorithms are inefficient compared to quicksort, mergesort, or heapsort, they are excellent for teaching:

• Tracing algorithms
• Understanding time complexity
• Practicing array manipulation and nested loops
• Algorithmic reasoning and iterative refinement

 

Command Term: Construct

In this standard (B2.4.3), the command term is Construct, which means:

“Display information in a diagrammatic or logical form.”

A good response will include full pseudocode or a working program, with correctly initialized loops, index tracking, and swaps.

A less-good response might skip essential parts like initialization, use ambiguous variables, or neglect edge cases like empty or one-element lists.