Попытка написать программу сортировки с ruby ​​- уровень стека слишком глубокий (ошибка системного стека) - PullRequest
1 голос
/ 07 марта 2011

Я читаю книгу Криса Пайна "Учись прогамам" (она о Руби). Прямо сейчас я пытаюсь написать программу, которая сортирует слова. К сожалению, я застрял с: stack level too deep (system stack error) in line 16, что, если я правильно гуглю, означает, что существует бесконечный цикл, но я не знаю почему.

Вот код:

words = []
wordss = []
word = 'word'
i = 0
k = 0

def sortw array
  i = 0
  if    (array.length == 1) || (array.length == 0)
  else sort array, [], [], i
  end
  return array
end

def sort unsorted, unsort, sorted, i
  k = 0 # The error should be here, according to command prompt
  while i < unsorted.length

    while (unsorted[i] < unsorted[k])
      if    k < unsorted.length
        k = k + 1
      elsif k == unsorted.length
        sorted.push unsorted[i]
      else unsort.push unsorted[i]
      end
    end

    i = i + 1
    sort unsorted, unsort, sorted, i
  end

  if unsort.length != 1
    i = 0
    sort unsort, [], sorted, i
  else sorted.push unsort[0]
  end

  return sorted
end

puts 'type one word per line...'
puts 'typing enter on an empty line sorts the inputted words'

while word != ''
  word = gets.chomp
  words = words.push word
end

wordss = (sortw words)

puts 'your words'
puts words
puts 'sorted here'
puts wordss

1 Ответ

1 голос
/ 07 марта 2011

Вы получаете ошибку, потому что рекурсия не останавливается из-за проблемы с алгоритмом сортировки.В методе sort значение k всегда меньше unsorted.length.Это приводит к тому, что другие массивы, sorted и unsort никогда не заполняются.

Например, попробуйте ввести их:

  • dog
  • zebra
  • cat

Кроме того, я думаю, что вы не хотите включать пустую строку, поэтому я бы изменил код с:

words = words.push word на words = words.push word if word != ''

Создает массив unsorted:

  • [0] собака
  • [1] зебра
  • [2] кошка

Ниже приведены итерации рекурсивного sort метода.

#initial variable state:
i = 0
k = 1
  1. собака = собака
    • пропустить секунду, пока цикл
    • i = 1
  2. зебра> собака
    • пропустить секунду во время цикла
    • i = 2
  3. кошка <собака <ul>
  4. введите второй цикл while
    • k = 1, теперь cat
    • k = 2, теперь cat = cat, поэтому выйдите, пока
  5. i = 3
  6. Поскольку i теперь равен длине массива unsorted, два цикла while neВернитесь больше.

Следовательно, следующий код приводит к бесконечному циклу, поскольку в массив unsort ничего не помещалось:

if unsort.length != 1
  i = 0
  sort unsort, [], sorted, i #Problem is that `unsort` and `sorted` are empty
elsif
...
end
...