Presentation: Unplugged Algorithms: Sorting Networks

Slide 1 of 7 · Settling starter · Computer Science · Year 7

3 minutes

Unplugged algorithms: sorting networks

A sorting network is an algorithm you can walk through. 6 numbers go in on the left, and if everybody obeys the same 3 rules, the numbers always come out in order on the right, without anybody being in charge and without anybody seeing more than 2 numbers at a time.

While the register is called: write your name, class and date on your worksheet, then read the 3 rules on the stimulus sheet, The six-wire sorting network.

Starter question: When 2 pupils meet at a coloured bar, which number takes the higher wire?

DCF: Data and computational thinking → Problem-solving and modelling No computers needed · pencil, cards and the stimulus sheet

Slide 2 of 7 · Today’s brief and key words · Computer Science · Year 7

2 minutes

Your brief: trace it, test it, then build a smaller one

Step 1: say the 3 rules back to your partner without looking. Today you will fill in a trace table for Card set B, do 3 tests that try to break the network, design a 3-wire network of your own and answer 4 counting questions.

Wire

One of the 6 lines, numbered 1 (top) to 6 (bottom). You only ever move along your own wire, left to right.

Comparator

A coloured bar joining 2 wires. (2,4) means the pupils on wires 2 and 4 compare cards. There are 12 of them.

Step

A group of comparators that all happen at the same time. The network has 5 steps.

Step 1 on your worksheet · 5 minutes with the starter Follow the rules exactly, even when it looks wrong

Slide 3 of 7 · Step 2: trace the network once · Computer Science · Year 7

10 minutes

Step 2: walk or finger-trace the network with Card set B

Put 12, 46, 25, 33, 51, 18 on wires 1 to 6 in that order. Go through the 5 steps using the table of comparators on the stimulus sheet. Nothing moves except at a coloured bar.

Step	Comparators in that step (all at the same time)
Step 1	(1,6) (2,4) (3,5)
Step 2	(2,3) (4,5)
Step 3	(1,4) (3,6)
Step 4	(1,2) (3,4) (5,6)
Step 5	(2,3) (4,5)

Step 2 on your worksheet · 10 minutes Smaller number up, larger number down

Slide 4 of 7 · Step 3: the trace table · Computer Science · Year 7

15 minutes

Step 3: fill in the trace table, one row per step

After each step, write what is on each wire. Write down every comparison you make, including the ones where nothing moves. Then write out the comparison that surprised you most, and say why.

After	Wire 1	Wire 2	Wire 3	Wire 4	Wire 5	Wire 6
Start	12	46	25	33	51	18
Step 1 · (1,6) (2,4) (3,5)	12	33	25	46	51	18

Step 3 on your worksheet · 15 minutes Someone else should be able to check your work from the table

Supply teacher script (no subject knowledge needed)

Say aloud: “15 minutes. The start row and step 1 are on the board. Fill in steps 2 to 5 on your sheet. Under the table, write the comparison that surprised you most and why.”

Quick check: after step 2: 12, 25, 33, 46, 51, 18. After step 3: 12, 25, 18, 46, 51, 33. After step 4: 12, 25, 18, 46, 33, 51. After step 5: 12, 18, 25, 33, 46, 51. Swaps happen at (2,4) in step 1, (2,3) in step 2, (3,6) in step 3, (5,6) in step 4, and (2,3) and (4,5) in step 5; the other 7 comparisons leave things alone.

Surprise answer: the worked example picks step 3: the top 4 wires held 12, 25, 33, 46 in order, but (3,6) pulled 18 up into wire 3 and pushed 33 down, making it look worse for a moment. It only came right in step 5. A step does not have to improve things, it has to move the right numbers into reach of the next comparators.

Slide 5 of 7 · Step 4: does it always work? · Computer Science · Year 7

10 minutes

Step 4: 3 tests, each one trying to break the network

Trace each input through all 5 steps and write what came out, and what that tells you.

