Введение

После всего изученного нами остался небольшой неизученный "должок" — "быстрые" сортировки. Мы уже разбирали несколько алгоритмов, работающих за квадратичное время — сортировка пузырьком, выбором, вставкой. Эти алгоритмы просты, но требуют оптимизации, когда дело доходит до больших массивов. Для каждого из них существуют оптимизации, делающие их "быстрыми" — то есть работающими за время $O(n \log n)$.

Начнём с того, что "вспомним" старые сортировки. Да, мы уже решали эти задачи, но, пожалуйста, напишите код для них заново. Это не должно занять много времени.

A: Сортировка пузырьком

Дан список целых чисел. Отсортируйте его в порядке невозрастания значений. Выведите полученный список на экран.

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

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

Вспомогательным списком пользоваться нельзя.

1 4 2 3 4
4 4 3 2 1
IDE

B: Сортировка выбором

Дан список целых чисел. Выведите все элементы этого списка в порядке невозрастания значений. Выведите новый список на экран.

Решите эту задачу при помощи алгоритма сортировки выбором. Решение оформите в виде функции selection_sort(A).

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

Вспомогательным списком пользоваться нельзя.

1 4 2 3 4
4 4 3 2 1
IDE

C: Сортировка вставкой

Дан список целых чисел. Отсортируйте его в порядке неубывания значений. Выведите полученный список на экран.

Решите эту задачу при помощи алгоритма сортировки вставкой. Решение оформите в виде функции insertion_sort(A).

В этой задаче нельзя пользоваться дополнительным списком и операциями удаления и вставки элементов.

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

Обратите внимание, на почти отсортированном массиве ваш алгоритм не должен работать за квадратичное время.

Поиск подходящего места для вставки можно сделать бинарным поиском. При этом можно пользоваться модулем bisect (см. документацию и по-русски).

1 4 2 3 4
1 2 3 4 4
IDE

От сортировки выбором к пирамидальной сортировке

Для определённости будем сортировать массив по возрастанию. (Точнее, по неубыванию, так как в массиве могут быть совпадающие элементы).

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

пока размер неотсортированной части > 1 выполнять
| найти максимальный элемент
| переставить его в конец отсортированной части
конец
Что здесь можно ускорить? Только поиск максимального элемента: ведь перенос элемента и так занимает $O(1)$ (в расчёте на весь массив – $O(n)$).

В простой сортировке выбором мы за $k-1$ сравнение (где $k$ – длина неотсортированной части) всего лишь находили максимальный (минимальный) элемент. При этом мы часто получали информацию про относительные величины некоторых пар элементов, но «забывали» её. В пирамидальной сортировке эта информация будет сохраняться. Другими словами: неотсортированная часть будет не совсем беспорядочной — она будет иметь внутреннюю структуру, которая позволит каждый раз быстро выбирать максимальный элемент.

Для его реализации этого "сохранения" понадобится структура данных, называемая двоичной (бинарной) кучей или пирамидой (По-английски эта структура данных называется $heap$, дословный перевод – куча, но термин $пирамида$, который тоже иногда используется, лучше соответствует сути дела. Рассматриваемый здесь алгоритм сортировки называют сортировкой с помощью кучи, пирамидальной сортировкой или, реже, сортировкой деревом.). Одновременно с этим окажется удобно изучить также основанную на куче приоритетную очередь. Как быстро нужно уметь извлекать из кучи максимальный элемент? Чтобы сложность сортировки была $O(n$ log $n)$, достаточно, чтобы время выбора было $O($log $n)$). Основная идея кучи состоит в том, что мы рассматриваем массив как представление двоичного дерева и вводим некоторый порядок на узлах этого дерева.

Итак, если мы реализуем такую структуру, то алгоритм сортировки приобретёт следующий вид:

преобразовать массив в кучу (пирамиду)
пока размер кучи > 1 выполнять
| выбрать максимальный элемент и перенести его в отсортированную часть
конец

Приоритетная очередь

