Основные алгоритмы сортировки
Сортировка по куче
Куча на самом деле представляет собой не что иное, как двоичное дерево с некоторыми дополнительными правилами, которым оно должно следовать: во-первых, оно всегда должно иметь структуру кучи, в которую заполняются все уровни двоичного дерева, начиная с слева направо, и во-вторых, он должен быть заказан как максимальная куча или минимальная куча. В качестве примера я буду использовать минимальную кучу.
Алгоритм сортировки кучи - это метод сортировки, который опирается на двоичные структуры данных кучи. Поскольку мы знаем, что кучи всегда должны следовать определенному порядку, мы можем использовать это свойство и использовать его для поиска наименьшего элемента с минимальным значением и последовательной сортировки элементов, выбирая корневой узел кучи и добавляя его в конец множество.
Вот псевдокод сортировки кучи:
HeapSort(A[1…n]): 1 - H = buildHeap(A[1…n]) 2 - for i = 1 to n do: 3 - A[i] = extract-min(H)
Для начала у нас есть несортированный массив. Первый шаг - взять этот массив и превратить его в кучу; в нашем случае мы хотим превратить его в минимальную кучу. Итак, нам нужно преобразовать и построить минимальную кучу из наших несортированных данных массива. Обычно это инкапсулируется одной функцией, которую можно назвать как-то вроде buildHeap.
Вот псевдокод buildHeap:
buildHeap(): 1 - initially H is empty 2 - for i = 1 to n do: 3 - Add(H, A[i])
Когда у нас есть данные нашего массива в формате минимальной кучи, мы можем быть уверены, что наименьшее значение находится в корневом узле кучи. Помните, что даже если вся куча не будет отсортирована, если мы построили нашу минимальную кучу правильно и без каких-либо ошибок, каждый отдельный родительский узел в нашей куче будет меньше по значению, чем его дочерние элементы. Итак, мы переместим наименьшее значение, расположенное в корневом узле, в конец кучи, заменив его последним элементом.
Теперь самый маленький элемент в куче находится на последнем узле, и это здорово. Мы знаем, что он находится в отсортированном положении, поэтому его можно полностью удалить из кучи. Но есть еще один шаг: убедиться, что новый элемент корневого узла находится в правильном месте! Маловероятно, что элемент, который мы поменяли местами в положение корневого узла, находится в правильном месте, поэтому мы переместим элемент корневого узла вниз в его правильное место, используя функцию, которая обычно называется чем-то вроде heapify .
Вот псевдокод extract-min и heapify:
extract-min(H): 1 - min = H[1] 2 - H[1] = H[H.size()] 3 - decrease H.size() by 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 - swap entries H[i] and H[j] 8 - i = j
Вот и все! Алгоритм продолжает повторять эти шаги до тех пор, пока куча не опустится до одного единственного узла. В этот момент он знает, что все элементы в несортированном массиве находятся в своих отсортированных позициях и что последний оставшийся узел в конечном итоге станет первым элементом в отсортированном массиве. Общее время работы этого алгоритма составляет O (n log n).
Сортировка слиянием
Алгоритм сортировки слиянием - это алгоритм сортировки, который сортирует коллекцию, разбивая ее пополам. Затем он сортирует эти две половины, а затем объединяет их вместе, чтобы сформировать одну полностью отсортированную коллекцию. В большинстве реализаций сортировки слиянием все это делается с помощью рекурсии.
Сортировка слиянием - это алгоритм «разделяй и властвуй», который можно свести к 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).
Выпуклая оболочка
Дан набор точек на плоскости. выпуклая оболочка множества - это наименьший выпуклый многоугольник, содержащий все его точки.
Подход 1 - подарочная упаковка O (n²)
Идея проста: мы начинаем с самой левой точки (или точки с минимальным значением координаты x) и продолжаем переносить точки в направлении против часовой стрелки. Если точка p является текущей точкой, следующая точка выбирается как точка, которая превосходит все другие точки при ориентации против часовой стрелки. Ниже приводится псевдокод:
1 - ConvexHull = Empty list 2 - Find point of smallest x and let it be u (:= u_original) 3 - Let L be the vertical line going through u 3 - Do: 4 - Let v be the point with the smallest angle between L and u * v 5 - Add v to ConvexHull 6 - Let L = uv line 7 - u := v 8 - Until v = u_original 9 - Output ConvexHull
Подход 2 - сканирование Грэма O (n log n)
Этот алгоритм можно разделить на 2 этапа:
- Этап 1 (точки сортировки): сначала мы находим самую нижнюю точку. Идея состоит в том, чтобы предварительно обработать точки, отсортируя их по самой нижней точке. После сортировки точек они образуют простой замкнутый путь. Какими должны быть критерии сортировки? Вычисление фактических углов было бы неэффективным, поскольку тригонометрические функции не просто вычислить. Идея состоит в том, чтобы использовать ориентацию для сравнения углов без их фактического вычисления.
- Этап 2 (точки принятия или отклонения). Когда у нас есть замкнутый путь, следующим шагом будет пересечение пути и удаление вогнутых точек на этом пути. Первые две точки в отсортированном массиве всегда являются частью выпуклой оболочки. Для остальных точек мы отслеживаем последние три точки и находим угол, образованный ими. Пусть это три точки: prev (p), curr (c) и next (n). Если ориентация этих точек (рассматривая их в том же порядке) не против часовой стрелки, мы отбрасываем c, в противном случае оставляем его.
1 - ConvexHull = Empty list 2 - Let u be the point with smallest x (if more such points, choose the one with smallest y) 3 - Sort the remaining points by by polor angle in counterclockwise order around u 4 - Add u and point 1 to ConvexHull 5 - For i = 2 to n - 1: 6 - While angle of the 2nd-to-last point, last point and i > 180 degree: 7 - Remove last point from ConvexHull 8 - Add i to ConvexHull 9 - Return ConvexHull
— —
Если вы хотите следить за моей работой по информатике и машинному обучению, вы можете проверить мои Medium и GitHub, а также другие проекты на https: // jameskle .com / . Вы также можете написать мне в Твиттере, написать мне по электронной почте или найти меня в LinkedIn. Или присоединяйтесь к моей рассылке, чтобы получать мои последние мысли прямо на ваш почтовый ящик!
