Слишком высокий уровень стека в рекурсивном вызове ruby

Question

Я пытаюсь реализовать алгоритм быстрой сортировки, используя ruby. Посмотри, что я сделал:

class Array

  def quick_sort  #line 14
    less=[];greater=[]
    if self.length<=1
      self[0]
    else
      i=1
      while i<self.length
        if self[i]<=self[0]
          less << self[i]
        else
          greater << self[i]
        end
      i=i+1
      end
    end
    less.quick_sort + self[0] + greater.quick_sort #line 29
  end
end
[1,3,2,5,4].quick_sort #line 32

Это сгенерировало ошибку:

bubble_sort.rb:29:in `quick_sort': stack level too deep (SystemStackError)
    from bubble_sort.rb:29:in `quick_sort'
    from bubble_sort.rb:32

Почему это происходит?

Answer 1

Я думаю, что проблема в вашем примере заключалась в том, что вам нужно было явно указать return.

if self.length<=1
  self[0]

return [] if self == []

и

less.quick_sort + self[0] + greater.quick_sort #line 29

должно было быть

less.quick_sort + [self[0]] + greater.quick_sort #line 29

Вот рабочий пример

class Array

  def quick_sort
    return [] if self == []
    pivotal = self.shift;
    less, greater = [], []
    self.each do |x|
      if x <= pivotal 
        less << x
      else 
        greater << x
      end
    end
    return less.quick_sort + [pivotal] + greater.quick_sort
  end
end
[1,3,2,5,4].quick_sort # => [1, 2, 3, 4, 5]

Answer 2

В этой части вы не должны обрабатывать регистр "=".Только <и> должны быть обработаны.Поэтому ваш алгоритм никогда не останавливается и вызывает бесконечную рекурсию.

if self[i]<=self[0]
  less << self[i]
else
  greater << self[i]
end

Answer 3

less.quick_sort + self[0] + greater.quick_sort

Эта строка находится за пределами оператора if, поэтому она выполняется независимо от того, истинно self.length<=1 или нет. Следовательно, метод повторяется бесконечно, что приводит к переполнению стека.

Следует также отметить, что self[0] не возвращает массив (если self не является массивом массивов), поэтому нет смысла использовать Array#+ для него. Это также не имеет смысла в качестве возвращаемого значения для вашего метода quick_sort.