Bubble sort in pseudocode

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which pseudocode correctly swaps Item[i] and Item[i + 1] in a bubble sort?

A Item[i] ← Item[i + 1] Item[i + 1] ← Item[i]

B Temp ← Item[i] Item[i] ← Item[i + 1] Item[i + 1] ← Temp

2. What does the inner loop of a bubble sort compare?

A The first element with every other element in the array

B Neighbouring elements: Item[i] and Item[i + 1]

3. When should a bubble sort swap Item[i] and Item[i + 1] to sort into ascending order?

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

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

4. True or false: a bubble sort can stop when a complete pass makes no swaps.

A True: no swaps means every neighbouring pair is already in order

B False: it must always keep making passes until the loop counter ends

5. What is the job of the outer loop in a bubble sort?

A It repeats the passes through the array

B It swaps the two items using Temp

Match the Pairs

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

Left column		Right column
1Temp ← Item[i] Item[i] ← Item[i + 1] Item[i + 1] ← Temp		ASwaps two neighbouring elements by holding one value in a temporary variable first
2IF Item[i] > Item[i + 1] THEN		BCompares two neighbouring elements and checks whether they are in the wrong order for an ascending sort
3The inner loop visits every neighbouring pair in one pass, so it stops one place before the end of the array		CFOR i ← 1 TO Count - 1
4The outer loop repeats passes until a pass makes no swaps, using a flag to record whether a swap happened		DThe loop goes up to Count, so on the last pass Item[i + 1] is outside the array. The loop should end at Count - 1.
5Item[i] ← Item[i + 1] Item[i + 1] ← Item[i]		EREPEAT Swapped ← FALSE // inner loop pass UNTIL Swapped = FALSE
6FOR i ← 1 TO Count IF Item[i] > Item[i + 1] THEN		FNo Temp variable is used, so Item[i] is overwritten and both elements end up with the same value. The original Item[i] is lost.

Definitions

bubble sort

Fill in the Blanks

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

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

IF Item[i] _ Item[i + 1] THEN // swap the two items ENDIF

FOR i ← 1 TO _ // compare Item[i] and Item[i + 1] NEXT i

REPEAT // inner loop makes one pass UNTIL Swapped = _____

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

Spot the Error

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

Question 1

A FOR i = 0 TO 3

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

C Temp ← Item[i]

D Item[i] ← Item[i + 1]

E Item[i + 1] ← Temp

F ENDIF

Question 2

A DECLARE Temp INTEGER

B Temp ← Item[i]

C Item[i] ← Item[i + 1]

D Item[i + 1] ← Temp

Question 3

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

B Temp ← Item[i]

C Item[i] ← Item[i + 1]

D Item[i + 1] ← Item[i]

E ENDIF

Question 4

A FOR i ← 0 TO 3

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

C Temp ← Item[i + 1]

D Item[i] ← Item[i + 1]

E Item[i + 1] ← Temp

F ENDIF

Question 5

A FOR i ← 0 TO 3

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

C CALL Swap(i)

D ENDIF

E NEXT i

Answer Key

Bubble sort in pseudocode

Section A: Quick Questions

B — Temp ← Item[i] Item[i] ← Item[i + 1] Item[i + 1] ← Temp

B — Neighbouring elements: Item[i] and Item[i + 1]

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

A — True: no swaps means every neighbouring pair is already in order

A — It repeats the passes through the array

Section B: Match the Pairs

Temp ← Item[i] Item[i] ← Item[i + 1] Item[i + 1] ← Temp → Swaps two neighbouring elements by holding one value in a temporary variable first

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

The inner loop visits every neighbouring pair in one pass, so it stops one place before the end of the array → FOR i ← 1 TO Count - 1

The outer loop repeats passes until a pass makes no swaps, using a flag to record whether a swap happened → REPEAT Swapped ← FALSE // inner loop pass UNTIL Swapped = FALSE

Item[i] ← Item[i + 1] Item[i + 1] ← Item[i] → No Temp variable is used, so Item[i] is overwritten and both elements end up with the same value. The original Item[i] is lost.

FOR i ← 1 TO Count IF Item[i] > Item[i + 1] THEN → The loop goes up to Count, so on the last pass Item[i + 1] is outside the array. The loop should end at Count - 1.

Section C: Definitions

bubble sort — A sort that makes repeated passes, comparing neighbouring items and swapping them using a Temp variable if they are in the wrong order, until a pass makes no swaps.

Section D: Fill in the Blanks

Temp ← Item[i]
Item[i] ← Item[i + 1]
Item[i + 1] ← Temp

IF Item[i] > Item[i + 1] THEN
  // swap the two items
ENDIF

FOR i ← 1 TO 9
  // compare Item[i] and Item[i + 1]
NEXT i

REPEAT
  // inner loop makes one pass
UNTIL Swapped = FALSE

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

Section E: Spot the Error

A — The FOR loop must set its counter with the assignment arrow, so it should be FOR i ← 0 TO 3. In pseudocode = is used for comparison, not assignment.

A — A DECLARE statement needs a colon between the identifier and its data type. It should be DECLARE Temp : INTEGER.

D — The second item must receive the value saved in Temp. Copying Item[i] again means the original Item[i] value is lost and Temp is never used. It should be Item[i + 1] ← Temp.

C — Temp must store the value of Item[i] before it is overwritten. Storing Item[i + 1] means the old Item[i] value is lost and the swap fails. It should be Temp ← Item[i].

B — The condition must compare neighbouring elements. Item[i] + 1 adds 1 to the value instead of looking at the next element. It should be IF Item[i] > Item[i + 1] THEN.