From: "Jan E." <lists@...>
Date: 2012-06-29T17:32:00+09:00
Subject: Re: stack level too deep for quicksort code

Hi,

alex zz wrote in post #1066577:
> But it shows stack level too deep error.
> I tried to add puts after
> left,right=parti(items,0,items.length)
> and see iterate outputs.
>
> Any thoughts?

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)

rather than

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 need the indices at all. 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.

-- 
Posted via http://www.ruby-forum.com/.