Course 1 Week 3 n=5 test case error?
Closed this issue · 2 comments
I'm looking at the fifth test case for n=5, https://github.com/beaunus/stanford-algs/blob/master/testCases/course1/assignment3Quicksort/input_dgrcode_05_5.txt
According to https://github.com/beaunus/stanford-algs/blob/master/testCases/course1/assignment3Quicksort/output_dgrcode_05_5.txt quicksort using the first element as pivot should result in 7 comparisons.
My code says it should be 6, and I've verified it manually.
If you start with [4, 5, 2, 3, 1] then your initial pivot is 4, you make 4 comparisons and you end up with [ 2, 3, 1, 4, 5].
On the left side you call the partition subroutine on [2,3,1] which uses 2 as its pivot and makes 2 more comparisons (6 total comparisons). You end up with [1,2,3] and you call the partition subroutine on the [1] and the [3] which both trigger the base case and result in no further comparisons.
On the right side you call the partition subroutine on just the [5] which also triggers the base case and makes no further comparisons.
Nm, apparently i'm supposed to be swapping the pivot with the rightmost element less than it rather than popping it off the list and inserting it at index i.
@sandramchung Thank you for interest in supporting this project. Cheers!