Tracing a bubble sort

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. A bubble sort (ascending) is run on [5, 3, 8, 1]. What does the array look like after pass 1?

A [3, 5, 1, 8]

B [1, 3, 5, 8]

2. Trace [4, 2, 7, 1, 3] through pass 1 of a bubble sort. How many swaps are made?

A 2 swaps

B 3 swaps

3. In the trace of [4, 4, 2], two equal values 4 and 4 are compared. What happens?

A No swap, because 4 > 4 is false

B They are swapped, because they are the same

4. In a trace table, Data[j] is 6 and Data[j + 1] is 2. What value is written in the Temp column?

A 2

B 6

5. A pass finishes and the Swapped column still shows FALSE. What does this tell you?

A No swaps were made, so the array is sorted and the loop stops

B The array is not sorted, so another pass is needed

Match the Pairs

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

Left column		Right column
15 3 8 1 → 3 5 1 8		ASwapped ← TRUE
2Temp ← Numbers[i]		BThe array before and after pass 1 of a bubble sort on 5, 3, 8, 1. Adjacent pairs were compared, and the 8 reached the end.
3In a trace table, the Swapped column changes to TRUE on any comparison that causes a swap during a pass.		CFOR Index ← 1 TO 4
4With 5 items, one pass makes 4 comparisons, so the trace has 4 comparison rows for each pass.		DThe Temp column holds the value copied out of the array just before a swap, so it is not lost when overwritten.
55 3 8 1 after pass 1: 1 3 5 8		EA single pass only swaps neighbouring items, so it cannot fully sort the array. After pass 1 the array is 3 5 1 8.
6IF Numbers[i] >= Numbers[i + 1] THEN		FUsing >= swaps equal values for no reason. With duplicates, Swapped is set to TRUE even though nothing changes.

Definitions

bubble sort trace

Fill in the Blanks

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

IF Data[i] _ Data[i + 1] THEN // swap, equal values are left alone ENDIF

Temp ← Data[i] Data[i] ← Data[i + 1] Data[i + 1] ← ____

IF Data[i] > Data[i + 1] THEN Swapped ← ____ ENDIF

// Data has 5 items FOR i ← 1 TO _ IF Data[i] > Data[i + 1] THEN

REPEAT Swapped ← _____ FOR i ← 1 TO 4

Spot the Error

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

Question 1

A Temp ← A[2]

B A[1] ← A[2]

C A[2] ← Temp

Question 2

A Temp ← A[J]

B A[J] ← A[J + 1]

C A[J + 1] ← A[J]

Question 3

A Start: 4 3 1

B Compare 4,3: swap -> 3 4 1

C Compare 4,1: no swap -> 3 4 1

D Pass 1 done: 2 swaps

Question 4

A Start: 3 3 1

B Compare 3,3: swap -> 3 3 1

C Compare 3,1: swap -> 3 1 3

D Pass 1 done: 1 swap

Question 5

A Swapped ← FALSE

B IF A[J] > A[J + 1] THEN

C Swapped ← FALSE

D ENDIF

Answer Key

Tracing a bubble sort

Section A: Quick Questions

A — [3, 5, 1, 8]

B — 3 swaps

A — No swap, because 4 > 4 is false

B — 6

A — No swaps were made, so the array is sorted and the loop stops

Section B: Match the Pairs

5 3 8 1 → 3 5 1 8 → The array before and after pass 1 of a bubble sort on 5, 3, 8, 1. Adjacent pairs were compared, and the 8 reached the end.

Temp ← Numbers[i] → The Temp column holds the value copied out of the array just before a swap, so it is not lost when overwritten.

In a trace table, the Swapped column changes to TRUE on any comparison that causes a swap during a pass. → Swapped ← TRUE

With 5 items, one pass makes 4 comparisons, so the trace has 4 comparison rows for each pass. → FOR Index ← 1 TO 4

5 3 8 1 after pass 1: 1 3 5 8 → A single pass only swaps neighbouring items, so it cannot fully sort the array. After pass 1 the array is 3 5 1 8.

IF Numbers[i] >= Numbers[i + 1] THEN → Using >= swaps equal values for no reason. With duplicates, Swapped is set to TRUE even though nothing changes.

Section C: Definitions

bubble sort trace — Writing out the array after every pass, showing each comparison and swap, plus the Temp and Swapped values, to see how a bubble sort puts the data in order.

Section D: Fill in the Blanks

IF Data[i] > Data[i + 1] THEN
   // swap, equal values are left alone
ENDIF

Temp ← Data[i]
Data[i] ← Data[i + 1]
Data[i + 1] ← Temp

IF Data[i] > Data[i + 1] THEN
   Swapped ← TRUE
ENDIF

// Data has 5 items
FOR i ← 1 TO 4
   IF Data[i] > Data[i + 1] THEN

REPEAT
   Swapped ← FALSE
   FOR i ← 1 TO 4

Section E: Spot the Error

A — Temp must store the first value, A[1], before it is overwritten. Storing A[2] in Temp means A[1] is lost and both elements end up equal. It should be Temp ← A[1].

C — A[J] has already been overwritten on line 2, so copying it would duplicate the new value. The original A[J] was saved in Temp, so the line should be A[J + 1] ← Temp.

C — 4 is greater than 1, so the pair must be swapped, giving 3 1 4. The trace should read: Compare 4,1: swap -> 3 1 4.

B — Bubble sort only swaps when the left value is greater than the right value. Duplicate values are equal, so there is no swap. The line should say: no swap.

C — When a swap happens inside the IF, the Swapped flag must be set to TRUE so the sort knows another pass is needed. It should be Swapped ← TRUE.