Stack level too deep for quicksort code

Ruby
1

Hi, below is my quicksort implementation in ruby(using the first element
as pivot).

def quicksort(items)
return items if items.nil? or items.length <= 1

first=items[0]

left,right=parti(items,0,items.length)

quicksort(left) + [first] + quicksort(right)

end

def parti(s,l,r)
p=s[l]
i=l+1
(l+1…r).each do |x|
if s[x] < p
s[x],s[i] = s[i],s[x]
i+=1
end
end
s[l],s[i-1] = s[i-1],s[l]
return [s[0…i-2],s[i…r]]
end

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?

2

On Jun 28, 2012, at 16:02 , bei zhao wrote:

I tried to add puts after
left,right=parti(items,0,items.length)
and see iterate outputs.

Any thoughts?

Write tests.

Start with an empty array, then 1, then 2, then many.

3

Ryan D. wrote in post #1066579:

On Jun 28, 2012, at 16:02 , bei zhao wrote:

I tried to add puts after
left,right=parti(items,0,items.length)
and see iterate outputs.

Any thoughts?

Write tests.

Start with an empty array, then 1, then 2, then many.

And add in lots of prints, for example at the start of each function,
perhaps also just before it returns.

def quicksort(items)
puts “Entering quicksort(#{items.inspect})”
…

Add more in as you home in on where the problem is.

4

By the way, this low level element swapping isn’t necessary in Ruby. The
whole parti method can be replaced by Enumerable#partition:

Then the code becomes as simple as this:

def quicksort array
return array if array.empty?
pivot = array.first
left, right =
array[1…-1].partition {|x| x < pivot}
quicksort(left) + [pivot] + quicksort(right)
end

5

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 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.

6

Lars H. wrote in post #1066622:

How about:

pivot = array.shift
left, right = array.partition {|x| x < pivot}

I wouldn’t do it. This removes the first element from the original
array, which will make no sense to the user.

7

On 06/29/2012 11:28 AM, Jan E. wrote:

pivot = array.first
left, right =
array[1…-1].partition {|x| x < pivot}

How about:

pivot = array.shift
left, right = array.partition {|x| x < pivot}

8

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?

9

On 06/29/2012 02:32 PM, Jan E. wrote:

Lars H. wrote in post #1066622:

How about:

pivot = array.shift
left, right = array.partition {|x| x < pivot}

I wouldn’t do it. This removes the first element from the original
array, which will make no sense to the user.

The only time the array is referenced later in the method is when you
partition all except the first element, so it makes perfect sense to me.

10

Updates:

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.

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.

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.

Thanks everyone who read and replied

11

Lars H. wrote in post #1066738:

The only time the array is referenced later in the method is when you
partition all except the first element, so it makes perfect sense to me.

I’m talking about the original array you want to sort. When you pass it
to the method, it will lose its first element:

my_array = [3, 1, 5, 2]
sorted = quicksort(my_array) # get a sorted copy
p my_array # WTF? my_array has suddenly become [1, 5, 2]

I’d actually call this a bug. The method should either sort the original
array, or it should not touch the original array at all and only return
a new sorted array. I think the second option makes more sense for a
function style method.

But your method would return a new sorted array and at the same time
somewhat corrupt the original one.

12

On 06/30/2012 03:09 PM, Jan E. wrote:

I’d actually call this a bug. The method should either sort the original
array, or it should not touch the original array at all and only return
a new sorted array. I think the second option makes more sense for a
function style method.

But your method would return a new sorted array and at the same time
somewhat corrupt the original one.

Ah, now I see what you mean. Good call.