Упражнения на слияние списков и реализация сортировки слиянием

От сортировки вставками до сортировки слиянием

В алгоритме сортировки вставкой в каждый произвольный момент начальная часть списка уже отсортирована. Далее первый элемент из неотсортированной части добавляется в отсортированную часть списка. Таким образом, мы $n$ раз подряд производим слияние двух отсортированных списков: одного длины 1, 2, и так далее до $n-1$, и второго — каждый раз длины 1.

Однако два списка длин $n$ и $m$ можно слить вместе в один отсортированный список за время порядка $n+m$. Если мы сначала разобьём элементы на пары, которые сольём в списки длины 2, затем их сольём в списки длины 4, и так далее, то потратим на всю сортировку как раз $O(n \log n)$ операций.

Проще всего описать это при помощи рекурсии. Если длина массива не превосходит 1, то он уже отсортирован. В противном случае отсортируем первую половину массива, отдельно отсортируем вторую половину, после чего сольём всё вместе.

A: Слияние списков

Даны два списка a и b упорядоченных по неубыванию. Объедините их в один упорядоченный список.

Решение оформите в виде функции merge(a: list, b: list) -> list, возвращающей новый список и не модицифицирующей данные списки. Алгоритм должен иметь сложность \(O(n+m)\) (\(n\) — размер первого списка, \(m\) — размер второго списка).

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

merge([1, 5, 7], [2, 4, 4, 5])
[1, 2, 4, 4, 5, 5, 7]

Код вызова функции для тестирования
a = eval(input())
a_copy = a[:]
b = eval(input())
b_copy = b[:]
res = merge(a, b)
if a != a_copy or b != b_copy:
    print("Фунция не должна модифицировать передаваемые параметры")
if type(res) != list:
    print("Функция должна возвращать список")
else:
    print(res)
IDE

B: Пересечение множеств

Даны два списка чисел, упорядоченных по возрастанию (каждый список состоит из различных элементов). Найдите пересечение данных множеств, то есть те числа, которые входят в оба массива. Алгоритм должен иметь сложность \(O(n+m)\).

Решение оформите в виде функции intersection(a: list, b: list) -> list, возвращающий пересечение двух данных списков. Полученный список должен быть упорядочен по возрастанию.

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

intersection([1, 3, 4, 7, 9], [2, 3, 7, 10, 11])
[3, 7]

Код вызова функции для тестирования
a = eval(input())
a_copy = a[:]
b = eval(input())
b_copy = b[:]
res = intersection(a, b)
if a != a_copy or b != b_copy:
    print("Фунция не должна модифицировать передаваемые параметры")
if type(res) != list:
    print("Функция должна возвращать список")
else:
    print(res)
IDE

C: Сортировка слиянием

Сортировка слиянием (англ. merge sort) позволяет отсортировать данный массив при помощи \(O(n\log n)\)) сравнений элементов.

Проще всего реализовать сортировку слиянием при помощи рекурсивной функции. Если длина данного массива равна 0 или 1, то массив уже отсортирован. Иначе необходимо разделить этот массив на две части равной (или отличающейся на 1) длины, каждую из них отсортировать рекурсивно, затем слить результат двух полученных массивов в исходный массив.

Реализуйте алгоритм сортировки слиянием. Решение оформите в виде функции merge_sort(a: list) -> list.

На проверку сдайте только тело этой и вспомогательной функции слияния.

merge_sort([4, 1, 4, 8, 6, 6, 5])
[1, 4, 4, 5, 6, 6, 8]

Код вызова функции для тестирования
a = eval(input())
a_copy = a[:]
res = merge_sort(a)
if a != a_copy:
    print("Фунция не должна модифицировать передаваемые параметры")
if type(res) != list:
    print("Функция должна возвращать список")
else:
    print(res)
IDE

Упражнения на нестандартные виды сортировок

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

Параметр key у метода sort и функции sorted

Допустим, у нас есть список названий деталей и их стоимостей. Нам нужно отсторитровать его сначала по названию деталей, а одинаковые детали по убыванию цены. Самая коротка реализация даст не совсем тот результат:
shop = [['каретка', 1200], ['шатун', 1000], ['седло', 300], ['педаль', 100], ['седло', 1500],
        ['рама', 12000], ['обод', 2000], ['шатун', 200], ['седло', 2700]]
shop.sort()
for i in range(len(shop)):
    print('{:<10} цена: {:>5}р.'.format(shop[i][0], shop[i][1]))
каретка    цена:  1200р.
обод       цена:  2000р.
педаль     цена:   100р.
рама       цена: 12000р.
седло      цена:   300р.
седло      цена:  1500р.
седло      цена:  2700р.
шатун      цена:   200р.
шатун      цена:  1000р.
Как и следовало ожидать, одинаковые детали отсортированы по возрастанию цены (не обращайте пока внимания на format, или почитайте документацию).

