Selection sort in Python

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. What does the inner loop of a selection sort do?

A Swaps every pair of neighbouring items

B Finds the smallest item in the unsorted part of the list

2. What does the outer loop of a selection sort go through?

A Each position in the list, one at a time

B Only the last position in the list

3. Which line correctly swaps two items in a Python list?

A nums[i], nums[m] = nums[m], nums[i]

B nums[i] = nums[m] and nums[m] = nums[i]

4. After the first pass of a selection sort on [5, 2, 9, 1], what is the list?

A [2, 5, 1, 9]

B [1, 2, 9, 5]

5. Which inner loop correctly checks only the unsorted items after position i?

A for j in range(i + 1, len(nums)):

B for j in range(0, i):

Match the Pairs

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

Left column		Right column
1for i in range(len(nums)):		ASwaps the item at position i with the smallest item found at position m.
2nums[i], nums[m] = nums[m], nums[i]		BThe outer loop: it goes through each position in the list, one at a time, to fill with the smallest remaining item.
3The inner loop searches the unsorted part of the list to find the position of the smallest item.		CThis is a bad swap. The first line overwrites nums[i], so its original value is lost and both items end up the same.
4When the inner loop finds a smaller item, remember its position as the new minimum.		Dif nums[j] < nums[m]: m = j
5nums[i] = nums[m] nums[m] = nums[i]		EThe inner loop always sets m to j without comparing, so m just ends up as the last position instead of the smallest item.
6for j in range(i, len(nums)): m = j		Ffor j in range(i + 1, len(nums)):

Definitions

selection sort

Fill in the Blanks

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

for i in _____(len(nums)): smallest = i

for j in range(_____, len(nums)):

if nums[j] _ nums[smallest]: smallest = j

a[i], a[_] = a[m], a[i]

for i in range(len(nums)): smallest = _ for j in range(i + 1, len(nums)):

Spot the Error

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

Question 1

A for i in range(n - 1):

B m = i

C for j in range(i - 1, n):

D if a[j] < a[m]:

E m = j

F a[i], a[m] = a[m], a[i]

Question 2

A n = len(a)

B for i in range(n - 1):

C m = 0

D for j in range(i + 1, n):

E if a[j] < a[m]: m = j

F a[i], a[m] = a[m], a[i]

Question 3

A a = [4, 1, 3]

B a[0], a[1] = a[0], a[1]

C print(a)

Question 4

A for i in range(n - 1)

B m = i

C for j in range(i + 1, n):

D if a[j] < a[m]:

E m = j

F a[i], a[m] = a[m], a[i]

Question 5

A n = length(a)

B for i in range(n - 1):

C m = i

D for j in range(i + 1, n):

E if a[j] < a[m]: m = j

F a[i], a[m] = a[m], a[i]

Answer Key

Selection sort in Python

Section A: Quick Questions

B — Finds the smallest item in the unsorted part of the list

A — Each position in the list, one at a time

A — nums[i], nums[m] = nums[m], nums[i]

B — [1, 2, 9, 5]

A — for j in range(i + 1, len(nums)):

Section B: Match the Pairs

for i in range(len(nums)): → The outer loop: it goes through each position in the list, one at a time, to fill with the smallest remaining item.

nums[i], nums[m] = nums[m], nums[i] → Swaps the item at position i with the smallest item found at position m.

The inner loop searches the unsorted part of the list to find the position of the smallest item. → for j in range(i + 1, len(nums)):

When the inner loop finds a smaller item, remember its position as the new minimum. → if nums[j] < nums[m]: m = j

nums[i] = nums[m] nums[m] = nums[i] → This is a bad swap. The first line overwrites nums[i], so its original value is lost and both items end up the same.

for j in range(i, len(nums)): m = j → The inner loop always sets m to j without comparing, so m just ends up as the last position instead of the smallest item.

Section C: Definitions

selection sort — A sorting algorithm that uses nested loops to find the smallest remaining item, then swaps it into place with a, b = b, a. It repeats for each position until the list is sorted.

Section D: Fill in the Blanks

for i in range(len(nums)):
    smallest = i

for j in range(i + 1, len(nums)):

if nums[j] < nums[smallest]:
    smallest = j

a[i], a[m] = a[m], a[i]

for i in range(len(nums)):
    smallest = i
    for j in range(i + 1, len(nums)):

Section E: Spot the Error

C — The inner loop must only check the unsorted items after position i, so it should start at i + 1. Starting at i - 1 looks back at the sorted part (and at -1 when i is 0).

C — m holds the index of the smallest item found so far in the unsorted part. It must start at i, the current position, not at 0, which is the start of the whole list.

B — This line does not swap anything because both values are put back where they came from. A swap needs the right side reversed: a[0], a[1] = a[1], a[0].

A — A for statement must end with a colon. It should be: for i in range(n - 1):

A — Python has no length() function for lists. The built-in is len(), so the line should be n = len(a).