Легко заметить, что задача реализации кучи родственна задаче эффективной реализации приоритетной очереди. (Это очередь, в которой важно не то, кто «встал» раньше, а кто «главнее». Более точно: при помещении в очередь указывается приоритет помещаемого элемента, а при взятии из очереди выбирается один из элементов с наибольшим приоритетом. В учебных задачах для простоты приоритетом обычно служит само значение элемента).

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

Будет удобно на время отвлечься от сортировки и разобрать подробно реализацию приоритетной очереди на основе кучи.

Двоичная куча (пирамида)

Следующая картинка показывает, как можно отобразить элементы массива A на вершины двоичного дерева:

                 A[0]
             /         \
       A[1]                A[2]
      /    \              /    \
  A[3]      A[4]      A[5]      A[6]
  /
A[7]
Заметим, что при этом получается дерево вполне определённой формы: все его уровни, кроме, возможно, самого нижнего, заполнены целиком. А на самом нижнем уровне все пустые места, если они есть, располагаются правее имеющихся вершин. Будем называть такое двоичное дерево почти полным. Из рисунка нетрудно видеть, что родитель вершины с индексом i имеет индекс (i-1)//2, а левая и правая дочерние вершины имеют индексы 2i+1 и 2i+2 соответственно.

Высотой дерева будем называть число уровней в дереве (или, что то же самое, длину пути от корня до самого дальнего листа плюс один). Так, для дерева на рисунке длина пути от корня до листа A[7] равна 3, а высота равна 4. Полезно установить связь между высотой h и числом вершин дерева s.

Упражнение. Сколько вершин может иметь почти полное двоичное дерево высоты h? Выразите высоту почти полного двоичного дерева через число вершин.

Чтобы быстро искать максимум в этом дереве, расположим элементы массива так, чтобы значение любого элемента было не меньше значений всех его потомков (если они существуют). Для этого достаточно, чтобы для каждого i выполнялись два неравенства: A[i] ≥ A[2i+1] (если 2i+1 ≤ s), и A[i] ≥ A[2i+2] (если 2i + 2 ≤ s). Вообще говоря, часто будет удобно, чтобы этому правилу подчинялись не обязательно все элементы массива, а лишь элементы его некоторого начального участка. Этот участок и будем называть кучей. Будем обозначать размер всего массива n, а размер кучи – s. Размер кучи может меняться от 0 до n включительно.

Итак, двоичной максимальной кучей будем называть некоторое начало A[0]…A[s-1] массива A[0]…A[n-1], (0 ≤ s ≤ n) если каждый его элемент обладает основным свойством максимальной кучи: его значение не меньше значений всех его потомков.

Нетрудно доказать, что максимальный элемент в такой куче имеет индекс 0 в массиве (находится в корне дерева). Если потребовать, чтобы элемент был не больше своих потомков, получим минимальную кучу. (Мы будем рассматривать, в основном, максимальные кучи). Обратите внимание, что «физически» куча – это участок массива. А «логически» её удобно рассматривать как двоичное дерево.

Операции с кучей

С кучей нам будет необходимо делать две основные операции: извлекать максимальный элемент, а также добавлять новый элемент. Для извлечения максимального элемента (который находится по нулевому индексу) мы поставим на его место последний элемент. А для добавления — просто припишем его в конец. Но после этого куча станет немного "испорченной". В обоих случаях есть не больше одного «неправильного» элемента. В первом случае это A[0], а во втором – A[s-1]. В первом случае его значение слишком мало для занимаемого им места, а во втором – слишком велико. В первом случае «неправильный» элемент нужно спустить вниз, а во втором – поднять вверх. Некоторым другим элементам при этом, естественно, тоже придётся подвинуться, но нам будет удобно следить, в первую очередь, именно за перемещением «неправильного» элемента.

Соответственно, нам понадобятся две процедуры для «починки» кучи, которые назовём sift_down (просеивание вниз) и sift_up (просеивание вверх). Каждую из них будем реализовывать для более общего случая, чем вроде бы требуется. А именно, будем считать, что «неправильным» может оказаться любой элемент кучи, а не только первый или последний (зачем это нужно, станет ясно из дальнейшего). Однако по-прежнему будем требовать, чтобы такой элемент был только один.

