CS: Sorting Algorithms: Bubble, Selection, and Insertion
Tracing, comparing, and choosing basic sorting algorithms
CS: Sorting Algorithms: Bubble, Selection, and Insertion
Tracing, comparing, and choosing basic sorting algorithms
CS - Grade 9-12
- 1
Bubble sort compares adjacent values and swaps them when they are out of order. Starting with the list [5, 1, 4, 2, 8], write the list after one full left-to-right pass of bubble sort.
Compare only neighboring values, moving from left to right.
After one full pass, the list is [1, 4, 2, 5, 8]. The swaps are 5 with 1, then 5 with 4, then 5 with 2. - 2
Selection sort finds the smallest value in the unsorted part and swaps it into the next sorted position. Starting with [29, 10, 14, 37, 13], write the list after the first two passes of selection sort.
After the first pass, the list is [10, 29, 14, 37, 13]. After the second pass, the list is [10, 13, 14, 37, 29]. - 3
Insertion sort builds a sorted section at the front of the list. The current list is [2, 5, 9, 4, 7], where [2, 5, 9] is already sorted. Insert 4 into the sorted section and write the new list.
Shift larger values to the right until the new value fits.
After inserting 4, the list is [2, 4, 5, 9, 7]. The value 4 moves before 5 and 9 but stays after 2. - 4
Complete this comparison: Bubble sort, selection sort, and insertion sort all have worst-case time complexity O(n^2). Which one usually has the best best-case time complexity on an already sorted list if implemented with an early stop or natural stopping condition, and why?
Insertion sort usually has best-case time complexity O(n) on an already sorted list because each item is checked and no shifting is needed. Optimized bubble sort can also be O(n) if it stops after a pass with no swaps. - 5
A stable sorting algorithm keeps equal values in their original relative order. In a typical implementation that swaps only when the left value is greater than the right value, is bubble sort stable? Explain your answer.
Focus on what happens when two adjacent values are equal.
Bubble sort is stable in this typical implementation because equal values are not swapped. Since equal values keep their original relative order, the sort is stable. - 6
Selection sort is often not stable. Consider the list [(4, A), (4, B), (3, C)], where the number is the sort key and the letter is the item label. Explain how selection sort can change the order of equal 4 values.
Selection sort can find (3, C) as the smallest value and swap it with the first item, producing [(3, C), (4, B), (4, A)]. The equal 4 values have changed order from A before B to B before A, so this version is not stable. - 7
Count the number of swaps made during one full pass of bubble sort on the list [6, 3, 5, 2]. Also write the list after that pass.
Track each adjacent comparison and count only the comparisons that cause a swap.
The pass makes 3 swaps. The list becomes [3, 5, 2, 6] after swapping 6 with 3, then 6 with 5, then 6 with 2. - 8
A list is almost sorted: [1, 2, 3, 5, 4, 6, 7]. Choose bubble sort, selection sort, or insertion sort as the best simple algorithm for this case, and explain your choice.
Insertion sort is the best choice among these simple algorithms because the list is nearly sorted. It only needs to move 4 left by one position, so it does very little work compared with selection sort. - 9
Selection sort runs on a list with 6 items. How many total comparisons are made to find the minimum values across all passes? Assume the final one-item section does not need a pass.
Add the number of comparisons needed for each shrinking unsorted section.
Selection sort makes 15 comparisons. The passes compare 5, then 4, then 3, then 2, then 1 item pairs, and 5 + 4 + 3 + 2 + 1 = 15. - 10
An optimized bubble sort stops if a full pass makes no swaps. Starting with [1, 2, 3, 4], how many passes are needed before the algorithm stops, and why?
Only 1 pass is needed. The first pass makes no swaps, which shows the list is already sorted, so the optimized algorithm stops. - 11
Trace insertion sort on [8, 4, 6, 2]. Write the list after inserting 4, after inserting 6, and after inserting 2.
At each step, treat everything to the left of the current item as already sorted.
After inserting 4, the list is [4, 8, 6, 2]. After inserting 6, the list is [4, 6, 8, 2]. After inserting 2, the list is [2, 4, 6, 8]. - 12
You need to sort 1,000,000 random numbers in a real application. Explain why bubble sort, selection sort, and insertion sort are usually poor choices for this task, and name one faster type of sorting algorithm.
Bubble sort, selection sort, and insertion sort are usually poor choices because their average or worst-case running time is O(n^2), which is too slow for 1,000,000 random numbers. A faster choice would be merge sort, quicksort, or heap sort, which are commonly O(n log n) on large inputs.