CS: Sorting Algorithms: Bubble, Selection, and Insertion Worksheet

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

After the first pass, the list is [10, 29, 14, 37, 13]. After the second pass, the list is [10, 13, 14, 37, 29].

Question 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.

Accepted Answer

After inserting 4, the list is [2, 4, 5, 9, 7]. The value 4 moves before 5 and 9 but stays after 2.

Question 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?

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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.

Accepted Answer

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.

Question 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?

Accepted Answer

Only 1 pass is needed. The first pass makes no swaps, which shows the list is already sorted, so the optimized algorithm stops.

Question 11

Trace insertion sort on [8, 4, 6, 2]. Write the list after inserting 4, after inserting 6, and after inserting 2.

Accepted Answer

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].

Question 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.

Accepted Answer

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.

CS: Sorting Algorithms: Bubble, Selection, and Insertion

Related Cheat Sheets

More CS Worksheets

More Grade 9-12 Worksheets