D: Просеивание вверх

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

В первой сточке задан размер кучи N (натуральное число от 1 до 105). Во второй строке вводится сама куча – N различных целых чисел. Гарантируется, что эти числа составляют корректную максимальную кучу).
В третьей строке вводится число M – количество запросов.
В следующих M строках вводятся сами запросы – по одному в строке. Запрос задаётся двумя целыми числами i и x. Требуется увеличить значение i-го элемента кучи на x и выполнить sift_up для восстановления кучи.
В качестве ответа на запрос требуется вывести одно число: сообщить, на каком месте массива оказался изменённый элемент после выполнения sift_up. (Вывести в отдельной строке одно число – соответствующий индекс). Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.

6 12 6 8 3 4 7 2 4 11 2 6
0 2 15 12 14 3 6 7
12 15 / \ / \ 6 8 12 14 / \ / / \ / 3 4 7 3 6 7

Прочитать после решения или в случае трудностей
Лучше после :)
Это точно трудности?

Проще всего алгоритм описать так. Если A[i] является корнем дерева или не превосходит своего родителя, то ничего делать не надо. В противном случае надо поменять местами его с родителем, после чего снова получим «немного испорченную кучу», но теперь элемент, который, возможно, имеет большее значение, чем требуется на его месте, находится по индексу (i-1)//2. Соответственно надо выполнить sift_up для этого элемента.

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

Полезно заметить сходство этого алгоритма с вставкой очередного элемента в подходящее место отсортированной части массива, которая происходит при простой сортировке вставками.

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

IDE

Вывод кучи

Для вывода кучи в виде дерева можно использовать следующую функцию:
def print_heap(ar):
    ml = max(len(str(x)) for x in ar)
    ars = [('{:0'+str(ml)+'}').format(x) for x in ar]
    dp = len(bin(len(ar))) - 1
    print('*' * 2**(dp-2) * (ml + 1))
    for i in range(1, dp + 1):
        str_space = ' ' * max(0, 2**(dp-i-2) * (ml + 1) - 1 - ml // 2)
        sep_space = ' ' * max(0, 2**(dp-i-1) * (ml + 1) - ml)
        print(str_space + sep_space.join(ars[2**(i-1) - 1: 2**i - 1]))
    print('*' * 2**(dp-2) * (ml + 1))
print_heap(list(range(8)))

E: Просеивание вниз

Реализуйте функцию sift_down, выполняющую просеивание вниз элемента кучи, который оказался меньше положенного.

Входные данные даются в формате из предыдущей задачи.
Запрос задаётся двумя целыми числами i и x. Требуется уменьшить значение i-го элемента кучи на x и выполнить sift_down для восстановления кучи.
В качестве ответа на запрос требуется вывести одно число: сообщить, на каком месте массива оказался изменённый элемент после выполнения sift_down. (Вывести в отдельной строке одно число – соответствующий индекс). Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.

6 12 6 8 3 4 7 2 1 5 0 2
4 0 10 4 8 3 1 7
12 10 / \ / \ 6 8 4 8 / \ / / \ / 3 4 7 3 1 7

Прочитать после решения или в случае трудностей
Лучше после :)
Это точно трудности?

Проще всего алгоритм описать так. Если у A[i] нет сыновей в дереве или если они не превосходят его по величине, то ничего делать не надо. В противном случае надо поменять местами его с максимальным из сыновей. (Если эти сыновья равны, то, вообще говоря, менять можно с любым из них. Но чтобы все последующие задачи были приняты тестирующей системой, надо менять непременно с левым). После чего снова получим «немного испорченную кучу», но теперь элемент, который, возможно, имеет меньше значение, чем требуется, находится на новом месте. Соответственно надо выполнить sift_down для этого элемента. При реализации можно избавиться от рекурсии. Оценка времени работы такая же, как для sift_up. Типичная ошибка – неправильная обработка ситуации, когда имеется только левый сын.

IDE

F: Извлечение максимального

