Bubble sort with nested FOR loops

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. An array has n items. How many passes does the outer loop of a bubble sort need?

A FOR Pass ← 1 TO n + 1

B FOR Pass ← 1 TO n - 1

2. An array has 6 items. How many times does the outer loop run?

A 5 times

B 6 times

3. Which inner loop header shrinks with each pass (array indexes start at 1)?

A FOR Index ← 1 TO n - Pass

B FOR Index ← 1 TO n

4. Which line correctly compares two neighbours inside the inner loop?

A IF Numbers[Index] > Numbers[Index] + 1 THEN

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

5. Why can the inner loop bound get smaller after each pass?

A The largest unsorted value has bubbled to the end and is already in place

B The smallest value has moved to the start and the rest is sorted

Match the Pairs

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

Left column		Right column
1FOR Pass ← 1 TO n - 1		AThe outer loop: it repeats the pass through the array n - 1 times
2FOR i ← 1 TO n - Pass		BThe outer loop runs to n instead of n - 1, so it does one pass too many
3Inside the inner loop, compare two neighbours and swap them if they are out of order		CThe NEXT statements are in the wrong order: the loops are not closed from the inside out
4Close the blocks in the right order: ENDIF first, then the inner NEXT, then the outer NEXT		D ENDIF NEXT i NEXT Pass
5FOR Pass ← 1 TO n FOR i ← 1 TO n - Pass IF Data[i] > Data[i + 1] THEN		EThe inner loop: it compares neighbours, and its bound shrinks after each pass
6 ENDIF NEXT Pass NEXT i		FIF Data[i] > Data[i + 1] THEN Temp ← Data[i] Data[i] ← Data[i + 1] Data[i + 1] ← Temp ENDIF

Definitions

FOR Pass ← 1 TO n - 1

Fill in the Blanks

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

FOR Pass ← 1 TO _____ FOR i ← 1 TO n - Pass IF List[i] > List[i + 1] THEN

FOR Pass ← 1 TO n - 1 FOR i ← 1 TO n - ____ IF List[i] > List[i + 1] THEN

FOR i ← 1 TO n - Pass IF List[i] _ List[i + 1] THEN Temp ← List[i]

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

_____ NEXT i NEXT Pass

Spot the Error

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

Question 1

A FOR Pass ← 1 TO n - 2

B FOR i ← 1 TO n - Pass

C CALL CompareSwap(A, i)

D NEXT i

E NEXT Pass

Question 2

A FOR Pass ← 1 TO n - 1

B FOR i ← 1 TO n - Pass

C CALL CompareSwap(A, Pass)

D NEXT i

E NEXT Pass

Question 3

A FOR Pass ← 1 TO n - 1

B FOR i ← 1 TO Pass

C CALL CompareSwap(A, i)

D NEXT i

E NEXT Pass

Question 4

A n ← 8

B FOR Pass ← 2 TO n - 1

C FOR i ← 1 TO n - Pass

D CALL CompareSwap(A, i)

E NEXT i

F NEXT Pass

Question 5

A FOR Pass ← 1 TO n - 1

B FOR i ← 1 TO n - Pass

C CALL CompareSwap(A, i)

D NEXT Pass

E NEXT Pass

Answer Key

Bubble sort with nested FOR loops

Section A: Quick Questions

B — FOR Pass ← 1 TO n - 1

A — 5 times

A — FOR Index ← 1 TO n - Pass

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

A — The largest unsorted value has bubbled to the end and is already in place

Section B: Match the Pairs

FOR Pass ← 1 TO n - 1 → The outer loop: it repeats the pass through the array n - 1 times

FOR i ← 1 TO n - Pass → The inner loop: it compares neighbours, and its bound shrinks after each pass

Inside the inner loop, compare two neighbours and swap them if they are out of order → IF Data[i] > Data[i + 1] THEN Temp ← Data[i] Data[i] ← Data[i + 1] Data[i + 1] ← Temp ENDIF

Close the blocks in the right order: ENDIF first, then the inner NEXT, then the outer NEXT → ENDIF NEXT i NEXT Pass

FOR Pass ← 1 TO n FOR i ← 1 TO n - Pass IF Data[i] > Data[i + 1] THEN → The outer loop runs to n instead of n - 1, so it does one pass too many

ENDIF NEXT Pass NEXT i → The NEXT statements are in the wrong order: the loops are not closed from the inside out

Section C: Definitions

FOR Pass ← 1 TO n - 1 — Outer loop of a bubble sort: it runs n - 1 passes. Inside it, an inner FOR loop compares neighbours and swaps them if out of order, so the whole array ends up sorted.

Section D: Fill in the Blanks

FOR Pass ← 1 TO n - 1
   FOR i ← 1 TO n - Pass
      IF List[i] > List[i + 1] THEN

FOR Pass ← 1 TO n - 1
   FOR i ← 1 TO n - Pass
      IF List[i] > List[i + 1] THEN

FOR i ← 1 TO n - Pass
   IF List[i] > List[i + 1] THEN
      Temp ← List[i]

Temp ← List[i]
List[i] ← List[i + 1]
List[i + 1] ← Temp

      ENDIF
   NEXT i
NEXT Pass

Section E: Spot the Error

A — The outer loop must run n - 1 passes. With n - 2 it stops one pass early, so the array may not be fully sorted. It should be FOR Pass ← 1 TO n - 1.

C — The inner loop must compare the neighbours at the inner loop counter i. Using Pass compares the same position every time. It should be CALL CompareSwap(A, i).

B — The inner loop bound should shrink as the passes go on, so it must be n - Pass. Using Pass makes it grow instead. It should be FOR i ← 1 TO n - Pass.

B — The outer loop must start at 1 to give n - 1 passes. Starting at 2 gives only n - 2 passes, so the array may not be sorted. It should be FOR Pass ← 1 TO n - 1.

D — The inner loop must be closed with NEXT i before the outer loop is closed. The loops must be closed in the reverse order they were opened. It should be NEXT i.