alex zz wrote in post #1066577:
But it shows stack level too deep error.
I tried to add puts after
and see iterate outputs.
The parti method fails for two element arrays, which are already
ordered. In this case the method will just return the original array and
force quicksort into an endless loop.
As an example:
You have parti([1, 2], 0, 1)
i will start with 1. Since the second element is not smaller than the
first one, the each iterator will do nothing. The same goes for the
swapping. But when you create the two subarrays, you will run into
trouble: i - 2 is -1, so the left subarray will be from the first
element to the last (negative indices count from right to left,
beginning with -1). This results in the original array [1, 2].
The solution would be to simply leave out the swapping (which seems
senseless to me, anyway) und take s[1 … i - 1] as the left subarray.
By the way, in the quicksort method it should say
left, right= parti(items, 0,items.length - 1)
left, right= parti(items, 0, items.length)
But I guess you already corrected that, because otherwise the method
wouldn’t have worked at all.
Actually you don’t even need the indices. It seems you mixed up two
different quicksort approaches: operating on the original array (called
“in-place”) and creating subarrays like you do. You only need the
indices if you do in-place sorting.