Реализуйте функцию extract_max, извлекающую из кучи максимальный элемент и восстанавливающую её структуру. Его индекс — 0, поэтому мы не можем просто удалить его. Нужно поставить какой-то элемент на его место. Лучше всего для этого подходит последний элемент. Но после этого куча станет немного «испорченной». Чтобы её исправить, нужно «просеить» этот элемент вниз.

На вход даётся куча в формате из предыдущей задачи.
Требуется вывести N-1 строку, в каждой – два числа. Первое – индекс конечного положения последнего элемента кучи после перестановки его на нулевое место и последующего просеивания; второе – значение извлечённого элемента (который раньше был на нулевом месте).

6 12 6 8 3 4 7
2 12 2 8 1 7 0 6 0 4
12 8 7 6 4 3 / \ / \ / \ / \ / 6 8 6 7 6 4 3 4 3 / \ / / \ / 3 4 7 3 4 3
IDE

Просеивание и равенство элементов

В следующих задачах в куче могут встречаться равные элементы. Это создаёт некоторый произвол при выполнении процедур sift_up и sift_down. Для однозначности ответа его придётся ограничить. Поэтому введём два правила:
1) Процедуры просеивания не должны перемещать элемент дальше, чем это действительно необходимо. Например, если A[i]=A[2*i+1], то вызов sift_up(2*i+1) не должен менять местами эти два элемента (хотя их обмен и не испортит кучу, он бесполезен).
2) Если при просеивании вниз можно перемещать рассматриваемый элемент как влево вниз, так и вправо вниз (это бывает, когда он меньше двух равных дочерних), то следует выбирать направление влево.
Второе правило довольно произвольно и введено лишь для обеспечения однозначности ответа. Первому правилу, напротив, должна удовлетворять любая разумная реализация кучи.

G: Приоритетная очередь

Требуется реализовать с помощью кучи приоритетную очередь, поддерживающую две операции: добавить элемент heappush и извлечь максимальный элемент heappop.

В первой строке вводятся два числа – максимальный размер приоритетной очереди N и количество запросов M. (1 ≤ M, N ≤ 105).
Далее идут M строк, в каждой строке – по одному запросу. Первое число в запросе задаёт его тип, остальные числа (если есть) – параметры запроса.
Тип 1 – извлечь максимальный (без параметров),
Тип 2 – добавить данный элемент в очередь.

В ответ на запрос типа 1 следует вывести:
• Если извлекать было нечего (очередь пуста), то -1.
• Иначе, как и в предыдущей задаче – два числа: первое – индекс конечного положения элемента после его просеивания (если же удалён был последний элемент и просеивать осталось нечего, вывести -1); второе – значение извлечённого элемента.
В ответ на запрос типа 2 следует вывести:
• Если добавить нельзя (нет места, поскольку в очереди уже N элементов), то вывести -1. (При этом куча не должна измениться).
• Иначе – индекс добавленного элемента.
Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.

4 7 1 2 9 2 4 2 9 2 9 2 7 1
-1 0 1 2 1 -1 1 9 9 4 9
9 9 9 9 9 9 / / \ / \ / \ / \ 4 4 9 9 9 9 9 4 9 / / 4 4
IDE

H: Приоритетная очередь с удалением

Условие этой задачи отличается от условия предыдущей лишь наличием ещё одного типа запроса – запроса на удаление заданного (не обязательно максимального) элемента. Это будет запрос типа 3 с единственным параметром, задающим индекс элемента, который требуется удалить из кучи.

В ответ на запрос типа 3 следует вывести:
• -1, если элемента с таким индексом нет и удаление невозможно. (При этом куча не должна измениться).
• Иначе – значение удаленного элемента.

4 10 1 2 9 2 4 2 9 2 9 2 7 1 3 3 2 1 3 2
-1 0 1 2 1 -1 1 9 -1 3 9 9 4 1
9 9 9 9 9 9 9 9 / / \ / \ / \ / \ / \ / \ 4 4 9 9 9 9 9 4 9 4 9 4 1 / / / 4 4 1
IDE

Построение кучи из массива

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