Это можно исправить так:

def prepare_item(item):
    return (item[0], -item[1])

shop = [['каретка', 1200], ['шатун', 1000], ['седло', 300], ['педаль', 100], ['седло', 1500],
        ['рама', 12000], ['обод', 2000], ['шатун', 200], ['седло', 2700]]
shop.sort(key=prepare_item)
for i in range(len(shop)):
    print('{:<10} цена: {:>5}р.'.format(shop[i][0], shop[i][1]))
каретка    цена:  1200р.
обод       цена:  2000р.
педаль     цена:   100р.
рама       цена: 12000р.
седло      цена:  2700р.
седло      цена:  1500р.
седло      цена:   300р.
шатун      цена:  1000р.
шатун      цена:   200р.

Что здесь произошло? Перед тем, как сравнивать два элемента списка к ним применялась функция prepare_item, которая меняла знак у стоимости. В результате при одинаковов первом значении сортировка по второму происходила в обратном порядке.

Ещё можно писать так (но делать это нужно аккуратно и с пониманием):

shop.sort(key=lambda x: (x[0], -x[1]))

Используя подходящую функцию prepare_item мы можем делать и более сложные сортировки:
Отсортировать только по второму элементу

def prepare_item(item):
    return item[1]
Отсортировать по модулю третьего элемента:
def prepare_item(item):
    return abs(item[2])
Отсортировать сначала по третьему элементу списка, затем по модулю первого:
def prepare_item(item):
    return (item[2], abs(item[0]))

Другой способ хитрых сортировок

Допустим данные нужно отсортировать сначала по столбцу А по возрастанию, затем по столбцу Б по убыванию, и наконец по столбцу В снова по возрастанию. Если данные в столбце Б числовые, то при помощи подходящей функции в key можно поменять знак у элементов Б, что приведёт к необходимому результату. А если все данные текстовые? Тут есть такая возможность. Дело в том, что сортировка sort в Python устойчивая, то есть она не меняет порядок «одинаковых» элементов. Поэтому можно просто отсортировать три раза по разным ключам:

data.sort(key=lambda x: x['В'])
data.sort(key=lambda x: x['Б'], reverse=True)
data.sort(key=lambda x: x['А'])

D: Оладьи

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

Сортировка стопки осуществляется серией “переворотов” оладий. Переворот заключается в том, что вы помещаете лопатку между двумя оладьями и переворачиваете всю стопку, оказавшуюся на лопатке, то есть меняете порядок следования оладий над лопаткой на обратный.

Стопка определяется заданием диаметра каждой оладьи в стопке в порядке следования (сверху вниз). Переворачивание определяется количеством оладий, которое переворачивается. Например, из стопки 7 3 9 1 5 переворачиванием трех оладий получится стопка 9 3 7 1 5.

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

Первая строка входных данных содержит натуральное число \(N\) (\(1 \le N \le 1000\)) — количество оладий в стопке. Далее идет \(N\) натуральных чисел, не превосходящих \(10^9\) — размеры оладий в стопке (сверху вниз).

Программа должна вывести последовательность натуральных чисел, не превосходящих \(N\), соответствующую количеству оладий, которое необходимо переворачивать для правильной сортировки стопки. Количество переворотов не должно превосходить \(10000\).

3 1 3 2
2 3 2
IDE

E: Число из кусочков

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

Первая строка входных данных содержит количество кусочков \(N\le100\). Следующие \(N\) строк содержат последовательности цифр, записанных на кусочках, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.

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

4 2 20 004 66
66220004

Указание. Эта задача — не про числа.

IDE

F: Кузнечики возвращаются

\(N\) кузнечиков сидят вдоль числовой прямой, в точках 1, 2, ..., \(N\). На кузнечиках написаны числа от \(1\) до \(N\). Необходимо расставить кузнечиков по порядку, чтобы каждый кузнечик оказался в точке, соответствующей его номеру.

Длина прыжка кузнечика равна 2 или 3. Одновременно в одной точке не могут находиться два кузнечика, поэтому единственно возможная операция перестановки кузнечиков заключается в том, что два кузнечика, сидящих в точках \(i\) и \(j\) одновременно прыгают и меняются местами. Это возможно сделать только в том случае, если \(|i-j|=2\) или \(|i-j|=3\).

Найдите последовательность обменов кузнечиков, которая упорядочивает их расстановку.

В первой строке входных данных дан размер массива \(N\) (\(5\le N\le 100\)), во второй строке записана некоторая перестановка чисел от \(1\) до \(N\) через пробел — номера кузнечиков.

