IB Computer Science Topic B2.4.3: Constructing and Tracing Bubble Sort and Selection Sort, Evaluating Time and Space Complexities Notes

Bubble Sort and Selection Sort: Same Cost, Different Behaviour

1. Bubble sort compares adjacent pairs and swaps them whenever they are the wrong way round.
2. Selection sort scans the unsorted part for the smallest remaining value and puts it straight into position.
3. Both are O(n²) and both sort in place, so the choice between them turns on how many swaps each performs and whether the data is nearly sorted already.

Bubble Sort: Walk the Array, Swapping Neighbours

1. Compare each pair of adjacent elements from the start of the array.
2. Swap the pair if the left value is greater than the right value.
3. At the end of the first pass the largest value has travelled to the last position, so the next pass can stop one place earlier.
4. Repeat until a pass completes with no swaps, which means the array is sorted.

Implementing Bubble Sort

1. The inner loop shortens by one on each pass, because the items at the end are already in their final positions.
2. The flag is reset at the start of every pass and checked at the end of it.

Tracing Bubble Sort on [5, 1, 4, 2]

1. After pass 1 the largest value, 5, is in its final position, so pass 2 makes only two comparisons instead of three.
2. Pass 3 makes one comparison and no swaps, so the flag stays false and the loop stops early.
3. The trace took 6 comparisons and 4 swaps.

Evaluating Bubble Sort

1. Time complexity
   1. Best case O(n): the array is already sorted, the first pass makes no swaps and the flag stops the loop.
   2. Average case O(n²): roughly half the pairs are out of order on each pass.
   3. Worst case O(n²): the array is in reverse order, so every comparison causes a swap.
2. Space complexity O(1): only one temporary variable is needed to perform a swap.
3. Strengths
   1. Short to write and easy to trace by hand, which is why it appears so often on Paper 2.
   2. Detects an already sorted array in a single pass, so it is a reasonable choice for nearly sorted data.
4. Weaknesses
   1. Unusable on large data sets: a million records would need roughly 10¹² comparisons.
   2. Performs many swaps, which is costly when the items being moved are large records rather than integers.

Selection Sort: Find the Smallest, Put It in Place

1. Treat the array as a sorted section on the left, which starts empty, and an unsorted section on the right.
2. Scan the whole unsorted section to find the index of the smallest value.
3. Swap that value with the first element of the unsorted section, which extends the sorted section by one.
4. Repeat until only one element remains unsorted, which must already be the largest.

Implementing Selection Sort

1. min_index is initialized to i, the first unsorted position, not to 0 and not to the value stored there.
2. The inner loop compares values but only ever updates an index, so the single swap happens after the scan finishes.

Tracing Selection Sort on [5, 1, 4, 2]

1. The array is already sorted after pass 1, but selection sort has no way to notice and still runs pass 2 in full.
2. The trace took 6 comparisons and 3 swaps, one of which moved nothing.
3. Bubble sort needed 4 swaps on the same array, which is the practical difference between them.

Evaluating Selection Sort

1. Time complexity
   1. Best, average and worst cases are all O(n²), because the inner scan runs to the end of the unsorted section every time.
   2. The comparison count is fixed at n(n − 1)/2, so 6 comparisons for 4 items and 4950 for 100.
2. Space complexity O(1): it sorts in place, using one temporary variable for the swap.
3. Strengths
   1. Makes at most n − 1 swaps, which matters when writing is expensive, such as sorting records on flash memory.
   2. Its running time is predictable, because it does not depend on the starting order of the data.
4. Weaknesses
   1. No best case: an already sorted array costs exactly as much as a reversed one.
   2. Not stable, so two equal values can end up in the opposite order from the one they started in.

Comparing Bubble Sort and Selection Sort

1. Neither is used in production, where library sorts run at O(n log n).
2. They are on the syllabus because their cost can be counted by hand, which is what makes complexity analysis concrete.