До сих пор все операции с кучей были основаны на двух базовых – просеивании вверх (sift_up) и просеивании вниз (sift_down). Давайте попробуем с помощью каждой из них написать и процедуру heapify. Построение кучи просеиванием вверх (Build_Heap1) Дан массив. Требуется преобразовать его в кучу с помощью процедуры просеивания вверх. Формат входных данных. В первой строке вводится длина массива N. В следующей строке идут элементы массива – N целых чисел. Формат выходных данных. N целых чисел – элементы кучи по порядку.

I: Построение кучи просеиванием вверх

Реализуйте функцию heapify1, формирующую кучу с помощью процедуры просеивания вверх.

В первой строке вводится длина массива N. В следующей строке идут элементы массива – N целых чисел.
Преобразуйте массив в кучу и выведите её элементы по порядку.

6 1 2 3 4 5 6
6 4 5 1 3 2

Прочитать после решения или в случае трудностей
Лучше после :)
Это точно трудности?

Можно считать, что с самого начала имеется «немного испорченная куча» размером s = 2, в которой последний элемент, возможно, имеет большее значение, чем требуется для занимаемого им места. Исправив её вызовом sift_up(1), получим «немного испорченную кучу» размером s = 3, которая, в свою очередь, тоже может быть исправлена вызовом sift_up(2). И так далее. Заметим, что это, по существу, ничем не отличается от последовательного добавления элементов A[1], A[2], … A[n-1] по одному в приоритетную очередь.

IDE

J: Построение кучи просеиванием вниз

Реализуйте функцию heapify2, формирующую кучу с помощью процедуры просеивания вниз.

В первой строке вводится длина массива N. В следующей строке идут элементы массива – N целых чисел.
Преобразуйте массив в кучу и выведите их по порядку.

6 1 2 3 4 5 6
6 5 3 4 2 1

Прочитать после решения или в случае трудностей
Лучше после :)
Это точно трудности?

Основная идея состоит в следующем. Мы можем сразу вызвать sift_down для любой вершины, чьи сыновья являются листьями. Вызвав её для всех таких вершин, получим поддеревья высоты 2, в каждом из которых выполняется основное свойство кучи. И так далее – новые вызовы sift_down будут обеспечивать выполнение основного свойства кучи в поддеревьях всё большего и большего размера. Реализовать это проще всего с помощью цикла for, который вызывает sift_down для всех элементов массива, кроме листьев дерева, справа налево.

IDE

Что быстрее?

Какая из этих реализаций heapify работает быстрее? Почему? (Качественно это можно понять, даже если ваши знания математики не позволяют количественно оценить разницу в их времени работы).

(Для хорошо знающих математику) Довольно очевидно, что каждая из реализаций heapify работает не дольше, чем за $O(n \log n)$, поскольку выполняется $O(n)$ вызовов, каждый из которых работает за $O(h)$. Однако не исключено, что если посчитать точнее, то можно найти лучшую оценку времени – ведь только последние вызовы происходят на куче размера, близкого к $n$, а первые выполняются на куче меньшего размера и, соответственно, занимают меньше времени.
Чтобы это выяснить, надо для каждой реализации сделать одно из двух:
• Доказать, что, по крайней мере в некоторых случаях, время работы действительно имеет порядок $O(n \log n)$.
• Найти и доказать более точную оценку времени, которая меньше, чем $O(n \log n)$.

Прочитать после решения или в случае трудностей
Лучше после :)
Это точно трудности?

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

Можно доказать (см. например, книгу Кормена и др.), что вторая реализация (на основе sift_down) всегда работает за время $O(n)$, а первая в худшем случае – за $O(n$ log $n)$.

K: Сортировка кучей - подробно

Требуется отсортировать по неубыванию с помощью изученного алгоритма целочисленный массив размера N, выводя также некоторые промежуточные результаты работы. А именно, должны быть выведены:
• первоначальная куча, построенная вызовом heapify2;
• куча после удаления каждого элемента (то есть после каждой итерации внешнего цикла);
• отсортированный массив.

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

L: Сортировка кучей

Требуется отсортировать по неубыванию с помощью изученного алгоритма целочисленный массив размера N.

