Re: stack level too deep for quicksort code

alex zz wrote in post #1066643:
> Actually the reason I skipped the 7-line solution and did this low level
> implementation is by the requirement of the course. I'm following
> algorithm class on coursera.

OK. But you should still get rid of "l" and "r", because these 
parameters are completely senseless in your case. They make it look like 
you just throw together some code fragments you've seen earlier without 
really understanding what they do and why.

Like a said: This is for in-place sorting. If you operate on the 
original array, you have to know where the current part of the array 
begins and ends. But in your case you're operating on actual subarrays, 
so those information are obviously not needed. You can also see this 
from the code: l is alyways 0, and r is always the last index of the 
array.



> It's true that array like [1,2] will break parti, because it will swap
> array[0] with array[i-1], basically array[0] it self.

No, that's not the problem. This simply has no effect. The problem 
occurs when i is never incremented and stays 1. In this case the left 
subarray s[1..i-2] becomes s[1..-1], which is the complete original 
array.



> I change the code to
>
> if i-2>=0
>   return s[0..i-2],s[i..r]
> else
>   return Array.new,s[i..r]
> end
>
> now it works.

Yeah, but this is rather a workaround. Why don't you simply leave out 
the swapping like I suggested earlier?

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