реализация быстрой сортировки: слишком глубокий уровень стека (SystemStackError)

#ruby #algorithm

#рубин #алгоритм #ruby

Вопрос:

Итак, я пытаюсь реализовать быструю сортировку в ruby, и я получаю эту ошибку `quicksort’: уровень стека слишком глубокий (SystemStackError)

 def quicksort(array)
  if array.length <= 1
    return array
  end
  less = Array.new
  greater = Array.new
  pivot = array[array.length/2]
  array.each do |x|
    if x < pivot
      less << x
    else 
      greater << x
    end
  end
  return quicksort(less) << pivot << quicksort(greater)
end

Редактировать
Я изменил else на elsif x > pivot , и , кажется , это работает .

1. Быстрая сортировка может использовать до n уровней стека (в патологических случаях), где n — количество входных элементов. Если этот случай достигнут, то только увеличение размера стека, выбор лучшего метода сводки (который только уменьшит патологически плохие случаи) или изменение реализации быстрой сортировки исправит это. Если это происходит для небольшого числа n, то, конечно, условие терминала неверно 🙂 Какой [наименьший] входной сигнал вызывает это исключение?

2. При каких условиях вы получаете эту ошибку?

3. Я изменил else => elsif x> pivot и, похоже, это работает.

Ответ №1:

У меня ваш алгоритм работает даже на уровне 1e7, когда я генерирую массив для тестирования.

  quicksort Range.new(1,1e7).to_a.shuffle

Конечно, для завершения работы потребовалось около 4,5 ГБ оперативной памяти. Что касается очистки выходных данных…

 ruby-1.9.3-p0 :018 >       quicksort [1,3,2] # => [1, 2, [], 3, []] 
ruby-1.9.3-p0 :019 >     quicksort [1,4,2,3] # => [1, 2, [3, [4]]]

Измените эту строку:

   return (quicksort(less) << pivot << quicksort(greater)).flatten.compact

И это делает все намного чище.

 ruby-1.9.3-p0 :037 >       quicksort [1,3,2] # => [1, 2, 3] 
ruby-1.9.3-p0 :038 >     quicksort [1,4,2,3] # => [1, 2, 3, 4]

Ответ №2:

вам нужно было удалить pivot из массива, потому что вы добавляете его обратно позже, поэтому вместо

 pivot = array[array.length/2]

вы должны были сделать

 pivot = array.delete_at(array.length/2)

Ответ №3:

В ruby размер стека по умолчанию установлен довольно маленьким. Так что не так уж сложно взорвать стек, выполняя рекурсивные функции с большими наборами данных.

Самый простой способ убедиться, что вы не повторяете бесконечно, — это выполнить quicksort на очень маленьком наборе данных. Если он все еще взрывается, вы знаете, что повторяете бесконечно.

Вы можете найти некоторую информацию о размере стека в этом сообщении, на которое отвечает Matz.

1. Но размер стека в Quicksort должен оставаться очень маленьким, если реализация не прерывается на уже отсортированных данных. Размер стека будет около lg (n) — намного меньше предела любого языка сценариев, даже если массив заполняет всю память!

Ответ №4:

Ваша функция повторяется бесконечно. Используйте ruby-debug, чтобы выяснить причину.

ПРАВКА1:

Я думаю, вы хотите, чтобы последняя строка функции была такой:

 return quicksort(less)   quicksort(greater)