6 10 4 2 2 1 6
1 2 2 4 6 10
IDE

Пакет heapq

Конечно же, столь важная вещь, как работа с кучей, реализована в стандартной библиотеке питона. Во всех задачах ниже можно (и даже желательно) использовать эту библиотеку. Ознакомиться с ним можно на странице с документацией. Хорошего русскоязычного текста я не нашёл, поделитесь ссылкой, если вдруг найдёте :)

От сортировки пузырьком к быстрой сортировке Хоара и поиску медианы

Итак, теперь будем оптимизировать сортировку пузырьком. То, что получится в результате, называется быстрой сортировкой или сортировкой Хоара (quicksort). Мы реализуем лишь самую "наивную" версию этого алгоритма.

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

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

def quicksort(A, begin=0, end=-1): pass
Содержимое функции достаточно просто: сначала выбираем опорный элемент — либо самый первый элемент в списке, либо (лучше) случайный. Далее за один проход по списку переупорядочиваем нашу часть массива так, чтобы сначала шли элементы, строго меньшие опорного, затем больше или равные опорному. При этом сохраняем индекс какого-нибудь опорного элемента. После разделения останется переставить этот опорный элемент так, чтобы до него были только строго меньшие элементы, а после него — больше либо равные. Далее рекурсивно сортируем то, что слева от него, и то, что справа.

Этот алгоритм обладает достаточно забавным свойством: если мы каждый раз будем выпирать опорный элемент очень неудачно (например строго минимальным или максимальным), то время его работы будет порядка n+(n-1)+...+1, то есть O(n2). Однако обычно такого не происходит, и данный алгоритм часто оказывается быстрее некоторых других, гарантирующих работу за n log n.

Процедура разделения массива оказывается полезной ещё и для нахождения медианы (элемента, который в отсортированном массиве стоит посередине), и более обще: k-й порядковой статистики (элемента, который в отсортированном массиве идёт k-ым). Если наш массив имеет длину n, то статистики с номерами 0.05n, 0.25n, 0.5n, 0.75n и 0.95n могут многое рассказать о распределении чисел в массиве. Например, если взять зарплаты в России в 2007 году, то эти статистики получатся примерно такими: 2000, 5000, 9000, 15000, 35000. Заметим, что при таком распределении средняя заработная плата может быть сколь угодно велика (в 2007 она была примерно 15000). Хотя 75% населения получали зарплату не большую 15000р, и более половины населения — вообще менее 10000р.

Идея поиска k-й порядковой статистики в следующем. Выберем случайный опорный элемент и переупорядочим массив так, чтобы сначала шли элементы, строго меньшие опорного, затем равные опорному, и наконец строго большие опорного. Заметим, что сделать такую разбивку чуть сложнее, чем более простую, необходимую для сортировки Хоара. Пусть элементов, строго меньших опорного S<, равных опорному — S=. Тогда сравнивая число k с S< и S<+S= легко понять, в какой части массива нужно искать ответ.

Этот алгоритм снова вероятностный, и если очень не повезёт, то он будет работать за время O(n2), что гораздо хуже, чем отсортировать массив и взять k-й элемент. Однако обычно он работает за время порядка O(n), и именно поэтому оказывается очень полезен.

M: Разделение массива

Реализуйте процедуру разделения массива.

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

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

7 3 1 7 2 4 3 2 3
1 2 2 3 4 7 3
Подсказка
Никто не видит, как я подглядываю...

Операция переупорядочивания массива:
Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше или равен опорному.
Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше опорного.
Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты.
Если r = l — найдена середина массива — операция разделения закончена.

IDE

N: Быстрая сортировка

Реализуйте быструю сортировку Хоара.

1 4 2 3 4
1 2 3 4 4
IDE

O: Поиск медианы

Реализуйте функцию для поиска k-й порядковой статистики.

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

Выведите элемент, который при упорядочении по возрастанию массива стоял бы на K-й позиции.

7 1 1 7 2 4 3 2 3
1
7 7 1 7 2 4 3 2 3
7
7 3 1 7 2 4 3 2 3
2
IDE

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

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

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

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

