Поиск и сортировка
Между однотипными информационными объектами (например, числами или строками) возможны различные операции отношения. Некоторые из этих отношений могут быть очевидны и использоваться очень часто, например: «число A больше числа B», «строка A длиннее строки B», «слово A при алфавитном порядке должно стоять раньше слова B». Некоторые отношения могут возникать только при решении задач отдельного вида.
Большинство отношений, с которыми мы сталкиваемся в реальной жизни, обладают следующим свойством: если отношение верно для пары объектов (A,B) и верно для пары объектов (B,C), то из этого следует что оно верно также и для пары (A,C). Такие отношения называются транзитивными. Примером может служить отношение «тяжелее чем». И верно: если известно, что A тяжелее B, а B тяжелее C, то и без взвешивания понятно, что A тяжелее C. В качестве другого примера можно взять отношение «строка длиннее чем». Если известно, что строка A длиннее B, а B длиннее C, то не нужно никаких дополнительных операций чтобы заключить что A длиннее С.
Взяв за основу то или иное транзитивное отношение, данные можно выстраивать в последовательности таким образом, чтобы оно выполнялось для любой пары соседних элементов. Например, последовательность 3, 6, 7, 10, 11, 12, 20, 24 построена на основе отношения «больше». В любой паре последующий элемент больше предыдущего. А поскольку отношение «больше» является транзитивным, то это же будет верно для цепочки подряд идущих элементов любой длины и для всей последовательности в целом (так как второй элемент больше первого, третий больше второго и так далее, то последний больше первого). О расположенных таким образом элементах принято говорить, что они расположены в порядке возрастания.
Приведем другой пример. Последовательность слов ‘a’, ‘an’, ‘the’, ‘then’, ‘image’, ‘window’ выстроена в упорядоченную цепочку на основе соотношения «длиннее».
Еще один пример. На основе алфавитного порядка слов можно получить цепочку: “at”, “bat”, “cat”, “dog”, “mouse”, “rat”.
Процесс, при котором из некоторого набора исходных данных получается такая закономерная цепочка, называется сортировкой. Как и многие другие процессы, сортировка может быть представлена в виде алгоритма. Основное требование к алгоритму сортировки – это гарантия результата (то есть получения упорядоченного набора данных) при любом расположении исходных данных.
Прежде чем перечислить основные алгоритмы сортировки желательно, чтобы читатель прислушался к следующим соображениям. При написании программы есть выбор: реализовать алгоритм, который будет работать быстро (и при этом потратить время на его изучение, отладку, «поимку» частных случаев) или написать хорошо знакомый алгоритм (который может быть и не является самым оптимальным в своей «весовой категории», но зато не будет отвлекать внимание от решения основной задачи). Вовсе не обязательно хорошо знать и уметь писать все алгоритмы сортировки, которые будут разобраны в этой главе, достаточно выбрать для себя какой-то наиболее привлекательный и научиться его реализовывать по-настоящему хорошо. Чутье подсказывает, что выбор алгоритмов и методов работы с данными должен делаться для каждой задачи отдельно, в зависимости от количества данных, сложности и других параметров. Другими словами, если мы пишем программку «только для себя», в которой будет не более тысячи чисел – можно выбрать один метод сортировки, если программой будут пользоваться тысячи человек (например, будут обращаться к какому-нибудь Интернет-серверу) и данных ожидается порядка нескольких миллиардов – то тут есть смысл искать менее знакомые, но более оптимальные алгоритмы.
И, перед тем как перейти к описаниям алгоритмов оговоримся, что все примеры будут касаться сортировки массивов, состоящих из целых чисел в порядке возрастания. Константой N будет обозначено количество элементов массива.
Метод выбора
Давайте представим себе, что перед нами на листе бумаги написан набор чисел, который необходимо отсортировать по возрастанию. Как мы будем действовать? Один из возможных вариантов – найти наименьшее число и записать его в ответ первым, потом следующее за ним по величине и записать вторым, потом следующее и так далее.
Именно по такой стратегии и действует метод выбора. Просмотрим все элементы массива и найдем наименьшее число (можно находить и наибольшее, тогда немного изменятся дальнейшие действия, но сама эффективность метода не пострадает). Поменяем его с первым. Затем опять будем искать наименьший элемент, но уже не во всем массиве, а начиная со второго. Найденное число поставим на второе место в массиве. Теперь уже два самых маленьких элемента поставлены нами на «свои» места. Повторим поиск наименьшего, начиная с третьего элемента и поставим найденное число на третье место в массиве. Будем действовать по такой схеме, пока не упорядочим весь массив.
Рассмотрим поэтапно работу данного метода на примере. Пусть дан исходный массив:
| 8 | 4 | 12 | 6 | 3 | 2 | 10 | 7 |
На первом шаге среди всех элементов массива найдем наименьший:
| 8 | 4 | 12 | 6 | 3 | 2 | 10 | 7 |
и поменяем его местами с первым.
| 2 | 4 | 12 | 6 | 3 | 8 | 10 | 7 |
В этот момент массив можно мысленно разделить на две части. В левой, упорядоченной, хранятся уже рассмотренные элементы, расположение которых, к тому же, не изменится. В правой 0 еще неупорядоченные элементы. Повторим предыдущий шаг (поиск минимума и постановку его, путем обмена на первое место), но уже как бы с «укороченным» массивом (с той частью, где элементы еще не упорядочены). Найдем наименьший из оставшихся элементов:
| 2 | 4 | 12 | 6 | 3 | 8 | 10 | 7 |
и поместим его в этот раз на второе место путем обмена со вторым элементом:
| 2 | 3 | 12 | 6 | 4 | 8 | 10 | 7 |
Повторим процесс для еще неупорядоченной части массива. Найдем в правой, неупорядоченной части наименьший элемент:
| 2 | 3 | 12 | 6 | 4 | 8 | 10 | 7 |
и поставим его на третье место в массиве.
| 2 | 3 | 4 | 6 | 12 | 8 | 10 | 7 |
Снова найдем наименьший элемент и поставим его на четвертую позицию:
| 2 | 3 | 4 | 6 | 12 | 8 | 10 | 7 |
Пятый шаг. Найдем наименьший элемент:
| 2 | 3 | 4 | 6 | 12 | 8 | 10 | 7 |
Поставим его на пятую позицию:
| 2 | 3 | 4 | 6 | 7 | 8 | 10 | 12 |
Повторим поиск и обмен до тех пор, пока в правой, неупорядоченной части массива не останется всего один элемент. Поскольку все элементы, кроме оставшегося были выбраны ранее, то они меньше его, так как на каждом шаге мы искали наименьший элемент. Это означает, что последний элемент будет самым большим в массиве и он должен стоять на последнем месте, где уже и находится. Поэтому чтобы поставить все элементы массива на их места достаточно повторить описанную процедуру N-1 раз.
Для реализации данного метода необходим двойной цикл. Параметром внешнего цикла может быть, например, количество уже упорядоченных элементов. Как уже отмечалось, во внешнем цикле достаточно N-1 шагов. Внутренний цикл обеспечивает поиск наименьшего элемента (а точнее, его номера) среди тех, которые еще не упорядочены. После этого элемент с найденным номером и первый элемент неупорядоченной части массива меняются местами.
Фрагмент программы может быть написан, к примеру, так:
const N = 100; var a : array [1..N] of integer; first : integer; <позиция, с которой начинается «неупорядоченная часть
массива. это число также равно номеру текущего шага цикла> i : integer; imin : integer; temp : integer; begin for first := 1 to N — 1 do < последовательно отодвигаем границу неупорядоченной части>begin imin := first; for i := first + 1 to N do if a[i] < a[imin] then imin:=i; temp := a[first]; a[first] := a[imin]; a[imin] := temp; end; end.
Время работы этого метода можно оценить как O(N 2 ) при любых исходных данных. Действительно, на первом шаге, чтобы найти наименьшее число необходимо сделать N-1 сравнение. На втором шаге – N-2, на третьем N-3 и так далее, на последнем шаге останется сделать всего 1 сравнение. То есть общее количество операций можно выразить по формуле суммы арифметической прогрессии: (N-1)+(N-2)+. +3+2+1=((N-1)+1)(N-1)/2 = N(N-1)/2.
Метод вставки
Идея данного метода состоит в следующем. Пусть есть несколько элементов, уже упорядоченных по возрастанию и к ним требуется добавить новый. Найдем такую позицию, куда этот элемент можно поставить, не нарушая упорядоченности массива. Все элементы массива, начиная с найденной позиции, сдвинем вправо и поставим новый элемент на освободившееся место.
Рассмотрим пример. Пусть дана уже упорядоченная часть массива, состоящая из пяти чисел:
| 2 | 5 | 7 | 12 | 18 |
И пусть сюда необходимо добавить новое число 9. Очевидно, что это число должно в массиве занимать позицию номер 4. Сдвинем числа, освободив нужную позицию. Получим:
| 2 | 5 | 7 | 12 | 18 |
После этого ничто не мешает поставить новое число на освободившееся место.
| 2 | 5 | 7 | 9 | 12 | 18 |
Данный метод, в частности, позволяет формировать уже упорядоченный массив на этапе его ввода, по мере поступления данных. Такая программа может выглядеть, например, так:
const N = 100; var a : array [1..N] of Integer; k,i,j : integer; data : integer; begin <1>for k:=1 to N do begin read(data); i:=k-1; while (i > 0)and (a[i] > data) do dec(i); inc(i); for j := k — 1 downto i do a[j + 1] := a[j]; a[i] := data; end; end.
Пояснения к тексту программы. В строке k – это порядковый номер числа, которое на текущем шаге добавляется к массиву. Это означает, что в массиве на момент этого шага k-1 число, причем эти числа уже упорядочены . Строка представляет собой последовательный поиск справа налево, то есть от больших элементов к меньшим. Цикл закончится либо когда i будет равно 0, либо когда элемент номер i будет меньше того, который мы хотим добавить. В любом случае, сдвигать мы должны элементы массива с номерами от i+1 и далее . Примечание общего порядка: данные по которым делается поиск – упорядочены, это позволяет использовать бинарный или любой другой более быстрый метод поиска. Поэтому при определении времени работы алгоритма будем ориентироваться на операции сдвига, а временем на операции поиска вообще можно пренебречь. Строка – цикл, сдвигающий элементы массива.
Время работы данного алгоритма в худшем случае как O(N 2 ). Худшим будет случай, когда для вставки нового элемента нужно будет двигать все предыдущие, то есть когда на вход подается массив, упорядоченный в обратную сторону.
В отличие от метода выбора, данный метод в лучшем случае (когда сдвигать ничего не нужно) будет работать за O(N). Если рассмотреть средний случай, то время будет O(N 2 ).
Метод становится очень эффективным в случае, если необходимо в уже упорядоченный массив внести некие небольшие изменения. В этом случае несколько вставок будут выполняться быстрее, чем сортировка всего массива заново каким-то другим методом.
Метод простого обмена
Перед тем, как излагать этот метод сортировки, внимательно прислушаемся к одному небольшому примечанию. Массив упорядочен по возрастанию, если меньшие числа в нем стоят раньше больших. Чем меньше число, тем раньше оно должно стоять в массиве, чем больше число – тем позже. Другими словами, чем больше число, тем больше его номер в массиве (индекс).
Если мы последовательно рассмотрим все пары соседних чисел, и в каждой из них это свойство выполняется, то массив можно считать упорядоченным.
Именно на этом и базируется основная идея метода обмена. Будем сравнивать пары соседних элементов массива. Если в какой-то паре большее число стоит левее меньшего, то их надо поменять местами.
Рассмотрим работу метода на примере. Пусть дан массив из 6 целых чисел, которые необходимо расположить в порядке возрастания.
| 4 | 3 | 5 | 8 | 6 | 2 |
Двигаться будем слева направо (хотя это не принципиально).
Шаг 1. Сравним 4 и 3. Число 4 больше (а значит должно стоять правее) — меняем местами эти элементы. Новый массив:
| 3 | 4 | 5 | 8 | 6 | 2 |
Независимо от того, меняли мы местами элементы или нет – просто переходим к следующей паре.
Шаг 2. Сравним 4 и 5. Числа в паре стоят в «правильном» порядке – меньшее левее большего. Ничего не делаем с этими элементами. Массив остается:
| 3 | 4 | 5 | 8 | 6 | 2 |
Переходим к следующей паре.
Шаг 3. Сравниваем 5 и 8. Эти числа также стоят в «правильном» порядке, поэтому массив не изменяется:
| 3 | 4 | 5 | 8 | 6 | 2 |
Берем следующую пару.
Шаг 4. Сравниваем 8 и 6. Здесь большее число стоит левее меньшего, поэтому меняем числа местами, получаем новый массив:
| 3 | 4 | 5 | 6 | 8 | 2 |
Переходим к следующей паре.
Шаг 5. Сравниваем 8 и 2.Опять большее число левее меньшего – переставляем числа.
| 3 | 4 | 5 | 6 | 2 | 8 |
Правда, массив пока мало похож на отсортированный. Однако, можно сделать одно важное наблюдение: после полного прохода по массиву хотя бы одно число (а именно – самое большое) будет поставлено на свое место. Именно поэтому в некоторых книжках этот метод также носит название «метод пузырька» или просто «пузырек». Наибольшее число, как пузырек из глубины стакана с газировкой, «всплывает» на поверхность (на последнее место в массиве) и остается там.
Теперь, если мы сделаем второй проход по массиву, то еще одно число встанет на свое место (а может быть и не одно, но об этом чуть позже). Значит, чтобы гарантированно получить отсортированный массив, надо сделать столько проходов, сколько элементов в массиве.
(Небольшое отступление: на самом деле достаточно сделать N-1 проход по массиву, потому что когда все числа кроме одного будут на своих местах, последнее тоже само собой окажется на своем месте)
Итак, мы выяснили, что для успешной сортировки надо сделать N-1 проход, по N-1 сравнению на каждом проходе. Таким образом уже вырисовывается структура программы – двойной цикл. Внешний цикл – по количеству проходов, внутренний – по тем парам элементов, которые мы сравниваем.
Пример программы сортировки массива
По структуре программы видно, что такая сортировка требует (N-1)(N-1) операций. То есть время работы программы можно оценить как O(N 2 ).
Приведем пару соображений по оптимизации написанного кода. Представим себе, что у нас есть массив на два миллиона чисел, и мы уже сделали миллион проходов. Это значит, что как минимум миллион чисел в массиве уже стоят на своих законных местах в конце массива. Следовательно, нет никакого смысла проходить правую половину массива, потому что там никаких изменений точно уже не будет. Итак, если на первом проходе мы делаем N-1 сравнение, то на втором достаточно N-2, на третьем — N-3 и так далее по мере увеличения количества чисел, которые стоят на своих местах. Таким образом кусочек программы, отвечающий за сортировку можно переписать так:
Как видите, изменился ровно один символ. В первом цикле разность N-1 заменена разностью N-i. Однако, количество операций (а вместе с ним и время работы) нам удалось сократить вдвое. Это легко увидеть, если нарисовать следующий график:
Площадь закрашенного треугольника будет как раз представлять количество сравнений. А треугольник есть ничто иное как половинка квадрата со стороной (N-1). Хотя, следует признать, что оценка времени работы алгоритма все еще составляет O(N 2 ).
Второе соображение для оптимизации метода простого обмена основано на таком утверждении: если за полный проход в массиве не сделано ни одной перестановки, то его можно считать отсортированным. Что значит «не сделано ни одной перестановки»? Это значит, что все пары соседних чисел расположены «правильно», то есть большее число идет позже меньшего, поэтому они в перестановках не нуждаются. Это позволяет значительно сократить время в случаях, когда более или менее повезло с исходными данными.
Например, в массиве ( 8, 1, 2, 3, 4, 5, 6 ) будет вообще достаточно одного прохода, чтобы вытолкнуть восьмерку на последнее место.
Существенных изменений в структуре программы не будет – как был двойной цикл, так и остался. Просто внешний цикл будет заменен на цикл с условием. Программа в этом случае может выглядеть, например, так:
Стоит заметить, что в худшем случае (а именно, если на входе дан массив, упорядоченный в другую сторону) время работы все равно будет составлять O(N 2 ) и по количеству операций сравнения программа не будет отличаться от предыдущего примера.
Сортировка с убывающими смещениями
Сразу оговоримся, что существует такой вариант исходных данных, при которых данный метод будет работать за время O(N2). Однако, в среднем случае этот метод способен дать значительный выигрыш по времени по сравнению с методом простого обмена.
Заметим следующее: каждый проход метода простого обмена способен сместить элемент массива не более чем на одну позицию влево. Поэтому, наибольшее время займет работа метода простого обмена в случаях, когда наименьший элемент находится на последнем месте. В методе обмена с убывающими смещениями добавляются несколько первых шагов, цель которых при необходимости поменять местами элементы, находящиеся друг от друга на расстоянии большем единицы. То есть поместить числа по возможности поближе к их окончательным позициям в массиве. Тогда количество шагов для метода простого обмена значительно сократится.
Итак, давайте рассмотрим работу этого метода на примере. Пусть дан массив из 8 чисел, который требуется упорядочить по возрастанию:
| 4 | 6 | 8 | 2 | 5 | 0 | 1 | 7 |
Выберем шаг d=[N/2] (в какую сторону округлять, в принципе не очень важно, обычно размеры массивов таковы, что на фоне тысяч элементов единичка при округлении как-то не замечается).
В нашем примере шаг будет равен d=[8/2]=4.
На первом проходе будем сравнивать пары элементов массива, расположенные на расстоянии d. В нашем примере это будут 1-й и 5-й, 2-й и 6-й, 3-й и 7-й, 4-й и 8-й. Как и ранее, в методе простого обмена, если расположение элементов в паре нас не устраивает – будем менять их местами.
Покажем подробно первый проход:
| 4 | 6 | 8 | 2 | 5 | 0 | 1 | 7 |
Шаг 1. Сравнить числа 4 и 5. Местами менять не будем.
| 4 | 6 | 8 | 2 | 5 | 0 | 1 | 7 |
Шаг 2. Сравнить числа 6 и 0. Поменять местами, чтобы большее стояло правее. Расположение чисел в массиве станет таким:
| 4 | 0 | 8 | 2 | 5 | 6 | 1 | 7 |
| 4 | 0 | 8 | 2 | 5 | 6 | 1 | 7 |
Шаг 3. Сравнить числа 8 и 1. Поменять местами. Теперь в массиве числа будут расположены так:
| 4 | 0 | 1 | 2 | 5 | 6 | 8 | 7 |
| 4 | 0 | 1 | 2 | 5 | 6 | 8 | 7 |
Шаг 4. Сравнить числа 2 и 7 и оставить их на своих местах.
После такого подготовительного прохода элементы массива расположены довольно близко к тем местам, которые они должны занять после сортировки. По крайней мере все «большие» элементы находятся в правой половине, все «маленькие» — в левой. Конечно, так будет далеко не всегда, но в среднем случае такие подготовительные действия могут быть очень полезны.
Далее, если d > 1, то d уменьшаем в 2 раза и делаем еще один проход. Теперь будем сравнивать числа, находящиеся на расстоянии 2: 1-е и 3-е, 2-е и 4-е, 3-е и 5-е, 4-е и 6-е, 5-е и 7-е, 6-е и 8-е.
После первого прохода массив был таким:
| 4 | 0 | 1 | 2 | 5 | 6 | 8 | 7 |
Разберем второй проход пошагово:
| 4 | 0 | 1 | 2 | 5 | 6 | 8 | 7 |
Шаг 1. Сравним 4 и 1. Они расположены не так, как нам это нужно. Поменяем местами. Числа в массиве будут расположены так:
| 1 | 0 | 4 | 2 | 5 | 6 | 8 | 7 |
| 1 | 0 | 4 | 2 | 5 | 6 | 8 | 7 |
Шаг 2. Сравним 0 и 2. Их расположение нас устраивает, поэтому просто перейдем к следующей паре.
| 1 | 0 | 4 | 2 | 5 | 6 | 8 | 7 |
Шаг 3. Сравним 4 и 5. Эти числа должны остаться на своих местах.
| 1 | 0 | 4 | 2 | 5 | 6 | 8 | 7 |
Шаг 4. Сравним 2 и 6. Переставлять также не надо.
| 1 | 0 | 4 | 2 | 5 | 6 | 8 | 7 |
Шаг 5. Сравним 5 и 8. Опять переставлять не надо.
| 1 | 0 | 4 | 2 | 5 | 6 | 8 | 7 |
Шаг 6. Сравним 6 и 7. И здесь также переставлять не надо.
Проход закончен. Получен массив:
| 1 | 0 | 4 | 2 | 5 | 6 | 8 | 7 |
Теперь, уменьшив d в 2 раза, получим d=1. С этого момента метод работает как метод простого обмена с проверкой, случались ли перестановки элементов на последнем проходе или нет.
Что касается нашего примера, то для его сортировки достаточно двух проходов – одного чтобы расположить все числа в нужном порядке и второго, чтобы убедиться что перестановок не произойдет.
Структура программы не сильно изменилась по сравнению с предыдущими примерами – все тот же двойной цикл. Внешний цикл в случае необходимости изменяет величину шага d, и условием выхода из него является отсутствие перестановок при d=1. Внутренний цикл организует полный проход по массиву со сравнением всех пар элементов на расстоянии d.
Текст программы может выглядеть, например, так:
Чем же так принципиальны те строки, которые выделены в тексте программы? Своим расположением. Порядком выполнения. Наиболее часто встречающейся ошибкой в реализации этого метода является такой порядок действий:
d:=N div 2; <сразу>repeat if d > 1 then d:=d div 2; until (d=1)and(not(flag));
В случае такого написания метод может просто перестать работать. Допустим, что только что закончился проход с шагом d=2, и на этом проходе не было перестановок. Следует ли из этого, что массив упорядочен? Нет. Далее сразу после прохода следует уменьшение d и он становится равным 1. И тут мы подходим к проверке условия окончания цикла. И оно выполняется. Чего быть не должно. Потому что с шагом d=1 прохода еще не было.
Сортировки — квадратичные и сортировка слиянием
Мы считаем, что вы уже знаете и умеете следующие вещи: * основы языков Python, C++ или Java (примеры в конспектах будут только на C++) * оператор if * циклы for и while * создание функций * концепцию рекурсии * поиск минимума в массиве
Квадратичные сортировки
Задача сортировки массива заключается в том, чтобы расставить его элементы в определённом порядке (чаще всего — по неубыванию. Это означает, что каждый элемент должен быть больше или равен всех предыдущих).
А именно мы хотим написать такую функцию sort_array , которая принимает массив в качестве аргумента и сортирует его элементы:
def sort_array(array): # надо придумать, что написать здесь array = [1, -3, 7, 88, 7] sort_array(array) print(array)[1, -3, 7, 88, 7]Задание
Какие вы знаете алгоритмы сортировки?
Если вы не знаете ни одного алгоритма, то придумайте какой-нибудь разумный алгоритм сами.
Сортировка пузырьком
Это самый популярный алгоритм сортировки, хоть он и не самый очевидный.
Пусть \(N\) — длина массива. Сортировка пузырьком заключается в том, что мы просто \(N\) раз пройдемся по массиву и будем менять два соседних элемента, если первый больше второго.
Ссылка на красивую визуализацию: https://visualgo.net/nl/sorting
Заметьте, как каждую итерацию максимальный элемент “всплывает как пузырек” к концу массива.
def bubble_sort(array): n = len(array) # длина массива for i in range(n): # n раз выполняем цикл for j in range(n - 1): # проходимся по всем элементам кроме последнего if array[j] > array[j + 1]: # сравниваем элемент по следующим a[j], a[j + 1] = a[j + 1], a[j] # меняем местами, если следующий меньше a = [1, -3, 7, 88, 7] bubble_sort(a) print(a)[-3, 1, 7, 7, 88]Заметьте, что после \(i\) шагов алгоритма сортировки пузырьком последние \(i + 1\) чисел всегда отсортированы. Именно поэтому алгоритм и работает.
И именно поэтому его можно немного ускорить.
Задание
Подумайте, какие лишние элементы мы перебираем. Как нужно изменить границы в двух циклах for, чтобы не делать никаких бесполезных действий?
Сортировка выбором
Более понятным и придумываемым способом является сортировка выбором минимума (или максимума).
Чтобы отсортировать массив, нужно просто \(N\) раз выбрать минимум среди еще неотсортированных чисел. То есть на \(i\) -ом шаге ищется минимум на отрезке \([i, n — 1]\) , и этот минимум меняется с \(i\) -ым элементом, теперь отрезок \([0, i]\) отсортирован.
Сортировка вставками
Также существует сортировка вставками.
Префиксом длины \(i\) будем называть первые \(i\) элементов массива.
Тогда пусть на \(i\) -ом шаге у нас уже будет отсортирован префикс до \(i\) -го элемента. Чтобы этот префикс увеличить, нужно взять элемент, идущий после него, и менять с левым соседом, пока этот элемент наконец не окажется больше своего левого соседа. Если в конце он больше левого соседа, но меньше правого — это значит, что мы правильно вставили этот элемент в отсортированную часть массива.
Задание
Сдайте 4 первые задачи в контесте:
- Напишите сортировку пузырьком.
- Напишите сортировку выбором максимума.
- Напишите сортировку вставками.
- Выберите любой алгоритм и примените его для сортировки пар.
При сдаче задач нельзя пользоваться встроенной сортировкой!
Сортировка подсчетом
Предыдущие три алгоритма работали с массивами, в которых лежат абсолютно любые объекты, которые можно сравнивать. Любые числа, строки, пары, другие массивы, почти все что угодно.
Но в особых случаях, когда элементы принадлежат какому-то маленькому множеству, можно использовать другой алгоритм — сортировку подсчетом.
Пусть, например, нам гарантируется, что все числа натуральные и лежат в промежутке от 1 до 100.
Тогда есть такой простой алгоритм: создадим массив размера \(100\) , в котором будем хранить на \(i\) -ом месте, сколько раз число \(i\) встретилось в этом массиве. Пройдемся по всем числам, и увеличим соответствующее значение массива на \(1\) . Таким образом мы подсчитали, сколько раз какое число встретилось. Теперь можно просто пройтись по этому массиву и вывести \(1\) столько раз, сколько раз встретилась \(1\) , вывести \(2\) столько раз, сколько встретилась \(2\) , и так далее.
Задание
Сдайте 5, 6 и 7 задачи в контесте:
- Напишите сортировку подсчетом.
- Придумайте, как преобразовать сортировку подсчетом, чтобы она работала быстро.
- Придумайте, как использовать идею сортировки подсчетом в этой задаче.
При сдаче задач нельзя пользоваться встроенной сортировкой!
О-нотация
Очень часто требуется оценить, сколько времени работают эти алгоритмы. Но тут возникают проблемы:
- на разных компьютерах время работы всегда будет слегка отличаться;
- чтобы измерить время, придётся запустить сам алгоритм, но иногда приходится оценивать алгоритмы, требующие часы или даже дни работы.
Зачастую основной задачей программиста становится оптимизировать алгоритм, выполнение которого займёт тысячи лет, до какого-нибудь адекватного времени работы. Поэтому хотелось бы уметь предсказывать, сколько времени займёт выполнение алгоритма ещё до того, как мы его запустим.
Для этого давайте для начала попробуем оценить число операций в алгоритме.
Возникает вопрос: какие именно операции считать. Можно считать любые элементарные операции: * арифметические операции с числами: +, -, *, / * сравнение чисел: , =, ==, != * присваивание: a[0] = 3
При этом надо учитывать, как реализованы некоторые отдельные вещи в самом языке. Например, в питоне срезы массива ( array[3:10] ) копируют этот массив, то есть этот срез работает за 7 элементарных действий. А swap , например, может работать за 3 присваивания.
Задание
Попробуйте посчитать точное число сравнений в сортировках пузырьком, выбором, вставками и подсчетом в худшем случае (это должна быть какая формула, зависящая от \(N\) — длины массива). Для сортировки подсчетом давайте считать, что все числа целые и лежат в промежутке от 1 до \(M\)
И также посчитайте точное число присваиваний в сортировках пузырьком, выбором, вставками и подсчетом в худшем случае. Давайте считать, что swap — это 3 присваивания.
Ниже будут ответы
В худшем случае алгоритмы работают за столько сравнений:
- Сортировка пузырьком (без улучшения): \(N(N-1)\)
- Сортировка пузырьком (с улучшением): \((N-1) + (N-2) + \ldots + 1 = \frac\)
- Сортировка выбором: \((N-1) + (N-2) + \ldots + 1 = \frac\)
- Сортировка вставками: \(1 + 2 + \ldots + (N-1) = \frac\)
- Сортировка подсчетом: нет сравнений
И столько присваиваний: * Сортировка пузырьком (без улучшения): \(3\frac\) * Сортировка пузырьком (с улучшением): \(3\frac\) * Сортировка выбором: \(3(N-1) + \frac\) * Сортировка вставками: \(3\frac\) * Сортировка подсчетом: \(N + M\) ( \(M\) — это создание массива)
Но чтобы учесть все элементарные операции, ещё надо посчитать, например, сколько раз прибавилась единичка внутри цикла for . А ещё, например, строчка n = len(array) — это тоже действие.
Также не сразу очевидно, какой из этих алгоритмов работает быстрее. Сравнивать формулы сложно. Хочется придумать способ упростить эти формулы так, чтобы:
- не нужно было учитывать много информации, не очень сильно влияющей на итоговое время;
- легко было оценивать время работы разных алгоритмов для больших чисел;
- легко было сравнивать алгоритмы на предмет того, какой из них лучше подходит для тех или иных входных данных.
Для этого придумали \(O\) -нотацию — асимптотическое время работы вместо точного (часто его ещё называют асимптотикой).
Пусть \(f(N)\) — это какая-то функция. Говорят, что алгоритм работает за \(O(f(N))\) , если существует число \(C\) , такое что алгоритм работает не более чем за \(C \cdot f(N)\) операций.
В таких обозначениях можно сказать, что * Сортировка пузырьком работает за \(O(N^2)\) * Сортировка выбором работает за \(O(N^2)\) * Сортировка вставками работает за \(O(N^2)\) * Сортировка подсчетом работает за \(O(N + M)\)
Это обозначение удобно тем, что оно короткое и понятное, а также оно не зависит от умножения на константу или прибавления константы. Если алгоритм работает за \(O(N^2)\) , то это может значить, что он работает за \(N^2\) , за \(N^2 + 3\) , за \(\frac\) или даже за \(1000 \cdot N^2 + 1\) действие. Главное, что функция ведет себя как \(N^2\) , то есть при увеличении \(N\) (в данном случае это длина массива) он увеличивается как некоторая квадратичная функция. Например, если увеличить \(N\) в 10 раз, время работы программы увеличится приблизительно в 100 раз.
Поэтому все эти рассуждения про то, сколько операций в swap или считать ли отдельно присваивания, сравнения и циклы — отпадают. Как бы вы ни ответили на эти вопросы, они меняют ответ на константу, а значит асимптотическое время работы алгоритма никак не меняется.
Задание
Найдите асимптотику данных функций. Максимально упростите ответ (например, до \(O(N)\) , \(O(N^2)\) и т. д.).
- \(\frac\)
- \(\frac\)
- \(1 + 2 + 3 + \ldots + N\)
- \(1^2 + 2^2 + 3^2 + \ldots + N^2\)
- \(\log + 3\)
- \(7\)
- \(10^\)
Задание
Найдите асимптотическое время работы данных функций:
def f(n): s = 0 for i in range(n): for j in range(n): s += i * j return s f(10)2025def g(n): s = 0 for i in range(n): s += i for i in range(n): s += i * i return s g(10)def h(n): if n == 0: return 1 return h(n - 1) * n h(10)3628800Задание
Найдите лучшее время работы алгоритмов, решающих данные задачи: * Написать числа от \(1\) до \(N\) * Написать все тройки чисел от \(1\) до \(N\) * Найти разницу между максимумом и минимумом в массиве * Найти число единиц в бинарной записи числа \(N\)
Сортировка слиянием* (для тех, кто всё успевает)
Возникает вопрос: а бывают ли сортировки, которые быстрее, чем квадратиные, и работают всегда?
Ответ — да. Есть несколько известных сортировок, работающих за \(O(N \log)\) , и доказано, что асимптотически быстрее сортировок не бывает.
Давайте подробнее рассмотрим сортировку слиянием, она же MergeSort.
Ссылка на красивую визуализацию: https://visualgo.net/nl/sorting (вкладка MER)
Для начала определим функцию слияния ( merge ) двух отсортированных массивов — она возвращает отсортированный массив, состоящий из элементов обоих массивов, и работает при этом за \(O(N)\) (где \(N\) — общее число элементов).
def merge(a, b): # надо придумать, что написать здесь merge([1, 3, 7, 10, 100], [2, 7, 7, 7, 11, 13, 18])[1, 2, 3, 7, 7, 7, 7, 10, 11, 13, 18, 100]В сущности слить два массива просто — это делается с помощью двух указателей \(i\) и \(j\) . Изначально они равны \(0\) (то есть указывают на нулевые элементы массивов \(a\) и \(b\) ). После этого достаточно смотреть на элементы \(a[i]\) и \(b[j]\) и минимальный из них класть в результирующий массив, после чего соответствующий указатель надо двигать дальше. Дальше нужно повторять этот процесс заново, пока мы не дошли до конца обоих массивов.
Когда функция merge уже написана, сам merge_sort писать уже легко — надо воспользоваться рекурсией. Чтобы отсортировать массив, достаточно отдельно отсортировать его левую и правую половины рекурсивно, и после этого эти половины слить.
Для удобства написания кода фунции можно сделать вот такими:
def merge(array, a, b, c): # функция сливает элементы массива array [a, b) и [b, c) # надо придумать, что написать здесь arr = [1, 1, 7, 10, 100, 2, 7, 40, 78, 6, 13, 100] merge(arr, 6, 9, 12) print(arr) merge(arr, 0, 6, 12) print(arr)[1, 1, 7, 10, 100, 2, 6, 7, 13, 40, 78, 100] [1, 1, 2, 6, 7, 7, 10, 13, 40, 78, 100, 100]def mergesort(array, a, c): # функция сортирует элементы массива array [a, c) # надо придумать, что написать здесь arr = [1, 1, 7, 10, 100, 2, 7, 40, 78, 6, 13, 100] mergesort(arr, 6, 12) print(arr) arr = [1, 1, 7, 10, 100, 2, 7, 40, 78, 6, 13, 100] mergesort(arr, 0, 12) print(arr)Задание
Разобраться, реализовать сортировку слиянием и сдать последнюю задачу в этом контесте:
Чтобы сдать это задание, нужно писать красивый код — будет проведено ревью.
Применение сортировки для решения задач
Также сортировка очень часто применяется как часть решения олимпиадных задач. В таких случаях обычно используют встроенную сортировку sort. Она на разных языках может быть реализована по-разному, но везде она работает за \(O(N log N)\) , и, обычно, неплохо оптимизирована.
# На питоне она пишется так a = [1, 5, 10, 5, -4] a.sort() print(a)[-4, 1, 5, 5, 10]// на C++11 она пишется так #include #include #include using namespace std; int main() < vectorv = ; sort(v.begin(), v.end()); for (auto x : v) < cout >Задание
Решить как можно больше задач из этого контеста:
В этом контесте можно и нужно использовать встроенную сортировку sort.
Квадратичные алгоритмы сортировки
Под квадратичными алгоритмами сортировки понимаются такие алгоритмы, временная сложность которых выражается как O(n 2 ). Т.е. если нам на вход дан массив длинной 10, то мы выполним 100 операций для того, чтобы его отсортировать.
Во всех нижеприведенных переменных нет выражения return , т.к. функции сортируют переданные им массивы «на месте». И в случае, когда return не указан, то функция вернет None .
Сортировка вставками (insertion sort)
Джуну прилетела важная задача по сортировке массива, но он, к сожалению, не знает про встроенные методы сортировки в Питоне и знаком только с тем, как можно сортировать вставками.
Итак, задача следующая. Нужно написать функцию, которая на вход принимает неупорядоченный массив чисел и возвращает его в отсортированном состояниии от наименьшего к наибольшему.
numbers = [5, 6, 1, 100, 12, 44, 55, 23, 33, 11, 99, 12, 66] def insertion_sort(numbers): numbers_length = len(numbers) for i in range(1, numbers_length): k = i while k > 0 and numbers[k-1] > numbers[k]: numbers[k], numbers[k-1] = numbers[k-1], numbers[k] k -= 1 insertion_sort(numbers) print(f'result: ') # result: [1, 5, 6, 11, 12, 12, 23, 33, 44, 55, 66, 99, 100]Джун прекрасно справился со своей задачей и написал сортировку вставками, а мы можем более подробно рассмотреть код.
Внутри функции insertion_sort() первым делом объявляется переменная numbers_length , которая содержит в себе длину массива. Далее в цикле for от первого элемента до последнего включительно мы начинаем выполнять манипуляции по перестановке чисел.
Переменная k хранит индекс элемента, который мы собераемся передвинуть на другую позицию, в случае если он больше предыдущего. После объявления переменной k мы создаем цикл while с условием «пока k больше нуля и предыдущий элемент массива больше текущего».
И в блоке инструкций уже описываем, что мы хотим сделать — а хотим мы поменять текущий элемент с предыдущим, а затем уменьшить значение k на единицу.
По сути алгоритм сравнивает попарно элементы, которые стоят рядом и затем их меняет местами. Например, если бы у нас был массив [5, 4, 3, 2, 1] , то на последней итерации цикла for мы бы протащили единицу с последней позиции на нулевую попутно сравнивая с каждый предыдущим элементом.
Для массива [5, 4, 3, 2, 1] это выглядело бы так:
- На первой итерации цикла for сравнимаем 4 и 5 — 4 меньше 5, поэтому меняем их местами и получаем массив [4, 5, 3, 2, 1] .
- На второй итерации сравниваем 3 с предыдущими элементами, пока 3 не встанет на нулевую позицию. Когда условия цикла while станут ложными у нас будет массив [3, 4, 5, 2, 1] .
- На третьей итерации сравниваем 2 с предыдущими элементами и получаем массив [2, 3, 4, 5, 1] .
- И на последней итерации мы «тащим» единицу на самую первую позицию поочередно меняя её с предыдущими элементами и получаем отсортированный массив [1, 2, 3, 4, 5] .
Сортировка методом выбора (selection sort | choise sort)
Функция сортировки выбором выглядит следующим образом:
numbers = [5, 4, 3, 2, 1] numbers_length = len(numbers) def selection_sort(numbers): for i in range(numbers_length-1): for k in range(i+1, len(numbers)): if numbers[k] < numbers[i]: numbers[k], numbers[i] = numbers[i], numbers[k] selection_sort(numbers) print(f'result: ') # result: [1, 2, 3, 4, 5]В данной сортировке мы идем по порядку от начала до предпоследнего элемента и сравниваем с «впередистоящими» элементами. Первая итерация внешнего цикла for для массива [5, 4, 3, 2, 1] выглядит так:
- Берем элемент с индексом 0 и сравниваем его с элементом под индексом 1 — 4 < 5, поэтому меняем их местами и получаем массив [4, 5, 3, 2, 1].
- На нулевом индексе у нас теперь стоит число 4, сравниваем с элементом под индексом 2 — 3 > 4, поэтому меняем местами. Получаем массив [3, 5, 4, 2, 1].
- Теперь сравниваем число 3 с элементом под индексом 3. Два меньше трех, поэтому меняем их местами. Получаем массив [2, 5, 4, 3, 1] .
- Тут можно догадаться, что будет дальше �� Снова сравниваем число под индексом 0 с индексом k+1 . На этот раз k равен 4, где у нас стоит число 1. Единица отправляется на нулевую позицию, а двойка отправляется в конец. Получаем массив [1, 5, 4, 3, 2] .
На следующей итерации внешний цикл for перейдет к следующему элементу и мы во внутреннем цикле снова пройдемся по всему массиву, чтобы поставить двойку на первую позицию. И так до самого последнего элемента.
Сортировка пузырьком (bubble sort)
numbers = [5, 4, 3, 2, 1] numbers_length = len(numbers) def bubble_sort(numbers): for i in range(1, numbers_length): for k in range(numbers_length-i): if numbers[k] > numbers[k+1]: numbers[k], numbers[k+1] = numbers[k+1], numbers[k] print(f'result: ') # result: [1, 2, 3, 4, 5]Сортировка пузырьком чем-то похожа и на сортировку вставками и на сортировку выбором.
Здесь мы на каждой итерации «толкаем» наибольший элемент вперед, пока он не встанет на своё место.
Но стоит отметить, что с каждой итерацией внешнего цикла диапазон для проверки во внутреннем цикле сужается, т.к. мы от длины массива вычитаем значение i .
В этом есть смысл, т.к. на первой итерации мы находим самое большое число и поочередно переставляем его в самый конец.
Квадратичные алгоритмы сортировки
На практике сортировка «пузырьком» почти не используется. Причина проста: есть существенно более эффективные алгоритмы сортировки с той же асимптотической сложностью и примерно такой же сложностью реализации.
Ниже мы рассмотрим две альтернативы пузырьку. Обе эти альтернативы разбивают массив на две части: до некоторого элемента (до — по номеру) массив отсортирован, после него — ещё нет. Шаг этих алгоритмов удлиняет отсортированный кусок на 1 элемент.
То есть устроены они так (в предположении, что переменная array связана с сортируемым массивом):
N = len(array) for sorted_length in range(N): ## здесь происходят перестановки элементов, приводящие к ## увеличению длины упорядоченного куска на 1 Сортировка поиском минимума
Для удлинения упорядоченной части на 1 мы ищем наименьший элемент неупорядоченной части и меняем его местами с начальным элементом неупорядоченной части:
N = len(array) for sorted_length in range(N): _, min_index = min([(x, i + sorted_length) for i,x in enumerate(array[sorted_length:])]) array[min_index], array[sorted_length] = ( array[sorted_length], array[min_index] ) Асимптотическую сложность этого алгоритма нетрудно вычислить. Поиск минимального элемента (перебором) на каждом шагу алгоритма занимает не более \(N\) операций вида «посмотреть на элемент и что-нибудь запомнить», но и не менее \(N-sorted_length\) (в том случае, когда минимальный элемент — последний, на который мы посмотрели в процессе перебора).
Поэтому время работы алгоритма \(T(N)\) удовлетворяет неравенствам
\[ N\cdot N \geqslant T(n) \geqslant N + (N-1) + (N-2) + \ldots + 1 = \frac \]
Осталось заметить, что \(N(N+1)/2 \geqslant \frac N^2\). Поэтому рассматриваемый нами алгоритм относится к классу квадратичных (т.е. асимптотической сложности \(N^2\)).
Сортировка вставками
Для удлинения упорядоченной части на 1 мы берём первый элемент неупорядоченной части и обменами с левым соседом ставим в то место упорядоченной части, где он должен в итоге оказаться:
N = len(array) for sorted_length in range(N): for k in range(sorted_length): i = sorted_length - k if array[i] < array[i-1]: array[i], array[i-1] = array[i-1], array[i] else: break Единственной сложностью реализации этого алгоритма является обеспечения корректности индекса i внутреннего цикла. Он должен быть в пределах от \(1\) (для того, чтобы было определено array[i-1] ) до \(N-1\) (для того, чтобы было определено array[i] ).
Поскольку k не превышает sorted_length-1 , то sorted_length-k не меньше
sorted_length - (sorted_length - 1) = 1 Также, поскольку k не меньше нуля, а sorted_length не превышает \(N-1\), то sorted_length - k тоже не превышает \(N-1\).
Асимптотическая сложность этого алгоритма ровно такая же, как и у сортировки поиском минимума: квадратичная. Доказательство в точности такое же.
Постскриптум
Среди трёх рассмотренных нами квадратичных алгоритмов (пузырёк, поиск минимума, вставки) на практике обычно можно встретить только вставки: имея одинаковую асимптотическую сложность, эти три алгоритма различаются по реальному времени работы (напомним, что асимптотическая сложность вообще не берёт в расчёт постоянные множители).
Может возникнуть естественный вопрос: «зачем вообще использовать квадратичный алгоритм сортировки, если есть алгоритмы с более низкой асимптотической сложностью?». Ответ весьма простой (хотя и состоит из двух частей):
- теория асимптотической сложности исследует лишь время работы алгоритма при достаточно большом \(N\)
- чем больше \(\alpha\), тем при большем количестве натуральных значений \(N\) выполнено неравенство \(\alpha N \log_2 N > N^2\)
Следствием любого из этих утверждений является то, что квадратичный алгоритм при достаточно маленьком \(N\) может работать быстрее линейно-логарифмического.
Считается (как результат большого количества экспериментов), что для массивов размером не более нескольких десятков элементов наиболее эффективный способ их отсортировать — применить сортировку вставками.