CODEWITHSUNDEEP
rubyquicksort
wise_gremlin
wise_gremlin

Reputation: 443

Quick Sort Algorithm in Ruby - Stack Level Too Deep

I am trying to implement a quick sort algorithm in Ruby. I got a simple one working pretty quickly but it involved creating temporary arrays on the fly. I'm trying to implement a more streamlined quick sort that only swaps elements in place without the need to create additional arrays.

Does anyone know why this code doesn't work? I've been following the pattern laid out here in exact detail but I can't get it to work properly.

def quicksort(arr = [], left = 0, right = 0)
  right = arr.length - 1 if right < 1
  if left < right
    index = partition(arr, left, right)
    quicksort(arr, left, index - 1)
    quicksort(arr, index, right)
  end
  arr
end

def partition(arr, left, right)
  pivot = arr[(left + right) / 2]
  while left <= right
    left += 1 while arr[left] < pivot
    right -= 1 while arr[right] > pivot
    if left <= right
      arr[left], arr[right] = arr[right], arr[left]
      left += 1
      right -= 1
    end
  end
  left
end

arr = [8, 10, 13, 5, 6, 20, 2, 43, 9, 11, 15]
p quicksort(arr)

Upvotes: 1

Views: 170

Answers (3)

Najibullah Jafari
Najibullah Jafari

Reputation: 11

If you want to print every step of quick sort you can do like this:

def advanced_quicksort(arr, low = 0, high = arr.length - 1)
    if low < high
        pivot_index = partition(arr, low, high)
        puts "[#{arr.join(', ')}]" #you can change it to ```puts arr.join(' ') else
        advanced_quicksort(arr, low, pivot_index - 1)
        advanced_quicksort(arr, pivot_index + 1, high)
    end
end

def partition(arr, low, high)
    pivot = arr[high]
    i = low - 1

    (low..high - 1).each do |j|
        if arr[j] < pivot
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
        end
    end

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    i + 1
end

# Example usage:
arr = [1, 3, 9, 8, 2, 7, 5]
puts "[#{arr.join(', ')}]"
advanced_quicksort(arr)

Upvotes: 0

rcgldr
rcgldr

Reputation: 28826

If sorting large arrays, the stack space can be limited to O(log(n)), but worst case time complexity will remain at O(n^2). I don't know ruby syntax, but the ideal is to only recurse on the smaller partition, and loop back for the larger partition:

def quicksort(arr, left = 0, right = arr.length - 1)
  while left < right
    index = partition(arr, left, right)
    if((index - left) < (right-index))
        quicksort(arr, left, index - 1)
        left = index
    else
        quicksort(arr, index, right)
        right = index-1
  end
  arr
end

Upvotes: 0

Schwern
Schwern

Reputation: 164819

If we throw a debugging p "Left #{left}, Right #{right}...

def quicksort(arr = [], left = 0, right = 0)
  right = arr.length - 1 if right < 1
  if left < right
    index = partition(arr, left, right)
    quicksort(arr, left, index - 1)
    ...

We find there's a problem. left is never set. It's always the default of 0. And right is doing its own thing.

"Left 0, Right 10"
"Left 0, Right 8"
"Left 0, Right 2"
"Left 0, Right 1"
"Left 0, Right 10"
"Left 0, Right 7"
"Left 0, Right 6"
"Left 0, Right 5"
"Left 0, Right 2"
"Left 0, Right 1"
"Left 0, Right 10"
"Left 0, Right 4"
"Left 0, Right 2"
"Left 0, Right 1"
"Left 0, Right 10"
"Left 0, Right 5"
"Left 0, Right 2"
"Left 0, Right 1"
"Left 0, Right 10"
"Left 0, Right 5"
"Left 0, Right 2"
"Left 0, Right 1"

The problem is right = arr.length - 1 if right < 1. If right is ever < 1 it's set back to the end of the array. left is always 0 so left is always less than right. quicksort(arr, 0, index - 1) is recursed into over and over again. quicksort(arr, index, right) is never reached.

Your partition is fine, and good eye noticing pivot can be calculated inside pivot.

What tripped you up is those defaults. You're setting a default for right any time it's less than 1. But it should only be set if it isn't passed in at all.

def quicksort(arr, left = 0, right = arr.length - 1)
  if left < right
    index = partition(arr, left, right)
    quicksort(arr, left, index - 1)
    quicksort(arr, index, right)
  end
  arr
end

Now quicksort(array) is equivalent to quicksort(array, 0, array.length - 1). Subsequent recursive calls pass left and right in, so no need for defaults.

And no default for the array. If they forget to pass an array in that should be an ArgumentError.

I prefer the public wrapper approach used in the video. If someone accidentally passes in too many arguments they get a clear ArgumentError rather than something weird happening.

# Using the ! convention for functions which alter their arguments.
def quicksort!(array)
  _quicksort!(array, 0, array.length - 1)
end

private def _quicksort!(array, left, right)
  ...
end

Upvotes: 2

Related Questions