2026/27, 10Д, Python: Сортировки (часть1)

Для поднятия настроения населения, были запрещены отрицательные числа. Поэтому в данном списке нужно оставить только положительные числа, удалив из списка все отрицательные числа и нули.

Решение оформите в виде функции positive(a: list). Функция получает на вход список чисел и должна удалить из этого списка неположительные значения, оставив только положительные числа, не меняя их порядка. Функция должна модифицировать тот список, который ей передали, и не возвращать значение при этом.

Сдайте на проверку только тело функции.

[1, -1, 0, 2, 1]

[1, 2, 1]

Решите задачу «только положительные» при условии, что сложность решения должна быть \(O(n)\), где \(n\) — размер исходного массива.

В тестах массив может иметь длину до \(10^5\) элементов, ограничение по времени работы программы — 1 секунда.

Напишите функцию swap(a: list, b: list), которая обменивает содержимое двух данных списков a и b.

Решение должно иметь сложность O(len(a) + len(b)).

Дан список сравнимых между собой элементов (чисел, строк и т.д.). Упорядочите его в порядке неубывания значений.

Решите эту задачу при помощи алгоритма сортировки выбором. Решение оформите в виде функции selection_sort(a). Эта функция должна вернуть новый список, упорядочив значения исходного списка.

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

selection_sort([1, 4, 2, 3, 4])

[1, 2, 3, 4, 4]

selection_sort(['one', 'two', 'three', 'four'])

['four', 'one', 'three', 'two']

Реализуйте алгоритм сортировки пузырьком.

Решение оформите в виде функции bubble_sort(A). Эта функция должна изменить переданный ей список, не возвращая значения.

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

[1, 4, 2, 3, 4]

[1, 2, 3, 4, 4]

['one', 'two', 'three', 'four']

['four', 'one', 'three', 'two']

Реализуйте алгоритм сортировки вставками.

Решение оформите в виде функции insertion_sort(a). Эта функция должна изменить переданный ей список, не возвращая значения.

Реализация алгоритма сортировки вставкой должна работать быстро на уже упорядоченном массиве или на массиве, который близок к упорядоченному.

[1, 4, 2, 3, 4]

[1, 2, 3, 4, 4]

['one', 'two', 'three', 'four']

['four', 'one', 'three', 'two']

Системный администратор вспомнил, что давно не делал архива пользовательских файлов. Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.

Известно, какой объем занимают файлы каждого пользователя.

Напишите программу, которая по заданной информации о пользователях и свободному объему на архивном диске определит максимальное число пользователей, чьи данные можно поместить в архив, при этом используя свободное место как можно более полно.

Программа получает на вход в одной строке число \(s\) — размер свободного места на диске, и число \(n\) — количество пользователей, после этого идут \(n\) чисел — объем данных каждого пользователя, записанных каждое в отдельной строке.

Выведите наибольшее количество пользователей, чьи данные могут быть помешены в архив.

Используйте стандартную сортировку. Решение должно иметь сложность стандартной сортировки + \(O(n)\). Решение не должно модифицировать исходный список после считывания и сортировки.

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал \(n\) машин —ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за километр.

Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, сколько придется заплатить за перевозку всех сотрудников. Естественно, директор хочет заплатить как можно меньшую сумму.

В первой строке записаны \(n\) чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании. Во второй строке записаны \(n\) чисел — тарифы за проезд одного километра в такси.

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

В супермаркете проводится беспрецедентная акция — «Покупая два любых товара, третий получаешь бесплатно*», а внизу мелким шрифтом приписано «* — из трёх выбранных вами товаров оплачиваются два наиболее дорогих».

Вася, идя в супермаркет, определился, какие товары он хочет купить, и узнал, сколько они стоят. Помогите ему определить минимальную сумму денег, которую ему нужно взять с собой, чтобы в итоге стать счастливым обладателем этих товаров.

Программа получает на вход несколько чисел в одной строке — стоимости выбранных Васей товаров. Все стоимости — натуральные числа, не превышающие 10000.

Выведите одно число — сумму денег, которую Вася должен взять с собой в супермаркет (минимально возможную).

Дан список чисел. Определите, сколько в нем различных чисел.

Используйте встроенную сортировку языка Python. Решение должно иметь сложность встроенной сортировки + \(O(n)\).

Дан список чисел (содержащий не менее двух элементов). Найдите в нем два ближайших друг к другу числа (то есть два числа с наименьшей разностью).

Выведите эти числа в порядке неубывания.

Используйте встроенную сортировку языка Python. Решение должно иметь сложность встроенной сортировки + \(O(n)\).