Tracing a selection sort

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. In a selection sort trace, where does the sorted part of the array grow from?

A The right end of the array

B The left end of the array

2. Trace one pass of selection sort on [5, 3, 8, 1]. What does the array look like after pass 1?

A [1, 3, 8, 5]

B [3, 5, 1, 8]

3. How many swaps does selection sort make in each pass?

A One swap per pass

B One swap for every pair compared

4. Array after pass 1 is [1, 6, 4, 9, 2]. Which item will be swapped into position 2 on pass 2?

A 4, because it is next to the 6

B 2, because it is the minimum of [6, 4, 9, 2]

5. During a pass, what does a trace table record besides the array?

A The index of the minimum found in the unsorted part

B The index of the largest item in the whole array

Match the Pairs

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

Left column		Right column
1minIndex ← i		A[1, 2, 8, 5]
2SWAP numbers[i], numbers[minIndex]		BMake the one swap for this pass, putting the minimum at the end of the sorted part
3Trace of [5, 2, 8, 1] after pass 1: the minimum 1 at index 4 is swapped with the first item, so the sorted part is [1]		C[1, 2, 8, 5]
4After pass 2 of [1, 2, 8, 5], the minimum of the unsorted part is already in place, so the swap changes nothing and the sorted part grows to two		DThe sorted part grows by one item each pass from the left, so after pass 2 it holds two items and never shrinks.
5Pass 1 of [4, 3, 1, 2] traced as [3, 4, 1, 2]		EThis swaps only the first two items, as a bubble sort would. Selection sort swaps the first item with the minimum, 1, giving [1, 3, 4, 2].
6Trace row for pass 2 shows the sorted part shrinking from [1, 2] to [1]		FAssume the first unsorted item is the smallest at the start of each pass

Definitions

trace table

Fill in the Blanks

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

FOR i ← 1 TO _____ minIndex ← i FOR j ← i + 1 TO n

FOR i ← 1 TO n - 1 minIndex ← _ FOR j ← i + 1 TO n

IF data[j] _ data[minIndex] THEN minIndex ← j ENDIF

temp ← data[i] data[i] ← data[________] data[minIndex] ← temp

Start: [5, 3, 8, 1] Pass 1: [_, 3, 8, 5] Pass 2: [1, 3, 8, 5]

Spot the Error

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

Question 1

A Start: [5, 3, 8, 1]

B Pass 1: [1, 5, 3, 8]

C Pass 2: [1, 3, 8, 5]

D Pass 3: [1, 3, 5, 8]

Question 2

A Start: [4, 2, 7, 1]

B Pass 1: [1, 4, 7, 2]

C Pass 2: [1, 2, 7, 4]

D Pass 3: [1, 2, 4, 7]

Question 3

A FOR i ← 2 TO n - 1

B min ← i

C FOR j ← i + 1 TO n

D IF A[j] < A[min] THEN

E min ← j

F swap A[i], A[min]

Question 4

A Array: [6, 2, 9, 4]

B Pass 1: min is 2 at index 2

C Pass 2: min is 2 at index 1

D Pass 3: min is 6 at index 4

Question 5

A min ← A[i]

B FOR j ← i + 1 TO n

C IF A[j] < A[min] THEN

D min ← j

Answer Key

Tracing a selection sort

Section A: Quick Questions

B — The left end of the array

A — [1, 3, 8, 5]

A — One swap per pass

B — 2, because it is the minimum of [6, 4, 9, 2]

A — The index of the minimum found in the unsorted part

Section B: Match the Pairs

minIndex ← i → Assume the first unsorted item is the smallest at the start of each pass

SWAP numbers[i], numbers[minIndex] → Make the one swap for this pass, putting the minimum at the end of the sorted part

Trace of [5, 2, 8, 1] after pass 1: the minimum 1 at index 4 is swapped with the first item, so the sorted part is [1] → [1, 2, 8, 5]

After pass 2 of [1, 2, 8, 5], the minimum of the unsorted part is already in place, so the swap changes nothing and the sorted part grows to two → [1, 2, 8, 5]

Pass 1 of [4, 3, 1, 2] traced as [3, 4, 1, 2] → This swaps only the first two items, as a bubble sort would. Selection sort swaps the first item with the minimum, 1, giving [1, 3, 4, 2].

Trace row for pass 2 shows the sorted part shrinking from [1, 2] to [1] → The sorted part grows by one item each pass from the left, so after pass 2 it holds two items and never shrinks.

Section C: Definitions

trace table — A table of the array after each selection sort pass: the minimum of the unsorted part is swapped to the left, so the sorted part grows by one each pass.

Section D: Fill in the Blanks

FOR i ← 1 TO n - 1
  minIndex ← i
  FOR j ← i + 1 TO n

FOR i ← 1 TO n - 1
  minIndex ← i
  FOR j ← i + 1 TO n

IF data[j] < data[minIndex] THEN
  minIndex ← j
ENDIF

temp ← data[i]
data[i] ← data[minIndex]
data[minIndex] ← temp

Start:  [5, 3, 8, 1]
Pass 1: [1, 3, 8, 5]
Pass 2: [1, 3, 8, 5]

Section E: Spot the Error

B — Selection sort makes one swap per pass. The minimum (1) swaps places with the first item (5), giving [1, 3, 8, 5]. The other items do not shift along.

B — Pass 1 makes one swap: the minimum (1) swaps with the first item (4). That gives [1, 2, 7, 4]. The 2 stays where it is.

A — The outer loop must start at 1 so the first pass puts the smallest item at index 1. Starting at 2 skips that pass. It should be FOR i ← 1 TO n - 1.

C — After pass 1 the array is [2, 6, 9, 4] and index 1 is already sorted. Pass 2 searches only the unsorted part, where the minimum is 4 at index 4.

A — The variable min stores the index of the smallest item, not its value. It is compared using A[min], so it must start as min ← i.