Сортировки и связанные с ними задачи.

  Д.Кнут. Искусство программирования для ЭВМ. тт 1-3. Москва. Мир. 1996-1998 Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999. Препарата Ф., Шеймос М. Вычислительная геометрия. Москва. Мир. 1989  

К вопросу о понимании предыдущих лекций. Найти ошибку. ``Доказательство'' того, что любое натуральное число можно однозначно описать не более, чем 20-тью словами (имеется в виду, можно использовать только существующие в языке слова, а не что-нибудь вроде "ШестьсотШестьдесятШесть"). Пусть это не так. Тогда существует множество, являющееся подмножеством натуральных чисел, каждый элемент которого невозможно назвать, использовав менее, чем 20 слов. У всякого подмножества натуральных чисел есть наименьший элемент.Получаем: "Наименьшее натуральное число, которое нельзя назвать менее, чем двадцатью словами, имеющимися в русском языке" - итого 13 слов потребовалось, дабы назвать данное число, которое принадлежит этому великолепному множеству => противоречие.

HeapSort или сортировка с помощью пирамиды.

Алгоритм основан на промежуточном упорядочивании массива входных данных {A₁ ,…, A_N }. Мы докажем, что промежуточно-упорядоченный массив (мы будем его называть пирамидально-упорядоченным) обладает свойством максимальности своего первого элемента. Тогда мы отрезаем от массива первый элемент и восстанавливаем утраченное свойство пирамидально-упорядоченности у оставшегося куска. Так, отрезая по одному (максимальному из оставшихся) элементу, мы можем `набрать’ полный упорядоченный массив.

Определение. Массив { A₁ ,…, A_N } называется пирамидально-упорядоченным, если для всех допустимых i: A_[i/2] ³ A_i.

Иначе данное соотношение можно выписать следующим образом:

A_i ³ A_2i и A_i ³ A_2i+1 (*)

Легко видеть, что данные соотношения задают древообразную структуру, в вершине которой находится первый элемент дерева. Его потомками являются элементы с номерами 2 и 3, и т.д. В получившемся дереве все слои заполнены, кроме, быть может, последнего. Поэтому глубина дерева равна [log N]+1, где N – количество элементов в множестве.

Пусть для некоторого поддерева пирамиды, начинающегося с элемента с индексом i и заканчивающегося элементом с индексом N, выполнено свойство (*) для всех элементов поддерева, кроме вершины поддерева. Т.е. свойство выполняется для всех элементов, имеющих индексы больше i (здесь имеется в виду возможное невыполнения условий A_k ³ A_2k и A_k ³ A_2k+1 для k=i и его выполнение при k>i).

Определим процедуру Heapify(A,i,N), которая в данном случае подправляет элементы поддерева до полной пирамидально-упорядоченности элементов с индексами от i до N. Здесь A – рассматриваемый массив, i – индекс массива с которого начинается рассматриваемое поддерево, N – количество элементов во всем дереве.

Процедура Heapify(A,i,N) осуществляет следующие действия. Она проверяет условия

A_i ³ A_2i в случае 2i£N

A_i ³ A_2i+1 в случае 2i+1£N.

Если они выполняются (случаи 2i³N, 2i+1³N легко рассмотреть отдельно), то дальше ничего делать не надо, происходит выход из процедуры. Иначе, выбирается максимальный из элементов A_i, A_2i, A_2i+1 и выбранный элемент меняется местами с A_i. Не ограничивая общности рассуждений, допустим, что максимальным оказался элемент A_2i, тогда после перестановки имеем A_i ³ A_2i+1 , при этом элемент A_2i+1 не изменился, поэтому свойство пирамидально-упорядоченности будет выполняться и дальше в данном (правом) поддереве. Далее рекурсивно вызываем процедуру Heapify(A,2i,N).

Исходя из построения процедуры Heapify, имеем следующее утверждение

Утверждение 1. Процедура Heapify(A,i,N) выполняется за время O(h(i,N)), где h(i,N) – глубина поддерева в пирамиде из N элементов, начинающегося с элемента с индексом i.

Алгоритм Heapsort(A,N) выглядит следующим образом

---

Дата добавления: 2015-10-30