I need to reproduce this quicksort pseudocode in a closed-book exam, but I struggle especially with the partition function. It chooses the first element as the pivot, scans inward with two pointers, swaps values that are on the wrong side of the pivot, then places the pivot in its final position. How can I understand and actively recall these steps instead of memorizing the code line by line?
3 Answers
You can also remember the larger design choices. Quicksort uses divide and conquer and is usually in-place, unlike a version that creates two new subarrays. Its average performance is O(n log n), but repeatedly choosing the smallest or largest remaining value can produce O(n²) behavior. It is also not stable, meaning equal elements may change their relative order. These properties help explain why the algorithm is structured the way it is, instead of treating it as an isolated block of code.
For this version of partition, remember the roles of the pointers: the pivot is the first element, i starts just after it, and j starts at the end. Move i right while its values are less than or equal to the pivot. Move j left while its values are greater than the pivot. If the pointers have not crossed, swap those two values because they are on the wrong sides. Once they cross, swap the pivot with the value at j. That final swap puts the pivot in its sorted position, so the function returns j. A useful checklist is: scan from both ends, swap misplaced values, then place the pivot.
Focus on the algorithm’s purpose rather than memorizing exact syntax. Quicksort recursively chooses a pivot, rearranges the array so smaller values are on one side and larger values are on the other, then repeats the process on both resulting sections. If you can describe those steps in plain English, you should be able to recreate the code in whatever language the exam uses.
I probably need to work on understanding the process more deeply first, because active recall is difficult when I do not fully understand the partition step.