Quick Sort Equal to or Less Than

Question

For my course I have to memorise a number of algorithms and to know how to perform them by hand. The steps of the quick sort are given as the following in the text book I am using:

1. Choose the item at the midpoint of the list to be the first pivot
2. Write down all the items that are less than the pivot, keeping them in order, in a sub-list
3. Write down the pivot
4. Write down the remaining items (those greater than the pivot) in a sub-list
5. Apply steps 1 to 4 to each sub-list
6. When all items have been chosen as pivots, stop

The problem is that these instructions are ambiguous as to what to do if there is an item which is equal to the pivot. Does it fall into the first sub-list (written before the pivot) or the second (written after the pivot)? I assume that there is some sort of agreed upon standard for this.

Answer 1

It doesn't really matter which way you decide to break the tightness. You could put all the elements less than or equal to the pivot in the first list and the ones larger than the pivot in the second list, or you could put only the elements smaller than the pivot in the fist list and the ones larger than or equal to the pivot in the second list.

You could even arbitrarily pick the list that will contain an element equal to the pivot (except the pivot itself), on an element-to-element basis. No matter how you will assign these elements to the lists, the algorithm will still work.

Another solution that slightly breaks the algorithm's description you gave is to put all elements smaller than the pivot in the first list $L_1$, all those larger than the pivot in the second list $L_2$, and insert as many copies of the pivot $x$ as there are elements equal to $x$ (including the pivot itself) between the sorted versions of $L_1$ and $L_2$.

As a final note: the pseudocode reported in your textbook seems wrong. You are supposed to recursively repeat the whole procedure on $L_1$ and $L_2$, not just steps $1$ to $4$ (otherwise you will never reach a recursion depth larger than $1$).

Answer 2

It seems the author assumed there were no two equal items, which isn't usually an assumption you should make. (those greater than the pivot) seems to be not an instruction, but just an explanation, so I would leave that out. Follow exactly what the instructions say: All items less than the pivot, then the pivot, then the remaining items (which may all be equal to the pivot, but the instructions don't care about that).

PS. Comparing using "<" vs "<=" can make a huge difference, for example if you sort a huge array where all items are equal. For that situation, you want an algorithm that handles it efficiently and not as the worst case.

PPS. It is often a very good idea to ask "what if ..." when you suspect it is something that can happen but that the algorithm designer didn't think about. Like in this case. If you write code that you designed, it is a good idea in that situation to add a comment that explains "Yes, I did think about this, and it works just fine in this case".

PPPS. This isn't at all how Quicksort is usually implemented, since it uses lots of additional space. Quicksort isn't supposed to use space except the original space of the data and a tiny bit of stack space. And you don't continue until every element has been chosen as the pivot, but until the sublists have length 0 or 1 (and lists of length 2 are likely sorted using a single comparison).