Test	Input on wires 1 to 6
Test 1: worst case. Put the numbers in backwards.	51, 46, 33, 25, 18, 12
Test 2: already sorted. How many swaps happen?	12, 18, 25, 33, 46, 51
Test 3: repeats. Does “the smaller number goes up” still say what to do when both cards are the same?	3, 3, 7, 1, 7, 1

Step 4 on your worksheet · 10 minutes Explain the result, do not just record it

Supply teacher script (no subject knowledge needed)

Say aloud: “10 minutes, about 3 minutes a test. Each test is an awkward input. Trace it all the way through, write what comes out, then write what it tells you about the network.”

Quick check: Test 1 comes out 12, 18, 25, 33, 46, 51. Step 1 swaps all 3 pairs giving 12, 25, 18, 46, 33, 51, step 2 swaps both pairs and it is sorted; steps 3 to 5 have nothing to do. The worst input for a person is not the worst for this network. Test 2 comes out unchanged with zero swaps, but all 12 comparisons still happen: no comparator knows what any other found, so the network always does the same amount of work. Test 3 comes out 1, 1, 3, 3, 7, 7. When cards are equal, neither is smaller, so nobody moves; either choice would give the same answer, so repeats are safe.

Slide 6 of 7 · Step 5 and self check · Computer Science · Year 7

7 minutes

Step 5: design a 3-wire network, answer the counting questions, then check

Draw the comparators you need on the 3-wire grid, test it with 3 on wire 1, 1 on wire 2 and 2 on wire 3, and write the comparators as pairs underneath in order. Answer the 4 counting questions. Then tick the criteria you have met and correct 1 thing.

I followed the algorithm exactly as written instead of just sorting the numbers in my head.
My trace table records the state of all 6 wires after every step, so someone else could check my work.
I tested the algorithm with awkward inputs: reversed, already sorted, and with repeated values.
I designed a smaller network of my own and tested it rather than assuming it worked.
I can explain why doing several comparisons at the same time makes the job finish sooner, even though it does not do fewer comparisons.

Step 5 on your worksheet · 7 minutes, then self check Finished early? Trace Card set A, the Welsh mountains

Supply teacher script (no subject knowledge needed)

Say aloud: “Draw a 3-wire network on the grid. Test it with 3, 1, 2 on wires 1 to 3. Answer the 4 counting questions. Then tick the success criteria you have met and correct 1 thing, for example a row in the trace table where a card moved without a bar.”

Quick check: a working 3-wire design is (1,2) (2,3) (1,2): 3, 1, 2 becomes 1, 3, 2, then 1, 2, 3, then stays 1, 2, 3. Counting: 1. 12 comparators (3 + 2 + 2 + 3 + 2). 2. 5 steps, because comparators in one step never share a wire. 3. 6 × 5 ÷ 2 = 15; the network does only 12, and only 5 steps instead of 15 because up to 3 happen at once. 4. 3 comparators; with only (1,2) then (2,3), the input 2, 3, 1 comes out 2, 1, 3, which is wrong.

Extension answers: Card set A (1085, 893, 886, 905, 1001, 915) comes out 886, 893, 905, 915, 1001, 1085, so wire 1 holds 886 m, Pen y Fan; Yr Wyddfa reached wire 6 in step 1 and never moved again. A 4-wire network needs 5 comparators. Turning one comparator round breaks the network; the pupil must give an input that comes out wrong as proof.

Slide 7 of 7 · Plenary review · Computer Science · Year 7

3 minutes

Quick-check answers before handing in

Check your main answers before your worksheets are collected.

Question	Correct answer
What comes out when Card set B goes in as 12, 46, 25, 33, 51, 18?	12, 18, 25, 33, 46, 51
How many comparators, and how many steps, in the 6-wire network?	12 comparators in 5 steps.
How many swaps happen when the numbers go in already sorted?	Zero, but all 12 comparisons still happen.

Check your name and class are on your worksheet Number cards back in the stimulus sheet, sheets left neat