The book says that the items in each sublist after using a pivot should be in the same order as in the original list. This is wrong: they can be in any order you like.
Edexcel don’t present any mathematical argument for why the items should be in the same order. But they insist that they have always done it that way and so the exam should make it compulsory for students to do Quicksort the wrong way and penalise them if they don’t.
Unless we can budge Edexcel by May, I’ll teach you how to do Quicksort the wrong way in the weeks before the exam. (It’s not hard). But don’t worry about it for now.
When you first scan the graph, fill in only the bottom (bigger) space in the silly set of little boxes by each vertex. Fill in the shortest path so far found to that vertex; when you find a shorter one, cross out the previous number and write the new one.
Fill in the other silly little spaces (on the upper level of each box) after you’ve finished scanning the graph. Into one little box, copy the length of the shortest path to that vertex (last number in the bigger space). Into the other little box, copy the order in which the vertices are finalised (it’s the same order as the order of their shortest paths).
Every time you finalise a vertex, mark in the edge you used to get there with the finalised shortest path with a 5B pencil.
To find the whole shortest path, just follow the 5B-pencil-marked track backwards.
To satisfy Edexcel, you must also write down the list of vertices on that shortest path, and for each edge write a calculation showing it’s on the shortest path, i.e. edge AB is on the shortest path if B is on the shortest path and shortest path to A + length AB = shortest path to B.
It’s easier to see what you’re doing if you mark each added-in alternating path with a – – – – – line, and gently cross out every path taken out. You should at the same time write the C−D=N−M stuff that the Edexcel book asks for. Do the “change status” stuff on p.154 just to reassure Edexcel. It’s a good check to write out the new bipartite graph with the complete matching at the end.
Example: suppose we have the initial matching shown for Elizabeth, Ngachung, and Conor. For some reason Conor can’t or won’t do the music, but he is willing and able to do food or drinks, and Ngachung is willing and able to do music.