Алгоритмы и структуры данных · 25 из 30
Сортировка вставками
Лабораторная «сортировки»: вставками, руками, без sorted. Так раскладывают карты в руке — берут следующую и сдвигают вправо все, что больше неё, пока не освободится её место. Борис Аркадьевич просит ещё и посчитать сдвиги: «по ним видно, насколько массив был перемешан».
Что сделать
Отсортируйте список вставками сами и посчитайте, сколько раз элементы сдвигались вправо.
Что приходит
spisok— список чисел; менять его нельзя
Что вернуть
Пару (новый список по возрастанию, число сдвигов).
Допишите функцию vstavki в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
Ограничения
Без
sorted— и своё имя так назвать нельзяБез метода
.sort()
Обходные пути — тоже нарушение: eval, exec, getattr, имена с двойным подчёркиванием, импорт os, subprocess и им подобных.
vstavki([5, 2, 4, 6, 1, 3])
([1, 2, 3, 4, 5, 6], 9)
Работайте с копией списка. Для каждого элемента, начиная со второго: запомните его и, двигаясь влево, сдвигайте на одно место вправо каждый элемент, который строго больше запомненного. На освободившееся место поставьте запомненный.
Сдвиг — перенос одного элемента на одно место вправо. Равные элементы не сдвигаются: сортировка устойчивая, и равные остаются в прежнем порядке.
Верните отсортированную копию и общее число сдвигов. Исходный список должен остаться прежним.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.