One pass of a bubble sort

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. In one pass of a bubble sort, which comparison checks each item against its neighbour?

A IF Marks[Index] > Marks[Index] THEN

B IF Marks[Index] > Marks[Index + 1] THEN

2. An array Marks has 6 items, so n = 6. Which loop header is correct for one pass?

A FOR Index ← 1 TO n - 1

B FOR Index ← 1 TO n

3. Where should the three swap lines go in one pass of a bubble sort?

A Inside the IF, so they only run when the pair is out of order

B After ENDIF, so they run on every loop

4. The array Marks holds 5, 9, 2, 7. After one full pass (ascending order), what does it hold?

A 2, 5, 7, 9

B 5, 2, 7, 9

5. What is guaranteed after one complete pass of a bubble sort (ascending)?

A The largest value is now at the end of the array

B The whole array is now in order

Match the Pairs

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

Left column		Right column
1IF Marks[Index] > Marks[Index + 1] THEN		AIF Marks[Index] < Marks[Index + 1] THEN
2FOR Index ← 1 TO n - 1		BThere is no temporary variable, so the first assignment overwrites Marks[Index] and both items end up with the same value. Use Temp to hold one value first.
3To sort into descending order, change the comparison so the swap happens when the first item is smaller than its neighbour		CLoops so that Index + 1 never goes past the last item in the array
4The swap must be inside the IF, so it only happens when the pair is in the wrong order		DIF Marks[Index] > Marks[Index + 1] THEN Temp ← Marks[Index] Marks[Index] ← Marks[Index + 1] Marks[Index + 1] ← Temp ENDIF
5FOR Index ← 1 TO n IF Marks[Index] > Marks[Index + 1] THEN		ECompares an item with its neighbour and runs the swap only if the first is larger than the second
6IF Marks[Index] > Marks[Index + 1] THEN Marks[Index] ← Marks[Index + 1] Marks[Index + 1] ← Marks[Index] ENDIF		FThe loop goes up to n, so on the last turn Marks[Index + 1] is outside the array and causes an error. The upper bound should be n - 1.

Definitions

IF Marks[Index] > Marks[Index + 1] THEN

Fill in the Blanks

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

FOR Index ← 1 TO 4 IF Marks[Index] _ Marks[Index + 1] THEN ENDIF

FOR Index ← 1 TO _____ IF Marks[Index] > Marks[Index + 1] THEN ENDIF

____ ← Marks[Index] Marks[Index] ← Marks[Index + 1] Marks[Index + 1] ← Temp

IF Marks[Index] _ Marks[Index + 1] THEN Temp ← Marks[Index] Marks[Index] ← Marks[Index + 1]

Marks[Index] ← Marks[Index + 1] Marks[_________] ← Temp ENDIF

Spot the Error

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

Question 1

A FOR i ← 1 TO n - 1

B IF Num[i] > Num[i] THEN

C SWAP(Num[i], Num[i + 1])

D ENDIF

E NEXT i

Question 2

A IF Num[i] > Num[i + 1] THEN

B Temp ← Num[i]

C Num[i] ← Num[i + 1]

D Num[i] ← Temp

E ENDIF

Question 3

A // One pass, ascending

B FOR i ← 1 TO n

C IF Num[i] > Num[i + 1] THEN

D SWAP(Num[i], Num[i + 1])

E ENDIF

F NEXT i

Question 4

A // One pass, descending

B FOR i ← 1 TO n - 1

C IF Num[i] > Num[i + 1] THEN

D SWAP(Num[i], Num[i + 1])

E ENDIF

F NEXT i

Question 5

A FOR i ← 1 TO n - 2

B IF Num[i] > Num[i + 1] THEN

C SWAP(Num[i], Num[i + 1])

D ENDIF

E NEXT i

Answer Key

One pass of a bubble sort

Section A: Quick Questions

B — IF Marks[Index] > Marks[Index + 1] THEN

A — FOR Index ← 1 TO n - 1

A — Inside the IF, so they only run when the pair is out of order

B — 5, 2, 7, 9

A — The largest value is now at the end of the array

Section B: Match the Pairs

IF Marks[Index] > Marks[Index + 1] THEN → Compares an item with its neighbour and runs the swap only if the first is larger than the second

FOR Index ← 1 TO n - 1 → Loops so that Index + 1 never goes past the last item in the array

To sort into descending order, change the comparison so the swap happens when the first item is smaller than its neighbour → IF Marks[Index] < Marks[Index + 1] THEN

The swap must be inside the IF, so it only happens when the pair is in the wrong order → IF Marks[Index] > Marks[Index + 1] THEN Temp ← Marks[Index] Marks[Index] ← Marks[Index + 1] Marks[Index + 1] ← Temp ENDIF

FOR Index ← 1 TO n IF Marks[Index] > Marks[Index + 1] THEN → The loop goes up to n, so on the last turn Marks[Index + 1] is outside the array and causes an error. The upper bound should be n - 1.

IF Marks[Index] > Marks[Index + 1] THEN Marks[Index] ← Marks[Index + 1] Marks[Index + 1] ← Marks[Index] ENDIF → There is no temporary variable, so the first assignment overwrites Marks[Index] and both items end up with the same value. Use Temp to hold one value first.

Section C: Definitions

IF Marks[Index] > Marks[Index + 1] THEN — One pass: a FOR loop compares each item with its neighbour and swaps them if the first is larger, so the biggest value moves to the end.

Section D: Fill in the Blanks

FOR Index ← 1 TO 4
   IF Marks[Index] > Marks[Index + 1] THEN
   ENDIF

FOR Index ← 1 TO n - 1
   IF Marks[Index] > Marks[Index + 1] THEN
   ENDIF

Temp ← Marks[Index]
Marks[Index] ← Marks[Index + 1]
Marks[Index + 1] ← Temp

IF Marks[Index] < Marks[Index + 1] THEN
   Temp ← Marks[Index]
   Marks[Index] ← Marks[Index + 1]

Marks[Index] ← Marks[Index + 1]
Marks[Index + 1] ← Temp
ENDIF

Section E: Spot the Error

B — Num[i] is compared with itself, so the condition is never true and nothing is ever swapped. It should compare with the neighbour: IF Num[i] > Num[i + 1] THEN.

D — This puts the old Num[i] back where it started, so Num[i + 1] never changes and the swap fails. The last swap line should be Num[i + 1] ← Temp.

B — When i reaches n, Num[i + 1] is outside the array. The upper bound must be n - 1 so that i + 1 stays inside the array.

C — Using > swaps larger values towards the end, which gives ascending order. For descending order the test must be <: IF Num[i] < Num[i + 1] THEN.

A — The loop stops one pair too early, so the last two items are never compared and the biggest value may not reach the end. The upper bound should be n - 1.