Программа должна вывести последовательность обменов кузнечиков. В каждой строке выводится два числа \(i\) и \(j\), означающих, что необходимо переставить переставить кузнечиков, сидящих в точках \(i\) и \(j\), при этом \(1\le i\le n\), \(1\le j\le n\), \(2\le|i-j|\le3\).

5 3 4 1 5 2
2 4 1 3 2 5
IDE

G: Ожерелье

В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из \(N\) колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до \(N\), начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.

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

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

Первая строка входных данных содержит число \(N\) (\(2 \le N \le 50\)). Во второй строке через пробел следуют \(N\) различных чисел от 1 до \(N\) — номера колечек, расположенных вдоль нити по часовой стрелке.

Программа должна вывести описание процесса упорядочения.

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

Количество выводимых строк не должно превышать 50000.

4 3 1 2 4
4 2 4 1 0
IDE

Задачи на упорядочивание маленьких списков за минимальное число сравнений

H: Упорядочить список из 4 элементов за 5 сравнений

Напишите функцию def sort4(a: list), упорядочивающую данный список a по неубыванию элементов. Предполагается, что в списке не более 4 элементов. Функция должна выполнять не более 5 сравнений элементов между собой при помощи операций “меньше” или “больше”.

Функция не возвращает значение, а переставляет элементы переданного списка.

Пример реализации аналогичной функции для 3 элементов:

def sort3(a):
    if a[0] > a[1]:
        a[0], a[1] = a[1], a[0]
    if a[1] > a[2]:
        a[1], a[2] = a[2], a[1]
    if a[0] > a[1]:
        a[0], a[1] = a[1], a[0]

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


Код вызова функции для тестирования
class Integer:
    count = 0
    def __init__(self, s=0):
        self.__data = int(s)
    def __lt__(self, other):
        Integer.count += 1
        return self.__data < other.__data
    def __eq__(self, other):
        return self.__data == other.__data
    def __str__(self):
        return str(self.__data)
    def __repr__(self):
        return str(self.__data)
src = [Integer(i) for i in range(1, 5)]
for perm in itertools.permutations(src):
    perm = list(perm)
    Integer.count = 0
    perm_sorted = perm[:]
    sort4(perm_sorted)
    if perm_sorted != src:
        print("Сортировка работает неправильно")
        print("Исходный список:", perm)
        print("Список после сортировки:", perm_sorted)
        break
    if Integer.count > 5:
        print("Выполнено слишком много сравнений:", Integer.count)
        print("Исходный список:", perm)
        break
else:
    print("OK")
IDE

I: Упорядочить список из 5 элементов за 7 сравнений

Напишите фунцию сортировки списка из 5 элементов, использующей не более 7 сравнений. Решение оформите в виде функции def sort5(a: list).

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

Эту задачу вряд ли получиться решить без использования вложенных условных инструкций.


Код вызова функции для тестирования
class Integer:
    count = 0
    def __init__(self, s=0):
        self.__data = int(s)
    def __lt__(self, other):
        Integer.count += 1
        return self.__data < other.__data
    def __eq__(self, other):
        return self.__data == other.__data
    def __str__(self):
        return str(self.__data)
    def __repr__(self):
        return str(self.__data)
src = [Integer(i) for i in range(1, 6)]
for perm in itertools.permutations(src):
    perm = list(perm)
    Integer.count = 0
    perm_sorted = perm[:]
    sort5(perm_sorted)
    if perm_sorted != src:
        print("Сортировка работает неправильно")
        print("Исходный список:", perm)
        print("Список после сортировки:", perm_sorted)
        break
    if Integer.count > 7:
        print("Выполнено слишком много сравнений:", Integer.count)
        print("Исходный список:", perm)
        break
else:
    print("OK")
IDE

Задачи на подсчёт количества инверсий

Здесь вам поможет сортировка слиянием.

J: Количество инверсий

Для заданного списка чисел найдите количество таких пар \((i, j)\), что \(i\lt j\) и \(a_i \gt a_j\).

Первая строка содержит число \(n\) — количество элементов в списке. Вторая строка содержит \(n\) различных целых чисел.

Программа должна вывести одно число — количество инверсий в данном списке. Решение должно иметь сложность \(O(n\log(n))\).

Указание: используйте сортировку слиянием.

5 6 11 18 28 31
0
8 94 89 82 72 69 61 54 50
28
IDE

K: Таблица инверсий

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

Программа должна вывести \(n\) чисел — ответ для каждого элемента массива. Решение должно иметь сложность \(O(n\log(n))\).

6 4 8 2 5 4 3
0 0 2 1 2 4
IDE