Пирамидальная сортировка, сортировка слиянием и выпуклая оболочка

Автор оригинала: James Le
  • Перевод

Базовые алгоритмы сортировки


Пирамидальная сортировка (или сортировка кучей, 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. Или подписывайтесь на мою рассылку, чтобы получать мои последние статьи прямо на ваш почтовый ящик!


Перевод статьи подготовлен в преддверии старта курса «Алгоритмы и структуры данных».

Приглашаем также посетить бесплатный демо-урок на тему «Пирамидальная сортировка». На этом бесплатном демо-занятии мы:— сначала реализуем алгоритм сортировки выбором, — потом превратим массив в пирамиду (кучу) и — ускорим время поиск максимального элемента в неотсортированной части массива с линейного до логарифмического.В итоге у нас получится алгоритм Пирамидальной сортировки. Мы наглядно продемонстрируем работу алгоритма на визуальных примерах с конкретными числами.

OTUS
Цифровые навыки от ведущих экспертов

Комментарии 6

    +1

    Что это за поток мыслей? Почему два алгоритма сортировки описаны рядом с алгоритмом вычисления выпуклой оболочки? Как они связаны?


    Зачем впилены номера строк с тире в псевдокоде? К ним нету никаких отсылок. Псевдокод на русском — та еще жесть, особенно на фоне других кусков псевдокода.


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

    Это вообще как? Как можно не полностью отсортировать heap? Ну и чтобы при этом всем она еще и правильно построена была.

      0
      Как можно не полностью отсортировать heap?

      Странный вопрос. Вообще-то он по определению не полностью отсортированный. У хипа только одна задача — наверху должен быть "самый-самый" элемент.

        0

        Насколько я помню, это не совсем так — главная особенность хипа — что любой родительский нод будет больше|меньше (соотв. для max-heap|min-heap) (или равен) любого из его детей.


        Википедия:


        In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete[1] tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C.

        Так что, да, наверху любого из нодов должен быть "самый-самый" элемент.

          –1

          Пирамидальная сортировка упорядочена максимумом вперёд не просто так.
          (Понятно, что всегда же можно проинвертировать порядок).


          Дело в том, что это нужно исключительно для сортировки пирамидой, размещённой на массиве, вершиной вперёд!


          Первый шаг — make_heap
          В цикле:


          • предусловие: [0..k) — это уже пирамида, [k..n) — ещё не обработанный хвост массива
          • действие: берём элемент [k] и помещаем в пирамиду, которая прирастает на освободившееся место
          • постусловие: [0..k+1) — пирамида, [k+1..n) — хвост

          Второй шаг — sort_heap — и вот тут всё становится важным!


          • предусловие: [0..k) — пирамида, [k..n) — уже упорядоченный хвост из максимумов
          • действие: берём [0] — это очередной максимум (меньший хвоста, разумеется), удаляем его из пирамиды, освобождая [k], куда и кладём взятый элемент
          • постусловие: [0..k-1) — пирамида, [k-1..n) — упорядоченный хвост

          Если разместить пирамиду на массиве в обратном направлении, тогда там удобно будет хранить минимумом к вершине.


          Ну а если мы делаем пирамидальную сортировку не на массиве по месту, а на списке и дереве, то, в зависимости от левого или правого фолда, пирамида должна держать минимум или максимум на вершине.

        +1

        Очень странная солянка из алгоритмов. Без этого статья слишкмо короткая получалась?

          –1

          Дожили, датасаентисты играют в псевдобейсик.
          Циферки ещё бы канонично расставили, с шагом 10.


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


          Зачем изучать именно эту подборку алгоритмов?
          Зачем именно в таком виде?


          Зачем вам, компании ОТУС, понадобилось иллюстрировать ваш курс переводом какой-то стрёмной статьи?




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


          Например, потребление памяти алгоритмами сортировки:


          • линейное (mergesort — выделяем промежуточные массивы)
          • логарифмическое (quicksort — стек рекурсии)
          • константное (heapsort, insertions, bubble)

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

          Самое читаемое