Базовые алгоритмы сортировки
Пирамидальная сортировка (или сортировка кучей, Heap Sort)
Куча (heap) — это не что иное, как двоичное дерево с некоторыми дополнительными правилами, которым оно должно следовать: во-первых, оно всегда должно иметь структуру кучи, где все уровни двоичного дерева заполняются слева направо, и, во-вторых, оно должно быть упорядочено в виде max-кучи или min-кучи. В качестве примера я буду использовать min-кучу.
Алгоритм пирамидальной сортировки — это метод сортировки, который полагается на такие структуры данных как двоичные кучи. Поскольку мы знаем, что кучи всегда должны соответствовать определенным требованиям, мы можем использовать это для поиска элемента с наименьшим значением, последовательно сортируя элементы, выбирая корневой узел кучи и добавляя его в конец массива.
Ниже приведен псевдокод пирамидальной сортировки:
HeapSort(A[1…n]):
1 - H = buildHeap(A[1…n])
2 - for i = 1 to n do:
3 - A[i] = extract-min(H)В самом начале мы имеем несортированный массив. Первый шаг — взять этот массив и превратить его в кучу; в нашем случае мы хотим превратить его в min-кучу. Итак, нам нужно преобразовать данные несортированного массива и построить из них min-кучу. Обычно это инкапсулируется одной функцией, которую можно назвать, например, buildHeap.
Ниже приведен псевдокод buildHeap:
buildHeap():
1 - Изначально H пустая
2 - for i = 1 to n do:
3 - Add(H, A[i])Как только данные нашего массива будут представлены в формате min-кучи, мы можем быть уверенными, что наименьшее значение находится в корневом узле нашей кучи. Помните, что даже если куча не будет полностью отсортирована, если мы построили нашу min-кучу правильно и без каких-либо ошибок, каждый отдельно взятый родительский узел в нашей куче будет меньше по значению, чем его дочерние элементы. Мы собираемся переместить наименьшее значение, расположенное в корневом узле, в конец кучи, заменив его последним элементом.
Теперь самый маленький элемент в куче находится в последнем узле, что нам и нужно. Мы знаем, что он находится в отсортирован относительно остальных элементов, поэтому его можно полностью удалить из кучи (функция extract-min). Но нам нужно сделать еще кое-что: убедиться, что новый элемент корневого узла находится на своем месте! Маловероятно, что элемент, который мы сделали корневым узлом, находится на своем месте, поэтому мы переместим элемент корневого узла вниз в его корректное положение, используя функцию, которая обычно называется heapify (приведение к виду кучи).
Ниже приведен псевдокод extract-min и heapify:
extract-min(H):
1 - min = H[1]
2 - H[1] = H[H.size()]
3 - уменьшаем H.size() на 1
4 - heapify(H, 1)
5 - return min
heapify():
1 - n = H.size()
2 - while (LeftChild(i) <= n and H[i] > H[LeftChild(i)]) or (RightChild(i) <= n and H[i] > H[RightChild(i)]) do:
3 - if (H[LeftChild(i)] < H[RightChild(i)]) then:
4 - j = LeftChild(i)
5 - else:
6 - j = RightChild(i)
7 - меняем местами H[i] и H[j]
8 - i = j
Вот и все! Алгоритм продолжает повторять эти шаги до тех пор, пока куча не сократится до одного единственного узла. На момент, когда это произойдет, мы будем уверенны, что все элементы в несортированном массиве находятся в своих отсортированных позициях и что последний оставшийся узел в конечном итоге станет первым элементом в отсортированном массиве. Общее время работы этого алгоритма составляет O(n log n).
Сортировка слиянием (Merge Sort)
Алгоритм сортировки слиянием — это алгоритм сортировки, который сортирует коллекцию, разбивая ее на половины. Затем он сортирует эти две половины и объединяет их вместе, чтобы сформировать одну полностью отсортированную коллекцию. В большинстве реализаций сортировки слиянием все это делается посредством рекурсии.
Сортировка слиянием — это алгоритм «разделяй и властвуй», который можно свести к 3 шагам:
Разделите (разбейте) задачу на минимально возможные «подзадачи» одного типа.
В первую очередь победите (решите) самые мелкие подзадачи. После того, как вы нашли рабочее решение, используйте ту же самую технику для решения более крупных подзадач — другими словами, решайте подзадачи рекурсивно.
Объединяйте результаты и соединяйте более мелкие подзадачи, пока вы, наконец, не примените то же решение к более крупной и сложной задаче, с которой вы начинали!
Суть алгоритмов «разделяй и властвуй» проистекает из того факта, что решить сложную проблему намного проще, если вы сможете понять, как разбить ее на более мелкие части. Если разбить проблему на отдельные части, решить ее станет намного проще. И обычно, когда вы выясняете, как решить «подзадачу», вы можете применить это решение к более крупной задаче. Именно эта методология делает рекурсию предпочтительным инструментом для алгоритмов «разделяй и властвуй», и именно по этой причине сортировка слиянием является отличным примером рекурсивных решений.
Функция mergeSort в свою очередь состоит из двух функций:
функции слияния, которая фактически объединяет два списка вместе и сортирует их в правильном порядке.
функции
mergeSort, которая будет продолжать разделять входной массив снова и снова (рекурсивно), а затем будет вызывать функцию слияния снова и снова (также рекурсивно).
Ниже приведен псевдокод сортировки слиянием:
Merge(A, B):
1 - i = 1; j = 1; k = 1;
2 - a_(m+1) = ∞; b_{n+1} = ∞
3 - while (k <= m+n) do:
4 - if (a_i < b_j) then
5 - c_k = a_i; i++;
6 - else
7 - c_k = b_j; j++;
8 - k++;
9 - return C = {c_1, c_2, …, c_(m+n)}
MergeSort(X, n)
1 - if (n == 1) return X
2 - middle = n/2 (round down)
3 - A = {x_1, x_2, …, x_middle}
4 - B = {x_(middle+1), x_{middle+2), …, x_n}
5 - As = MergeSort(A, middle)
6 - Bs = MergeSort(B, n - middle)
7 - return Merge(As, Bs)Именно потому, что сортировка слиянием реализована рекурсивно, это делает ее быстрее, чем другие алгоритмы, которые мы рассмотрели до сих пор. Сортировка слиянием имеет время выполнения O(n log n).
Выпуклая оболочка (или выпуклый контур, Convex Hull)
Нам дан набор точек на плоскости. Выпуклая оболочка множества — это наименьший выпуклый многоугольник, содержащий все его точки.
Подход 1 — Упаковка подарков (Gift Wrapping) O(n²)
Идея проста, мы начинаем с самой левой точки (или точки с минимальным значением координаты x) и продолжаем оборачивать точки против часовой стрелки. Если точка p является текущей точкой, следующая точка выбирается как точка, которая перекрывает все остальные точки по ориентации против часовой стрелки. Ниже приводится псевдокод:
1 - ConvexHull = пустой список
2 - Ищем точку с наименьшим x и присваиваем ее u (:= u_original)
3 - Пусть L будет вертикальной линией, проходящей через u
3 - Do:
4 - Пусть v будет точкой с наименьшим углом между L и u * v
5 - Добавляем v в ConvexHull
6 - Пусть L = uv линии
7 - u := v
8 - Until v = u_original
9 - Выводим ConvexHull
Подход 2 — Алгоритм Грэхема (Graham Scan) O(n log n)
Этот алгоритм можно разделить на 2 этапа:
Этап 1 (сортировка точек): сначала мы находим самую нижнюю точку. Идея состоит в том, чтобы предварительно обработать точки, сортируя их по самой нижней точке. После сортировки точек они образуют простой замкнутый путь. Какими должны быть критерии сортировки? Вычисление фактических углов было бы неэффективным, поскольку тригонометрические функции не являются простыми в вычислении. Идея состоит в том, чтобы использовать ориентацию для сравнения углов без их фактического вычисления.
Этап 2 (включении или отбрасывание точек): после того, как у нас есть замкнутый путь, следующим шагом будет прохождение по пути и удаление из него вогнутых точек. Первые две точки в отсортированном массиве всегда являются частью выпуклой оболочки. Для оставшихся точек мы смотрим на последние три точки и находим угол, образованный ими. Пусть это три точки: prev(p), curr(c) и next(n). Если ориентация этих точек (рассматривая их в том же порядке) не против часовой стрелки, мы отбрасываем c, в противном случае мы оставляем ее.
1 - ConvexHull = пустой список
2 - Пусть u - точка с наименьшим значением x (если таких точек несколько, выбираем ту, у которой наименьший y)
3 - Сортируем оставшиеся точки по угловой фазе в порядке против часовой стрелки вокруг u
4 - Добавляем u и первую точку в ConvexHull
5 - For i = 2 to n - 1:
6 - While угол между предпоследней, последней и точкой i > 180 градусов:
7 - Удаляем точку из ConvexHull
8 - Добавляем i в ConvexHull
9 - Return ConvexHull
— —
Если вам интересно следить за моей работой в области компьютерных наук и машинного обучения, вы можете посетить мои Medium и GitHub, а также другие проекты на https://jameskle.com/. Вы также можете написать мне мне в Твиттере, но электронной почте или найти меня в LinkedIn. Или подписывайтесь на мою рассылку, чтобы получать мои последние статьи прямо на ваш почтовый ящик!
Перевод статьи подготовлен в преддверии старта курса «Алгоритмы и структуры данных».
Приглашаем также посетить бесплатный демо-урок на тему «Пирамидальная сортировка». На этом бесплатном демо-занятии мы:— сначала реализуем алгоритм сортировки выбором, — потом превратим массив в пирамиду (кучу) и — ускорим время поиск максимального элемента в неотсортированной части массива с линейного до логарифмического.В итоге у нас получится алгоритм Пирамидальной сортировки. Мы наглядно продемонстрируем работу алгоритма на визуальных примерах с конкретными числами.
