#ruby #insertion-sort #argument-error
Вопрос:
Ниже приведен обновленный код:
def insertion_sort(list) num = list.length for i in (0..(num-2)) if list[i] gt; list[i 1] amp;amp; i == 0 list[i], list[i 1] = list[i 1], list[i] i =1 elsif list[i] == list[i 1] i =1 elsif list[i] gt; list[i 1] amp;amp; i gt; 0 len = (list[0..(i 1)].length) list2 = list[0..(i 1)] list = list - list2 count = 0 while count lt;= len 1 if list2[len-1] lt; list2[len-2] list2[len-2],list2[len-1]= list2[len-1],list2[len-2] elsif list2[len-1] == list2[len-2] count =1 len-=len else count =1 len-=1 end end list = list2 list end end list end p insertion_sort([2,1,4,8,7,3,100,99,8]) p insertion_sort([2,1,4,8,8,7,3,100,99]) p insertion_sort([3790,780,780,1,55]) Краткие сведения:
- код работает, если два одинаковых целых числа находятся рядом друг с другом :[2,1,4,8,8,7,3,100,99] и размер массива gt; 5.
- если два одинаковых целых числа находятся в случайных позициях: [2,1,4,8,7,3,100,99,8]. Ниже произошла бы ошибка aaa.rb:4:в `gt;»: сравнение целого числа с нулем не удалось (аргумент)
с кодом строки 4: если список[i] gt; список[i 1] amp;amp; i == 0
Для решения 1. Я изменил цикл while на «подсчет времени Но не тогда, когда одинаковые целые числа находятся в случайных позициях.
Кто-нибудь знает, как это решить? Заранее спасибо!
Комментарии:
1. Код отлично работает для меня (вывод [1, 2, 3, 4, 7, 8, 8, 99, 100]). Какую версию Ruby вы запускаете снова?
2. @CormacMulhall в настоящее время использует Ruby 3.0.0p0. На какой версии вы тестировали код? Спасибо!
3. Протестировано с 3.0.2 и 2.7.4 (последние выпуски в ветвях 3 и 2). Ошибка подразумевает, что
iэто выходит за рамки списка, и я не понимаю, почему это произойдет, основываясь на вашем коде. Вы уверены, что код, который вы запускаете, немного не отличается от кода, который вы вставили сюда?4. @CormacMulhall На самом деле массив выше [2,1,4,8,8,7,3,100,99] работал без ошибок. Но я протестировал другой, более экстремальный массив [3790,1,780,55,23,50,1111,60,50], и в итоге получил аргумент. «сравнение целого числа с нулем не удалось». Не могу понять, почему это выходит за рамки дозволенного…
Ответ №1:
Спасибо за разъяснения в комментариях. Теперь я вижу проблему.
В алгоритме подкачки здесь
elsif list[i] gt; list[i 1] amp;amp; i gt; 0 len = (list[0..(i 1)].length) list2 = list[0..(i 1)] list = list - list2 count = 0 while count lt;= len 1 ... вы пытаетесь разделить массив на две части. Вы получаете list2 первую половину массива, а затем пытаетесь получить вторую половину, вычитая list2 из list .
Проблема с использованием метода вычитания здесь заключается в том, что если у вас есть дубликаты, он удалит их и сделает ваши списки слишком короткими.
В примере [3790,1,780,55,23,50,1111,60,50] у вас должно быть a 50 в первом массиве и a 50 во второй половине.
Но использование вычитания удаляет одно из них 50 .
Когда вы снова соединяете два временных списка, вам теперь не хватает одного элемента (недостает 50 ), и вы получаете ошибку «за пределами границ», когда добираетесь до конца массива и пытаетесь получить доступ к этому 9-му элементу, которого больше не существует.
Вместо того, чтобы использовать здесь вычитание, просто используйте тот же метод, который вы использовали для создания list2 .
list2 = list[0..(i 1)] # All elements in list from position 0 to i 1 list = list[(i 2)..-1] # All elements in list from position i 2 to end of list Теперь list и list2 являются просто исходным разделением списка, и когда вы добавляете их обратно вместе, они должны быть одинаковой длины
def insertion_sort(list) num = list.length for i in (0..(num-2)) if list[i] gt; list[i 1] amp;amp; i == 0 list[i], list[i 1] = list[i 1], list[i] i =1 elsif list[i] == list[i 1] i =1 elsif list[i] gt; list[i 1] amp;amp; i gt; 0 len = (list[0..(i 1)].length) list2 = list[0..(i 1)] list = list[(i 2)..-1] count = 0 while count lt;= len 1 if list2[len-1] lt; list2[len-2] list2[len-2],list2[len-1]= list2[len-1],list2[len-2] elsif list2[len-1] == list2[len-2] count =1 len-=len else count =1 len-=1 end end list = list2 list end end list end p insertion_sort([2,1,4,8,7,3,100,99,8]) p insertion_sort([2,1,4,8,8,7,3,100,99]) p insertion_sort([3790,780,780,1,55]) Комментарии:
1. Спасибо, Кормак! Я как раз собирался проверить список вычитания и добавления, но, к счастью, я сначала прочитал ваш ответ. Очень тщательно 100!