A problem with Edexcel about Quicksort

Edexcel are insisting that the order of items within each new sublist remains the same as in the previous list, though without giving any mathematical reason why this is even a good idea, let alone essential.

We’ll see if I can convince them. I’ve copied the correspondence to Ursula Martin. She is professor of computer science at Oxford University, a successor in that post to Tony Hoare, who invented the Quicksort algorithm (but is now retired).

Professor Martin writes: “Your remarks about Quicksort seem on track to me”; but, she comments ruefully, “changing the mind of Edexcel sounds a somewhat challenging proposition”.

I’ll take on the challenge. I’ve also had an email from Paul Curzon, professor of computer science at Queen Mary University of London, agreeing with me.

In the meantime, I suggest we continue with Quicksort as we’ve been doing it, so that you get the basic idea of Quicksort without the complication that Edexcel introduces.

When we come to revision, if I haven’t convinced Edexcel by then, we can discuss which of the workarounds I’ve mentioned below is best.

Below is the correspondence so far. Note also the ruling about the use of coloured pens in the exam. Coloured pens make some things in D1 much easier, but we’ll have to learn to do without them. Working with a felt-tip as well as an ordinary pen is probably the answer.


Hi,

1. Is there any objection to doing Quicksort (when written on paper as a series of lists) with the following difference from what is prescribed in the text book?

When you scan through each list, you write each item below the pivot (supposing it’s an ascending-order sort) in the next free lefthand space in the next list; and each item above the pivot in the next free righthand space.

Then, finally, you put the pivot in the last remaining free space in the next list.

This way the items above the pivot will be in the reverse of their previous order, rather than the same order as previous (as per book). That makes no difference at all to the quality of Quicksort.

On the other hand, as it stands in e.g. Example 11 of the textbook, as the student starts to scan the first list she or he has no way of telling that 37 should go in the fourth position of the next list.

There’s a workaround, of course: they write 41 in the middle of the next list, and then 37 to the right of it, and then, when they come to 44, 44 somewhere well to the left of it, to allow space for more items below the pivot.

But that’s slightly messy. Better neat and simpler.

The problem doesn’t arise in real-life implementations of Quicksort, of course, because they’re done in-place. So far as I understand it, the usual in-place implementations of Quicksort will have the items above the pivot in the same order as they were before the pass (or almost exactly so), but that’s just how it works out, not essential to the algorithm.

2. Are there regulations which prohibit the students using more than one colour pen in the exam? I notice that page 13 of the textbook says “Colours should not be used in the exam”, but there is nothing on the cover of the exam papers to prohibit using more than one colour.

I ask this with a view not to Quicksort, where extra colours don’t help much, but the graph algorithms.

Thanks,

Martin Thomas


On 08/09/14 12:15, -, ate wrote: Dear Martin

Re your first query.

There are a great many Quicksort algorithms – at least 23 of them, no to mention the ones that involve fixed and floating pivots……. If you look at past papers and mark schemes you will see that the examiners insist that the order of items within each new sub list remains the same as in the previous list. So the method you describe would not be accepted since the items would be in the reverse of their previous order. I would not advise the use of this method.

Re your second query

The papers are scanned prior to being marked electronically. The image created is in black and white, so colours are not distinguishable. Indeed some colours do not scan at all. Consequently, as stated in the examiners reports, it is not recommended that candidates use colour. The candidates are not forbidden from using colour, and there are systems in place to manage the scripts of any that do, but I would support the statements, in the examiners report, that candidates should be discouraged from using colour.

I hope this helps

Kind Regards

Susie


Hi Susie,

Thanks. I get the point about colour.

But I don’t see how the students can write the items within each sublist in the same order as in the previous list without either

a) actually doing many additional scans to Quicksort, so that e.g. with the first worked example in the book they see 37 and then scan through the entire list to see how many must go before it before placing 37 in the next row of their working;

b) writing the next row with lots of blank spaces – in that worked example, putting 41 in the middle of the next row, then 37 after it, then the first number more than 41 well over to the left to allow full space in case it turns out that all subsequent numbers are more than 41.

So, either they’re not really doing (any variant of) Quicksort, but a type of Quicksort-plus-much-extra-scanning (a prohibitive amount of extra scanning if the list were of such a length that one would want to use Quicksort on it in real life); or they have to set their work out very awkwardly.

I don’t see a good reason for insisting on that. What is the reason?

A possible workaround is that they do it the way I suggested, then after each pass rewrite the list to get the elements after the pivot in the prescribed same order. That may be better than (a) or (b) above, though not good. Would that be acceptable?

Thanks,

Martin


Dear Martin

Without loss of generality let’s assume they are putting a list into ascending order.

I suggest the following algorithm:

Identify the pivot for the sublist
Read the sublist from left to right writing down all the elements smaller than the pivot.
Then write down the pivot
Then complete the new sublist by reading the (old) sublist from left to right writing down all the elements greater than the pivot.

So if the sublist were 34 89 21 45 28 77 43
The pivot is 45
So we read the list from left to right writing down all the terms less than 45
34 21 28 43
Then add the pivot
34 21 28 43 45
Then read the list from left to right writing down all the terms greater than 45
34 21 28 43 45 89 77

I hope this helps

Susie


Hi Susie,

Thanks. Yes, that’s possible. But it demands a double scan. It corresponds to doubling the number of operations in Quicksort.

The extra labour may be trivial with the tiny lists in the D1 book, but isn’t it fundamentally miseducating the students about algorithmics? Isn’t the whole point of the exercises with tiny lists to learn how sorting can be done efficiently with big lists?

I still can see no positive reason for demanding that the items in the new sublist should be in the same order as in the previous list. Why not just change the advice to examiners?

Best wishes,

Martin


Dear Martin

It is very important that the scripts of all candidates are treated equally. The concern is that what you wish your candidates to do by intent is what other candidates do by accident. if we instruct the examiners to accept the sublists in either the ‘original’ order or ‘reverse’ order, some candidates will do a hybred of both and should that too be accepted.
This is part of what I meant by saying that there are a huge number of quick sorts.
We would end up having to accept anything, however inconsistently applied

Hence the decision to specify, through the examiners reports as well as in feedback meetings, the desire for the sublists to be in the same order as the original list.

So here is a suggestion.
You could instruct your candidates to write the left hand list as you are currently doing – that would give the sublist in the same order as the original list.
On the right hand sublist instead of starting at the right hand end of the page, could they not start ‘half way’ across the page, so again the list would be in the same order as the original list?
(I would comment that the method I described to you earlier does generate a neat looking solution with all the rows of elements in satisfying columns.).

Kind Regards

Susie


Hi Susie,

Yes, one option is to write out each successive pass with lots of free space, so that (as you say) the elements “above” the pivot are entered by filling in from the left in the right-hand half of the page.

But my objection is that it is mathematically unsound to insist on a particular order in the sublists, and it is mathematically correct that candidates’ answers should be accepted whatever order they have within the sublists. To tell the students otherwise is to miseducate them mathematically.

That’s the point on which I consulted Professor Martin, and on which she confirmed my opinion.

Best wishes,

Martin Thomas