Bubble sort: how it works

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. In a bubble sort, which items are compared with each other?

A The first item and the last item only

B Neighbouring items (next to each other in the list)

2. Sorting in ascending order, a bubble sort compares 7 and 3. What happens?

A They are swapped, because 7 is bigger than 3

B They stay where they are, because 7 comes first

3. After the first full pass of a bubble sort in ascending order, where is the largest value?

A At the start of the list

B At the end of the list

4. After each pass of a bubble sort, how many more items are in their final position?

A At least one more item is in place at the end

B The whole list is always sorted after one pass

5. List: 4, 9, 2. Which pair of values is compared first in a bubble sort?

A 4 and 9

B 4 and 2

Match the Pairs

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

Left column		Right column
1IF Numbers[i] > Numbers[i + 1] THEN		AIF Scores[i] < Scores[i + 1] THEN
2Temp ← Numbers[i]		BStores one of the two items safely so the pair can be swapped without losing a value
3Each pass of a bubble sort compares neighbours from the start of the list up to the last item not yet in place		COne pass only guarantees that the largest value is at the end. More passes are usually needed, so the sort is not necessarily finished.
4To sort in descending order, swap when the left item is smaller than the right item		DCompares two neighbouring items and checks whether they are in the wrong order for an ascending sort
5[5, 3, 8] after one pass becomes [3, 5, 8] and the sort is always finished		EA bubble sort can sort strings as well as numbers, because strings can be compared in alphabetical order.
6Names: Zara, Adam, Maya. Bubble sort cannot sort text, only numbers		FFOR i ← 1 TO 4

Definitions

bubble sort

Fill in the Blanks

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

IF Numbers[i] _ Numbers[i + 1] THEN

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

IF Numbers[i] _ Numbers[i + 1] THEN

FOR Pass ← 1 TO 4 FOR i ← 1 TO 5 - ____

IF Names[i] > Names[_____] THEN

Spot the Error

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

Question 1

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

B Temp ← A[i]

C A[i] ← Temp

D A[i + 1] ← Temp

E ENDIF

Question 2

A FOR i ← 1 TO 4

B IF A[i] < A[i + 1] THEN

C swap A[i] and A[i + 1]

D ENDIF

E NEXT i

Question 3

A // One pass over 5 items

B FOR i ← 1 TO 5

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

D swap A[i] and A[i + 1]

E ENDIF

F NEXT i

Question 4

A FOR pass ← 1 TO 1

B FOR i ← 1 TO 5 - pass

C swap if A[i] > A[i + 1]

D NEXT i

E NEXT pass

Question 5

A Unsorted ← 5

B FOR pass ← 1 TO 4

C Unsorted ← Unsorted + 1

D OUTPUT Unsorted

E NEXT pass

Answer Key

Bubble sort: how it works

Section A: Quick Questions

B — Neighbouring items (next to each other in the list)

A — They are swapped, because 7 is bigger than 3

B — At the end of the list

A — At least one more item is in place at the end

A — 4 and 9

Section B: Match the Pairs

IF Numbers[i] > Numbers[i + 1] THEN → Compares two neighbouring items and checks whether they are in the wrong order for an ascending sort

Temp ← Numbers[i] → Stores one of the two items safely so the pair can be swapped without losing a value

Each pass of a bubble sort compares neighbours from the start of the list up to the last item not yet in place → FOR i ← 1 TO 4

To sort in descending order, swap when the left item is smaller than the right item → IF Scores[i] < Scores[i + 1] THEN

[5, 3, 8] after one pass becomes [3, 5, 8] and the sort is always finished → One pass only guarantees that the largest value is at the end. More passes are usually needed, so the sort is not necessarily finished.

Names: Zara, Adam, Maya. Bubble sort cannot sort text, only numbers → A bubble sort can sort strings as well as numbers, because strings can be compared in alphabetical order.

Section C: Definitions

bubble sort — A sorting method that compares neighbouring items and swaps them if in the wrong order, repeating passes until the list is sorted. The largest value bubbles to the end each pass.

Section D: Fill in the Blanks

IF Numbers[i] > Numbers[i + 1] THEN

Temp ← Numbers[i]
Numbers[i] ← Numbers[i + 1]
Numbers[i + 1] ← Temp

IF Numbers[i] < Numbers[i + 1] THEN

FOR Pass ← 1 TO 4
   FOR i ← 1 TO 5 - Pass

IF Names[i] > Names[i + 1] THEN

Section E: Spot the Error

C — Line 3 should be A[i] ← A[i + 1]. A swap needs Temp to hold the first value, then the second value moves into position i, then Temp goes into position i + 1. As written, A[i] gets its own value back and the value in A[i + 1] is never moved.

B — For ascending order, neighbours are in the wrong order when the first is bigger than the second, so the test must be A[i] > A[i + 1]. Using < swaps pairs that are already correct.

B — With 5 items there are only 4 neighbouring pairs. The loop must stop at 4, because when i is 5 the code compares A[5] with A[6], which does not exist.

A — One pass only moves the largest value to the end. A list of 5 items may need up to 4 passes, so the outer loop should be FOR pass ← 1 TO 4.

C — After each pass one more item is in its final place at the end, so the number of unsorted items goes down by 1. It should be Unsorted ← Unsorted - 1.