P: Слияние двух отсортированных массивов

Реализуйте функцию для слияния двух отсортированных массивов.

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

Выведите объединение этих последовательностей, отсортированную по неубыванию.

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

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

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

1 4 2 3 4
1 2 3 4 4
IDE

Что делать, если данные не помещаются в оперативную память

Если данных очень много, то они не поместятся в оперативную память, и стандартные методы сортировки применить будет невозможно. Отличительной особенностью внешних носителей данных является скорость доступа. Скажем, время на получение информации из оперативной памяти в современном компьютере составляет порядка 50нс, а из жёсткого диска — порядка 5мс. Это в сто раз больше. Скорость последовательного чтения с жёсткого диска составляет примерно 200МБ/с, в то время как скорость чтения из оперативной памяти имеет порядок 20ГБ/с, снова в 100 раз быстрее. При непоследовательном доступе к жёсткому диску задержки увеличиваются, скорость сильно падает.

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

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

Предположим, что оперативная память вмещает P элементов, а нам нужно отсортировать P×2k элементов. Тогда мы первый раз прочитаем и запишем каждый элемент при подготовке серий. В результате P×2k чтений-записей получатся серии длины P. После первого слияния мы получим серии длины P×21, затем P×22 и так далее. В результате потребуется (k+1) полных прочтений и записей данных на диск.

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

Существует красивая идея, которая позволяет после первого прохода получить отсортированные серии длиной не P, а в среднем 2P. Если же при этом данные будут частично отсортированы, то длины серий будут ещё больше. Об этой идее есть задача ниже.

Теперь представим себе, что мы можем выполнять эффективное слияние не 2-х массивов, а сразу 4-х. Тогда после первого слияния мы получим серии длиной сразу P×22, а итоговое количество чтений-записей данных станет почти в два раза меньше!

А если сливать не 4-е массива, а сразу, скажем, 1024? Или даже 1048576 (если P>1048576)? Тогда чтений-записей будет почти в 10 раз меньше (или даже в 20)! Однако здесь есть некоторая проблема: если сливаемых массивов станет слишком много, и доступ к информации на диске станет по большей части случайным, а не последовательным. И время доступа увеличится. Раз в 10-100. И мы потеряем всё, чего добились. Лучше всего, если у нас будет несколько жёстких дисков, тогда мы сможем взаимодействовать с ними параллельно, и увеличить количество одновременно сливаемых серий без потери скорости.

R: Слияние нескольких упорядоченных массивов

Реализуйте функцию для слияния нескольких отсортированных массивов.

В первой строке даётся натуральное число N — количество массивов. В следующих N строках даны отсортированные по неубыванию массивы.

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

3 1 4 5 1 3 5 1 2 5
1 1 1 2 3 4 5 5 5
Подсказка
Я — овощ, и не хочу думать
Никто не видит, как я подглядываю...

Необходимо собрать кучу из N троек (начальный элемент i-го массива, i, 0). После этого нужно последовательно извлекать из кучи минимальную тройку. Первый элемент тройки — минимальный ещё не выведенный элемент, его нужно отправить на вывод. А второй элемент тройки — номер массива, из которого нужно взять элемент и назад добавить в кучу, а третий — индекс последнего взятого элемента из этого массива.

IDE

S: Формирование серий для внешней сортировки

В этой задаче мы представим себе, что у нас есть оперативной памяти на P чисел, и последовательность целых чисел, которую необходимо отсортировать. Её длина существенно больше P.

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

Считаем первые P чисел и сформируем из них минимальную кучу. Дальше извлекаем минимальный элемент из кучи и сразу же добавляем его в текущую серию. После этого считываем очередной элемент последовательности. Если он равен элементу, который мы только что вывели, то его тоже можно добавить в серию (вывести) и продолжить дальше. Если он больше текущего, то он может быть добавлен в серию в будущем. Для этого его нужно включить в кучу и продолжить работу. Однако если новый элемент меньше текущего, то его нельзя добавить в текущую серию. Тогда добавим его во вторую кучу. Размер первой кучи при этом уменьшится на 1, а размер второй — увеличится на 1, в сумме мы по-прежнему храним P элементов. Будет продолжаться до тех пор, пока все P элементов станут непригодными для добавления в текущую серию (и окажутся во второй куче, тогда как первая станет пустой). Это значит, что текущую серию нужно закончить, поменять кучи местами и начать новую серию.

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

