Comparing the number of comparisons in bubble and selection sort

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. A list has 10 items. About how many comparisons does selection sort make?

A 45 (10 x 9 / 2), which is about n squared

B 10, one comparison per item

2. The list size doubles from 100 to 200 items. How does the number of comparisons change in bubble or selection sort?

A It roughly doubles

B It roughly quadruples

3. Which sort makes far fewer swaps on a random list?

A Selection sort, at most n - 1 swaps

B Bubble sort, at most n - 1 swaps

4. Bubble sort uses a swapped flag and the list is already sorted. How many comparisons does it make?

A n - 1, because one pass finds no swaps and it stops

B About n squared, because it always does every pass

5. Selection sort is given an already sorted list. What happens?

A It stops early after one pass

B It still makes about n squared comparisons

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1n * (n - 1) / 2		AUNTIL swapped = FALSE
2n: 10 -> 20		BComparisons do not just double. They grow with n squared, so doubling n gives about four times the comparisons (45 to 190).
3Bubble sort best case: on an already sorted list, the swapped flag lets it stop after one pass of n - 1 comparisons		CThe number of comparisons selection sort always makes on n items. For n = 10 that is 45 comparisons.
4Selection sort makes at most one swap per pass, so at most n - 1 swaps in total		DDoubling the list size makes about four times as many comparisons: 45 becomes 190.
5n goes from 10 to 20, so comparisons go from 45 to 90		ESWAP A[i], A[min] after the inner FOR loop
6Selection sort comparisons ≈ n		FSelection sort still makes about n squared / 2 comparisons. Its advantage over bubble sort is fewer swaps, not fewer comparisons.

Definitions

O(n^2)

Fill in the Blanks

Complete each line of code by filling in the missing parts.

comparisons ← n * (n - 1) / _

newWork ← _ * oldWork // when n is doubled

IF A[j] > A[j + 1] THEN SWAP A[j], A[j + 1] swapped ← ____

swapped ← TRUE WHILE _______ = TRUE swapped ← FALSE

FOR i FROM 1 TO n - 1 min ← index of smallest in A[i..n] ____ A[i], A[min]

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A comps ← 0

B FOR i ← 1 TO n - 1

C FOR j ← i TO n

D comps ← comps + 1

Question 2

A comps ← 0

B FOR pass ← 1 TO n - 1

C FOR j ← 1 TO n - pass

D comps ← comps - 1

E IF a[j] > a[j+1] THEN

Question 3

A n ← 10

B before ← n * n

C n ← n + 2

D after ← n * n

E PRINT after / before

Question 4

A n ← 100

B selSwaps ← n - 1

C bubComps ← n * (n - 1) / 2

D selComps ← n - 1

E PRINT selSwaps, selComps

Question 5

A swapped ← TRUE

B WHILE swapped = FALSE

C swapped ← FALSE

D FOR j ← 1 TO n - 1

E IF a[j] > a[j+1] THEN

F SWAP; swapped ← TRUE

Answer Key

Comparing the number of comparisons in bubble and selection sort

Section A: Quick Questions

A — 45 (10 x 9 / 2), which is about n squared

B — It roughly quadruples

A — Selection sort, at most n - 1 swaps

A — n - 1, because one pass finds no swaps and it stops

B — It still makes about n squared comparisons

Section B: Match the Pairs

n * (n - 1) / 2 → The number of comparisons selection sort always makes on n items. For n = 10 that is 45 comparisons.

n: 10 -> 20 → Doubling the list size makes about four times as many comparisons: 45 becomes 190.

Bubble sort best case: on an already sorted list, the swapped flag lets it stop after one pass of n - 1 comparisons → UNTIL swapped = FALSE

Selection sort makes at most one swap per pass, so at most n - 1 swaps in total → SWAP A[i], A[min] after the inner FOR loop

n goes from 10 to 20, so comparisons go from 45 to 90 → Comparisons do not just double. They grow with n squared, so doubling n gives about four times the comparisons (45 to 190).

Selection sort comparisons ≈ n → Selection sort still makes about n squared / 2 comparisons. Its advantage over bubble sort is fewer swaps, not fewer comparisons.

Section C: Definitions

O(n^2) — Bubble and selection sort both make about n squared comparisons, so doubling n quadruples the work, but selection sort makes far fewer swaps.

Section D: Fill in the Blanks

comparisons ← n * (n - 1) / 2

newWork ← 4 * oldWork
// when n is doubled

IF A[j] > A[j + 1] THEN
    SWAP A[j], A[j + 1]
    swapped ← TRUE

swapped ← TRUE
WHILE swapped = TRUE
    swapped ← FALSE

FOR i FROM 1 TO n - 1
    min ← index of smallest in A[i..n]
    SWAP A[i], A[min]

Section E: Spot the Error

C — Selection sort compares a[min] with the elements after position i, so the inner loop must start at i + 1. Starting at i adds a pointless comparison of an item with itself on every pass and gives the wrong comparison count.

D — Each time bubble sort compares a[j] with a[j+1], the counter must go up by 1, so it should be comps ← comps + 1. Subtracting would make the total shrink instead of reaching about n squared.

C — Doubling n means multiplying it by 2, so the line should be n ← n * 2. Then after is 400 and before is 100, so the program prints 4 (doubling n quadruples the work). Adding 2 would not double n.

D — Selection sort still compares about n squared / 2 items, the same as bubble sort. It is only its swaps that are limited to n - 1. The line should be selComps ← n * (n - 1) / 2.

B — The loop must keep running while swaps are still being made, so the condition is WHILE swapped = TRUE. With = FALSE the loop would never start because swapped begins as TRUE.