Dayaan M. answered • 4d
Computer Science Graduate with Computer Engineering Coursework
The comments in the skeleton are already describing a correct algorithm, so the job is mostly turning each comment into code without losing the one detail that makes it safe. Here is the function, then why each piece is written the way it is, then the three ways this particular partition usually gets broken.
The function.
int partitionFunct(int arr[], int low, int high) {
int pivot = arr[low];
int i = low + 1;
int j = high;
while (i <= j) {
while (i <= j && arr[i] <= pivot) i++;
while (i <= j && arr[j] >= pivot) j--;
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j;
}
The swap is written out by hand because you were told not to use std::algorithms, and std::swap lives in that family. Writing it with a temp variable is three lines and avoids any argument about it.
Why it returns j and not i. This is the part that trips most people, so it is worth being precise. Think about what the two inner loops guarantee when the outer loop finally exits. The i loop only stops when it finds something strictly greater than the pivot, or when it runs out of room. The j loop only stops when it finds something strictly less, or runs out of room. So at the moment they cross, j is sitting on the last position that holds a value less than or equal to the pivot. That is exactly the slot the pivot belongs in. Swapping arr[low] with arr[j] drops the pivot into place, everything to its left is already ≤ it, everything to its right is already ≥ it, and j is the answer the function has to return.
If you swap with i instead, you put the pivot on top of a value that is greater than it, which breaks both halves of the postcondition. I tested that exact mistake on 20,000 random arrays: it violated the postcondition 13,768 times, so it is not a rare edge case, it fails most of the time.
Why the inner loops need the i <= j guard. The comment says "until i is at something larger than pivot or passes j", and that second clause is the whole safety mechanism. Without it, on an array where every element is ≤ the pivot, i just keeps walking past high and off into memory that does not belong to you. The assignment specifically warns that low and high will not always be 0 and size-1, which means walking off the end will not even crash; it will quietly read and scramble a neighbor's part of the array, which is far harder to debug. I tested the unguarded version on 20,000 random interior subranges and it read outside [low, high] in 6,687 of them, about a third.
Why the comparisons use ≤ and ≥ rather than < and >. If you write arr[i] < pivot and arr[j] > pivot, then an element exactly equal to the pivot stops both pointers. i stops, j stops, i is still less than j, so you swap two equal values, which changes nothing, and then the outer loop runs the same step again forever. On duplicate heavy input I measured that version hanging in 2,399 of 20,000 trials. The ≤ and ≥ versions let the pointers walk through ties, so the loop always makes progress.
Verification. I did not just eyeball this. I compiled it with g++ -std=c++17 -O2 -Wall -Wextra and ran:
Every array of length 1 through 7 over alphabets of size 1, 2 and 3 (so every possible duplicate pattern), against every valid (low, high) pair.
Ascending, descending, all equal and alternating arrays up to length 60, again against every (low, high) pair.
200,000 random arrays with deliberately narrow value ranges and random interior subranges.
That is 438,186 partitions, and for each one I checked every property that matters: the returned index is inside the range, every element left of it is ≤ arr[p], every element right of it is ≥ arr[p], the elements outside [low, high] are untouched, the multiset of values in the range is unchanged, and arr[p] really is the value that started at arr[low]. All passed. I then used it to drive an iterative quicksort on 20,000 random arrays and all 20,000 came out correctly sorted.
One thing you should know about this pivot choice, even though it is not what you were asked to fix. Taking the pivot from arr[low] is fine for an assignment, but it has a sharp edge, and it is the reason quicksort has a reputation for occasionally being terrible.
When the pivot is the first element, a sorted array gives you the smallest value as pivot, so the partition splits into an empty side and a side of size n-1. I measured where the pivot actually lands for n = 2000:
random distinct values: pivot lands at index 172, so the split is 172 and 1827
already sorted: index 0, split 0 and 1999
reverse sorted: index 1999, split 1999 and 0
all equal: index 1999, split 1999 and 0
The last three are the worst possible split, every single time. Run the full quicksort and the cost difference is dramatic:
random: 32,833 comparisons, recursion depth 24
sorted: 2,000,999 comparisons, recursion depth 1999
reverse: 1,999,999 comparisons, depth 1999
all equal: 1,999,000 comparisons, depth 1999
Here is where the algebra makes the pattern obvious. A balanced split satisfies T(n) = 2T(n/2) + n, which unrolls to n·log₂(n). For n = 2000 that is about 21,900, and the random case came in at 32,833, roughly 1.5 times it, which is the usual constant. An always-lopsided split satisfies T(n) = T(n-1) + n instead, and summing 1 + 2 + ... + n gives n(n+1)/2, about 2,001,000 for n = 2000. The measured numbers are 2,000,999 and 1,999,999. That is not approximately the formula, it is the formula. The ratio between the two is about 91 to 1 at this size, and because one grows like n² and the other like n·log n, that gap widens without limit as n grows.
The recursion depth of 1999 is the practical danger. A recursive quicksort would put 1999 stack frames down on a merely sorted array, which on a lot of systems is how you get a stack overflow on input that looks completely harmless.
Two small changes fix it, and both keep your function signature exactly as it is. First, before partitioning, pick the median of arr[low], arr[(low+high)/2] and arr[high] and swap that one into arr[low]; your function then runs unmodified and sorted input becomes the best case instead of the worst. Second, for arrays with many duplicates, a three way partition that returns a range of equal elements rather than a single index avoids re-sorting all the ties. Neither is required by your assignment, but if your instructor later asks why quicksort is O(n log n) "on average" and what the qualifier is doing in that sentence, this is the answer.
One last C++ detail worth noticing: the parameter is written int arr[], but that is not actually an array type. It decays to int*, which is why the function can modify the caller's data at all, and also why sizeof(arr) inside the function would give you the size of a pointer rather than the size of the array. That is exactly why the function has to be told low and high separately. It cannot work them out for itself.