В первой строке даны два числа P и N — количество элементов, помещающихся в оперативную память, и длина последовательности для сортировки соответственно. Во второй строке дана последовательность целых чисел длины N.

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

Следующей строчкой выведите среднюю длину серий, округлённую до двух знаков после запятой.

4 21 31 12 50 14 8 59 9 43 91 93 32 81 67 52 41 52 63 67 77 74 65
12 14 31 50 59 91 93 8 9 32 43 52 52 63 67 67 74 77 81 41 65 7.0
IDE

T: Внешняя сортировка

Достаточно эффективная внешняя сортировка может быть реализована следующим образом: сначала мы формируем начальные серии (так как делали это в предыдущей задаче) и записываем их последовательно в N различных "файлов" (первую серию в первый файл, вторую — во второй и т.д.). После этого, мы начинаем сливать N-ки отсортированных серий вместе, получающиеся серии при этом записывать в другие N различных "файлов". После того, как все N-ки серий будут слиты, мы начинаем сливать N-ки серий второго порядка и записывать их в первые N файлов. Будем продолжать операцию до тех пор, пока весь массив не будет отсортирован.

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

Выполните внешнюю сортировку данных по описанному алгоритму.

Перепишите вашу программу так, чтобы использовались реальные файлы. При каком N достигается максимальная производительность сортировки на вашем компьютере?

4 2 21 31 12 50 14 8 59 9 43 91 93 32 81 67 52 41 52 63 67 77 74 65
8 9 12 14 31 32 41 43 50 52 52 59 63 65 67 67 74 77 81 91 93
IDE

Разные задачи

U: Коммерческий калькулятор

Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму N натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым оказывается нарушен классический принцип “от перестановки мест слагаемых сумма не меняется”). Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в 1.05 €), потом результат с 12 (1.65 €), и затем с 13 (2.3 €), то всего мы заплатим 5 €, если же сначала отдельно сложить 10 и 11 (1.05 €), потом 12 и 13 (1.25 €) и, наконец, сложить между собой два полученных числа (2.3 €), то в итоге мы заплатим лишь 4.6 €. Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных N чисел.

Входные данные Первая строка входных данных содержит число N (2 ≤ N ≤ 105). Во второй строке заданы N натуральных чисел, каждое из которых не превосходит 10000.

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

4 10 11 12 13
4.60
2 1 1
0.10
IDE

V: Тупики

На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).

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

Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

Входные данные Сначала вводятся число K — количество тупиков и число N — количество электропоездов (1≤K≤100000, 1≤N≤100000). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 109. Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.

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

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

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

W: Менеджер памяти

Пете поручили написать менеджер памяти для новой стандартной библиотеки языка H++. В распоряжении у менеджера находится массив из N последовательных ячеек памяти, пронумерованных от 1 до N. Задача менеджера — обрабатывать запросы приложений на выделение и освобождение памяти.

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

Запрос на освобождение памяти имеет один параметр T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером T — запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером T был отклонен, то текущий запрос на освобождение памяти игнорируется.

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

Входные данные В первой строке входных данных задаются числа N и M — количество ячеек памяти и количество запросов, соответственно (1 ≤ N ≤ 2311; 1 ≤ M ≤ 105). Каждая из следующих M строк содержит по одному числу: (i+1)-я строка входных данных (1 ≤ i ≤ M) содержит либо положительное число K, если i-й запрос — запрос на выделение с параметром K (1 ≤ K ≤ N), либо отрицательное число –T, если i-й запрос — запрос на освобождение с параметром T (1 ≤ T < i).

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

42 9 7 3 8 -2 6 5 -5 9 4
1 8 11 19 25 30 19
IDE