4785

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

Лекция

Информатика, кибернетика и программирование

Быстрые алгоритмы сортировки и поиска. Нижняя оценка времени задачи сортировки массива по числу сравнений. Быстрые алгоритмы сортировки. Сортировка деревом Пирамидальная сортировка Быстрая сортировка Хоара. Поиск k-того в м...

Русский

2012-11-27

115.5 KB

56 чел.

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

1.Нижняя оценка времени задачи сортировки массива по числу сравнений.

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

 Сортировка деревом;

 Пирамидальная сортировка;

 Быстрая сортировка Хоара.

3.Поиск k-того в массиве. Поиск медианы массива.

4.Метод “разделяй и властвуй”.

5.Метод цифровой сортировки.

6.Задачи и упражнения

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

1.Нижняя оценка времени задачи сортировки массива по числу сравнений.

Теорема.  Любой алгоритм сортировки массива, использующий только сравнения и перестановки, в худшем случае требует минимум O(n log2 n) сравнений.

Доказательство. Пусть a1, a2, ..., an - подмножество элементов, выбранных из абстрактного множества U, на котором определено отношение линейного порядка. (Это означает, что любые два различных элемента a и b из U сравнимы: a < b или b < a.) Это подмножество порождает n! перестановок, и каждая перестановка может быть исходной последовательностью (входом) для применения алгоритма сортировки. Иными словами, задача сортировки размера n имеет n! различных входов. Обозначим это множество входов через Per(A). Например, при n = 3 подмножество {a, b, c} порождает 3! = 6 различных входов: [a b c], [a c b], [b a c], [b c a], [c a b], [c b a].

Алгоритм сортировки ввиду абстрактности множества U осуществляет перестановки, сортирующие вход B, исходя только из проверки условий, содержащих сравнения двух элементов A, прямо или косвенно выбранных из массива B по их индексам. Пусть S - некоторое подмножество из Per(A).

Условие, содержащее сравнение a[i] ? a[j], на одной части множества S даст результат - True, для другой - False. Пусть T(S), F(S) - эти подмножества. Тогда |S| = |T(S)| + |F(S)|.  Следовательно, количество элементов по крайней мере в одном из подмножеств T(S), F(S) не меньше |S|/2. Пусть С(1,B), С(2,B), ..., С(k, B) - последовательность значений условий, проверяемых алгоритмом последовательно на входе B длины k и СonSeq(k, B) - множество входов, которые генерируют ту же последовательность условий. Тогда

(СonSeq(k, B), B Per(A)) = Per(A)

и, следовательно, существует такой вход В, для которого

|СonSeq(k, B)| |Per(A)|/2k     (*)

Пусть B и B’ - два (различных) входа и P - некоторая перестановка. Легко показать, что из B B’ следует P(B) P(B’). Поэтому последовательности перестановок, сортирующих различные входы, будут различными. Но каждая последовательность перестановок однозначно определена соответствующей последовательностью условий. Следовательно, каждому входу B соответствует своя последовательность значений условий С(1,B), С(2,B), ..., С(m, B), проверяемая в процессе выполнения программы сортировки на этом входе. Таким образом,

СonSeq(m, B) = {B}.       (**)

Из (*), (**) следует существование такого входа B, для которого выполнено неравенство |Per(A)|/2m  1, т.е. n!/2m  1 или m log(n!). По формуле Стирлинга

log(n!) log2((n/e)n) = n(log2 n - 1) = O(n log2 n).

Мы показали, что для любого алгоритма сортировки с помощью сравнений и перестановок существует такой вход, на котором m >= O(n log2 n)

Таким образом, функция сложности в худшем случае алгоритма сортировки С(n) ограничена снизу величиной O(n log2 n). Конец доказательства.  

Вспомним, что алгоритм сортировки вставками имеет такую же по порядку величины функцию C(n). Таким образом, эта оценка достижима.

Вопрос об оценке функции количества перестановок M(n) остался открытым. Можно предполагать, что каждой перестановке предшествует некоторое сравнение. Тогда общее количество перестановок, осуществляемых алгоритмом, не превосходит C(n) и, следовательно, эффективные алгоритмы сортировки должны иметь сложность O(n log2 n) как по сравнениям, так и по перестановкам. Ниже мы рассмотрим некоторые такие алгоритмы.

2. Быстрые алгоритмы сортировки: Сортировка деревом.

Алгоритм сортировки деревом ТreeSort по существу является улучшением алгоритма сортировки выбором. Процедура выбора наименьшего элемента усовершенствована как процедура построения т.н. сортирующего дерева. Сортирующее дерево - это структура данных, в которой представлен процесс поиска наименьшего элемента методом попарного сравнения рядом стоящих элементов.  Алгоритм сортирует массив в два этапа.

I этап : построение сортирующего дерева;

II этап : просеивание элементов по сортирующему дереву.

Рассмотрим пример:

Пусть массив A состоит из 8 элементов (рис 1, 1-ая строка).  Вторая строка состоит из минимумов рядом стоящих элементов первой строки. Каждая следующая строка составлена из минимумов рядом стоящих элементов предыдущей.

рис 1

a2 = min(a1,a2)

a3 = min(a3,a4)

a5 = min(a5,a6)  

a8 = min(a7,a8)

a3 = min(a2,a3)

a5 = min(a5,a8)

a5 = min(a3,a5)

Эта структура данных называется сортирующим деревом. В корне сортирующего дерева расположен наименьший элемент. Кроме того, в дереве построены пути элементов массива от листьев до соответствующего величине элемента узла - ветвления. (На рис.1 путь минимального элемента a5 - от листа a5 к корню отмечен толстой линией.)

Когда дерево построено, начинается этап просеивания элементов массива по дереву. Минимальный элемент пересылается в выходной массив B и все вхождения этого элемента в дереве заменяются на специальный символ M.

рис 2

      B

       1      2    . . .    8

Затем осуществляется просеивание элемента вдоль пути, отмеченного символом M, начиная с листка, соседнего с M (На рис 2. сверху-вниз) и до корня. Шаг просеивания - это выбор наименьшего из двух элементов, встретившихся на пути к корню дерева и его пересылка в узел, отмеченный M. Просеивание 2-го элемента показано на рис 3. (Символ М больше, чем любой элемент массива.)

рис 3

a6 = min(M, a6)

a6 = min(a6, a8)

a3 = min(a3, a6)                                          B

b2 := a3

   1      2    . . .          8

Просеивание элементов происходит до тех пор, пока весь исходный массив не будет заполнен символами M, т.е n раз:

For I := 1 to n do begin

  Отметить путь от корня к листку символом M;

  Просеять элемент вдоль отмеченного пути;

  B[I] := корень дерева

end;

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

Сортирующее дерево можно реализовать, используя либо двумерный массив, либо одномерный массиве ST[1..N], где N = 2n-1 (см. следующий раздел). Оценим сложность алгоритма в терминах M(n), C(n). Прежде всего отметим, что алгоритм TreeSort работает одинаково на всех входах, так что его сложность в худшем случае совпадает со сложностью в среднем.

Предположим, что n - степень 2 (n = 2l). Тогда сортирующее дерево имеет l + 1 уровень (глубину l). Построение уровня I требует n / 2I сравнений и пересылок. Таким образом, I-ый этап имеет сложность

C1(n) = n/2 + n/4 + ... + 2 + 1 = n - 1,   M1(n) = C1(n) = n - 1

Для того, чтобы оценить сложность II-го этапа С2(n) и M2(n) заметим, что каждый путь просеивания имеет длину l, поэтому количество сравнений и пересылок при просеивании одного элемента пропорционально l. Таким образом, M2(n) = O(l n), C2(n) = O(l n).

Поскольку l = log2n, M2(n)=O(n log2 n)), C2(n)=O(n log2 n), Но С(n) = C1(n) + C2(n), M(n) = M1(n) + M2(n). Так как C1(n) < C2(n), M1(n) < M2(n), окончательно получаем оценки сложности алгоритма TreeSort по времени:

M(n) = O(n log2 n),  C(n) = O(n log2 n),

В общем случае, когда n не является степенью 2, сортирующее дерево строится несколько иначе. “Лишний” элемент (элемент, для которого нет пары) переносится на следующий уровень. Легко видеть, что при этом глубина сортирующего дерева равна [log2 n] + 1. Усовершенствование алгоритма II этапа очевидно. Оценки при этом меняют лишь мультипликативные множители.  Алгоритм TreeSort обладает существенным недостатком: для него требуется дополнительная память размера 2n - 1.

Пирамидальная сортировка.

Алгоритм пирамидальной сортировки HeapSort также использует представление массива в виде дерева. Этот алгоритм не требует вспомогательных массивов, сортируя “на месте”. Рассмотрим сначала метод представления массива в виде дерева:

Пусть A[1 .. n] - некоторый массив. Сопоставим ему дерево, используя следующие правила:

     левый сын       правый сын             рис 4

1.A[1] - корень дерева ;

2.Если A[i] - узел дерева и 2i n,

      то A[2*i] - узел - “левый сын” узла A[i]

3.Если A[i] - узел дерева и 2i + 1 n,

      то A[2*i+1] - узел - “правый сын” узла A[i]      отец 

          

Правила 1 - 3 определяют в массиве структуру дерева, причем глубина дерева не превосходит [log2 n] + 1. Они же задают способ движения по дереву от корня к листьям. Движение вверх задается правилом 4:

4.Если A[i] - узел дерева и i > 1

      то A[i mod 2] - узел - “отец” узла A[i];

Пример1. Пусть A = [45 13 24 31 11 28 49 40 19 27] - массив. Соответствующее ему дерево имеет вид:

рис 5

Обратите внимание на то, что все уровни дерева, за исключением последнего, полностью заполнены, последний уровень заполнен слева и индексация элементов массива осуществляется сверху-вниз и слева-направо. Поэтому дерево упорядоченного массива удовлетворяет следующим свойствам:  A[i] A[2*i],  A[i] A[2*i+1],  A[2*i] A[2*i+1].

Как это ни удивительно, алгоритм HeapSort сначала строит дерево, удовлетворяющее прямо противоположным соотношениям

  A[i] A[2*i], A[i] A[2*i+1]                           (6)

а затем меняет местами A[1] (наибольший элемент) и A[n].

Как и TreeSort, алгоритм HeapSort работает в два этапа:

I.Построение сортирующего дерева;

II.Просеивание элементов по сортирующему дереву.

Дерево, представляющее массив, называется сортирующим, если выполняются условия (6). Если для некоторого i это условие не выполняется, будем говорить, что имеет место (семейный) конфликт в треугольнике i (рис 4).

И на I-ом, и на II-ом этапах элементарное действие алгоритма заключается в решении семейного конфликта: если наибольший из сыновей больше, чем отец, то переставляются отец и этот сын (процедура ConSwap).

В результате перестановки может возникнуть новый конфликт в том треугольнике, куда переставлен отец. Таким образом можно говорить о конфликте (рода) в поддереве с корнем в вершине i. Конфликт рода решается последовательным решением семейных конфликтов проходом по дереву сверху-вниз. (На рис 5 путь решения конфликта рода в вершине 2 отмечен.) Конфликт рода решен, если проход закончился (i > n div 2) или в результате перестановки не возник новый семейный конфликт.  (процедура Conflict)

Procedure ConSwap(i, j : Integer);

    Var b : Real;

    Begin

     If a[i] < a[j] then begin

       b := a[i]; a[i] := a[j]; a[j] := b

     end

    End;

Procedure Conflict(i, k : Integer);

      Var j : Integer;

    Begin

      j := 2*i;

      If j = k

       then ConSwap(i, j)

       else if j < k then begin

          if a[j+1] > a[j] then j := j + 1;

           ConSwap(i, j); Conflict(j, k)

        end

      End;

I этап - построение сортирующего дерева - оформим в виде рекурсивной процедуры, используя определение:

Если левое и правое поддеревья T(2i) и T(2i+1) дерева T(i) сортирующие, то для перестройки T(i) необходимо разрешить конфликт рода в этом дереве.

Procedure SortTree(i : Integer);

     begin

      If i <= n div 2 then begin

        SortTree(2*i);

        SortTree(2*i+1);

         Conflict(i, n)

       end

     end;

На II-ом этапе - этапе просеивания - для k от n до 2 повторяются следующие действия:

1.Переставить A[1] и A[k];

2.Построить сортирующее дерево начального отрезка массива A[1..k-1], устранив конфликт рода в корне A[1].  Заметим, что 2-ое действие требует введения в процедуру Conflict параметра k.

Program HeapSort;

  Const n = 100;

     Var A : Array[1..n] of real;

          k : Integer;

       {процедуры ConSwap, Conflict, SortTree, ввода, вывода}

       Begin

         { ввод }

         SortTree(1);

         For k := n downto 2 do begin

          ConSwap(k, 1); Conflict(1, k - 1)

         end;

        { вывод }

       End.

Оценим сложность алгоритма в терминах C(n), M(n). Поскольку каждая  перестановка  связана со сравнением в процедуре ConSwap, M(n) C(n). Далее, в процедуре Conflict сравнение предшествует вызову ConSwap, поэтому общее число сравнений не превосходит удвоенного числа вызовов ConSwap. Следовательно, С(n) можно получить, оценив количество обращений к ConSwap.

Сложность I-го этапа C1(n) удовлетворяет соотношению C1(n) 2C1(n / 2) + C0(n) где C0(n) - сложность процедуры Conflict(1, n). Для С0(n) имеем: C0(n) C0(n/2) + 1, поскольку вызов Conflict(i, n) содержит один (рекурсивный) вызов Conflict(2i, n) и цепочка вызовов обрывается при i > n/2.  Поэтому C0(n) c0 log2 n. Таким образом,

C1(n) 2 C1(n / 2) + c0 log2 n.

Пусть k - некоторое число. Тогда

C1(n) <= 2 k C1(n/2k) +c0 (2 k-1 log2(n/2 k-1) + ...+ log2(n/2) log2 n)

Поскольку С1(1) = 0, имеем C1(n) <= c0 (log2 n + 2 log2(n/2) + ... (n/2) log2(2)). Заменим log( n/2 i ) на log2 n, усилив неравенство. Получим C1(n) <= (c0 log2 n)(1 + 2 + 4 + ... n/2)

Сумма в скобках не превосходит n. Поэтому

   C1(n) <= с0 n log2 n     (7)

Арифметический цикл II-го этапа выполняется n - 2 раза и каждое повторение содержит ConSwap(k, 1) и Conflict(1, k - 1).  Поэтому его сложность C2(n) можно оценить неравенством C2(n) <= (1+C0(n-1)) + (1+C0(n-2)) + ... + (1+C0(2)) Заменим C0(i) на C0(n-1), усилив неравенство. Получим

   C2(n) <= n + n C0(n-1) = c1 n log2 n   (8)

Окончательно С(n) = C1(n) + C2(n) = (c0+c1) n log2 n, или

   С(n) = O( n log2 n )     (9)

Мы показали, что пирамидальная сортировка (с точностью до мультипликативной константы) оптимальна: ее сложность совпадает (с той же точностью) с нижней оценкой задачи.

Быстрая сортировка Хоара.

Усовершенствовав метод сортировки, основанный на обменах, К.Хоар предложил алгоритм QuickSort сортировки массивов, дающий на практике отличные результаты и очень просто программируемый.  Автор назвал свой алгоритм быстрой сортировкой.

Идея К. Хоара состоит в следующем:

1 Выберем некоторый элемент x массива A случайным образом;

2.Просматриваем массив в прямом направлении (i = 1, 2,...), ища в нем элемент A[i] не меньший, чем x;

3.Просматриваем массив в обратном направлении (j = n, n-1,..), ища в нем элемент A[j] не больший, чем x;

4.Меняем местами A[i] и A[j];

Пункты 2-4 повторяем до тех пор, пока i < j;

В результате такого встречного прохода начало массива A[1..i] и конец массива A[j..n] оказываются разделенными “барьером” x: A[k] x при k < i , A[k] x при k > j , причем на разделение мы затратим не более n/2 перестановок. Теперь осталось проделать те же действия с началом и концом массива, т.е. применить их рекурсивно!

Таким образом, описанная нами процедура Hoare зависит от параметров k и m - начального и конечного индексов обрабатываемого отрезка массива.

Procedure Swap(i, j : Integer);

      Var b : Real;

    Begin

       b := a[i]; a[i] := a[j]; a[j] := b

    End;

Procedure Hoare(L, R : Integer);

      Var left, right : Integer;

           x : Integer;

    Begin

     If L < R then begin

       x := A[(L + R) div 2];    {выбор барьера x}

       left := L; right := R ;

       Repeat {встречный проход}

        While A[left] < x do left := Succ(left);  {просмотр вперед}

        While A[right] > x do right := Pred(right);  {просмотр назад}

         If left <= right then begin

          Swap(left, right); {перестановка}

          left := Succ(left);  right := Pred(right);

         end

        until left > right;

        Hoare(L, right); {сортируем начало}

        Hoare(left, R) {сортируем конец}

      end

     End;

Program QuickSort;

   Const n = 100;

     Var A : array[1..n] of Integer;

{ процедуры Swap, Hoare, ввода и вывода }

Begin

   Inp;  Hoare(1, n);  Out

 End.

Наиболее тонкое место алгоритма Хоара - правильная обработка момента окончания движения указателей left, right. Заметьте, что в нашей версии переставляются местами элементы, равные x. Если в циклах While заменить условия (A[left] < x) и (A[right] > x) на (A[left] <= x) и (A[right] >=x), при x = Max(A) индексы left и right пробегут весь массив и побегут дальше! Усложнение же условий продолжения просмотра ухудшит эффективность программы.

Анализ сложности алгоритма в среднем, использующий гипотезу о равной вероятности всех входов, показывает, что

C(n) = O(n log2 n),  M(n) = O(n log2 n).

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

3.Поиск k-того в массиве. Поиск медианы массива.

С задачей сортировки тесно связана нахождения k-того по величине элемента в массиве. С ее частным случаем - поиском 1-го (минимального) и n-того элемента (максимального) - мы уже знакомы. Аналогично можно решить задачу поиска 2-го и n-1-го по величине элементов, однако количество сравнений возрастает вдвое. Прежде, чем рассмотреть задачу в общем виде, приведем необходимое определение.

K-тым по величине элементом последовательности называется такой элемент b этой последовательности, для которого в последовательности существует не более, чем k-1 элемент, меньший, чем b и не менее k элементов,  меньше или равных b.

Например, в последовательности {2, 1, 3, 5, 4, 2, 2, 3 } четвертым по величине будет 2.

Иными словами, если отсортировать массив, то k-тый элемент окажется на k-том месте (b = A[k]). Можно ожидать, что наиболее сложным будет алгоритм поиска элемента при          k = n div 2 - т.е. элемента, равноудаленного от концов массива. Этот элемент назовем медианой массива.

Очевидное решение задачи поиска k-того элемента - полная либо частичная (до k) сортировка массива A. Например, алгоритм TreeSort можно прервать после просеивания k элементов. Тогда C(n) = O(n + k log2 n)

Однако эффективное на практике решение получается, если применить идею К.Хоара разделения массива барьером. В самом деле, анализ метода разделения элементов по барьеру в процедуре Hoare показывает, что после ее окончания имеют место соотношения

Right < Left, при i < Left A[i] <= x, при i > Right A[i] >= x

Таким образом, отрезок First .. Last разбивается на 3 части:

 

  First                Right            Left                Last

A[i] <= x             A[i] = x              A[i] >= x

Дальнейший поиск, следовательно, можно организовать так:

Если k <= right

то искать k-тый элемент в A[First .. right]

иначе если k <= left

 то k-тый элемент равен x

 иначе искать k - тый элемент в A[left + 1 .. Last]

Procedure HoareSearch(First, Last : Integer);

       Var l, r : Integer; x : Integer;

      Begin

       If First = Last

         then Write(A[k]) { остался 1 элемент }

         else If First < Last then begin

          x := A[k]; {выбор барьера x}

           l := First; r := Last;

           Repeat {встречный проход}

            While A[l] < x do l := Succ(l);

            While A[r] > x do r := Pred( r );

             If l <= r then begin

              Swap(l, r);

              l := Succ(l); r := Pred( r );

             end

            until l > r;

       If k <= r

       then HoareSearch(First, r) {1-ая часть массива}

       else If k <= l

        then Write(x) {элемент найден}

        else HoareSearch(l+1, Last) {3-ая часть массива}

       end

     End;

Автор метода предлагает в качестве барьерного элемента выбирать A[k], хотя это не дает никаких преимуществ перед выбором среднего или случайного элемента.

Как и алгоритм быстрой сортировки, этот алгоритм в худшем случае неэффективен. Если при каждом разделении 1-ая часть массива будет содержать 1 элемент, алгоритм затратит O(kn) шагов. Однако в среднем его сложность линейна (вне зависимости от k). В частности, даже при поиске медианы A[n div 2] C(n) = O(n), M(n) = O(n)

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

4.Метод “разделяй и властвуй”.

Один из наиболее известных методов проектирования эффективных алгоритмов - метод “разделяй и властвуй” заключается в сведении решаемой задачи к решению одной или нескольких более простых задач.

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

Отличительный признак метода - разбиение задачи на равные по сложности подзадачи. Эффективность получаемого алгоритма зависит от во первых, от количества действий, затраченных на сведение задачи к подзадачам, во-вторых - баланса сложностей подзадач.

Классический пример применения метода - бинарный поиск в упорядоченном массиве. Массив разбивается на две равные части. Используя затем два сравнения, алгоритм либо находит элемент, либо определяет ту половину, в которой его следует искать - т.е сводит задачу размера n к задаче размера n/2.  Этот же прием используется в алгоритмах Хоара сортировки и поиска, в алгоритме возведения числа в натуральную степень ($8, пример 11), в некоторых других ранее сформулированных задачах.  Рассмотрим известное решение задачи поиска минимального и максимального элемента в массиве.

Пусть A[1..n] - числовой массив. Требуется найти Max(A) и Min(A). Предположим, что n = 2 k. Такое предположение дает возможность делить массив и все получаемые в процессе вычислений его части пополам.

Опишем основную процедуру MaxMin.Пусть S - некоторое множество и |S| = m. Разобьем S на равные по числу числу элементов части: S = S1  S2, S1S2 = , |S1| = m/2, |S2| = m/2. Найдем Max1, Min1 как результат MaxMin(S1) и Max2, Min2 как результат MaxMin(S2).

Затем Max := Max(Max1, Max2);  Min := Min(Min1, Min2);

procedure MaxMin(L, R : Integer Var Max, Min : Real);

      Var Max1, Min1, Max2, Min2 : Real;

    Begin { L, R - границы индексов массива A }

     If R - L = 1

       then If A[L] > A[R] { выбор Маx, Min за одно сравнение }

        then begin

           Max := A[l]; Min := A[R] end

        else begin

           Max := A[R]; Min := A[L] end

         else begin

          C := (R + L - 1) div 2;

          MaxMin(L, C, Max1, Min1);

          MaxMin(C+1, R, Max2, Min2);

          If Max1 > Max2 then Max := Max1 else Max := Max2;

          If Min1 < Min2 then Min := Min1 else Min := Min2

         end

      End;

Пусть С(n) - оценка сложности процедуры MaxMin в терминах сравнений. Тогда, очевидно

С(2) = 1,

C(n) = 2 C(n/2) + 2 при n > 2

Отcюда С(n) = 2 (n/4 + n/8 + ... + 1) + n/2 = 2(n/2 - 1) + n/2;

C(n) = 3/2 n - 2

Для сравнения заметим, что алгоритм поиска Max и Min методом последовательного просмотра массива требует 2 n - 2 сравнений.  Таким образом, применение метода “разделяй и властвуй” уменьшило временную сложность задачи в фиксированное число раз.  Разумеется, истинная причина улучшения - не в применении рекурсии, а в том, что максимумы и минимумы двух рядом стоящих элементов массива ищутся за одно сравнение! Метод позволил просто и естественно описать вычисления.

Длина цепочки рекурсивных вызовов в алгоритме равна log2 n -1, и в каждой копии используются 4 локальных переменных. Поэтому алгоритм использует вспомагательную память объема O(log2 n), распределяемую динамически. Это - плата за экономию времени.

5.Метод цифровой сортировки.

Иногда при решениии задач типа задачи сортировки можно использовать особенности типа преобразуемых данных для получения эффективного алгоритма. Рассмотрим одну их таких задач - задачу об обращении подстановки.

Подстановкой множества 1..n назовем двумерный массив A[1..2, 1..n] вида

1

2

..........

n-1

n

j1

j2

...........

j n-1

j n

в котором 2-ая строка содержит все элементы отрезка 1.  .n.  Подстановка B называется обратной к подстановке A, если B получается из A сортировкой столбцов A в порядке возрастания элементов 2-ой строки с последующей перестановкой строк.  Требуется построить алгоритм вычисления обратной подстановки. Из определения следует, что столбец [i, ji] подстановки A нужно преобразовать в столбец [ji , i] и поставить на ji-тое место в подстановке B.

{Type NumSet = 1..n;

Substitution = array[ 1..2, NumSet] of NumSet; }

Procedure Reverse ( Var A, B : Substitution);

    Begin

     For i := 1 to n do begin

       B[A[2, i], 2] := i; B[A[2, i], 1] := A[2, i]

     end

    End;

Сложность процедуры Reverse линейна, поскольку тело арифметического цикла состоит из двух операторов присваивания. Между тем столбцы подстановки отсортированы.

Аналогичная идея используется в так называемой сортировке исчерпыванием (или цифровой сортировке), применяемой для сортировки последовательностей слов (многоразрядных чисел).  Для каждой буквы алфавита алгоритм создает структуру даных “черпак”, в которую пересылаются слова, начинающиеся на эту букву. В результате просмотра последовательность оказывается отсортированной по первой букве. Далее алгоритм применяют рекурсивно к каждому “черпаку”, сортируя его по следующим буквам.

6.Задачи и упражнениия.

1.Дан массив A[1..900] of 1..999 . Найти трехзначное число, не содержащееся в этом массиве. Рассмотреть два варианта задачи:

a)Вспомагательные массивы в алгоритме не используются;

б)Использование вспомагательных массивов разрешено.

2.Реализовать алгоритм TreeSort, применив метод вложения дерева в массив. Для этого использовать вспомагательный массив B.

3.Реализовать итеративную версию алгоритма HeapSort:

a)Заменить рекурсию в процедуре SortTree арифметическим циклом For...downto, обрабатывающем дерево по уровням, начиная с нижнего;

б) Заменить рекурсию в процедуре Conflict итерационным циклом, управляемым переменной i. { i := 2i или i := 2i + 1 }.

4.Реализовать итеративную версию алгоритма процедуры HoareSeach, заменив рекурсию итерационным циклом.

5-6 Применить для решения задач 1-2 параграфа 8 идею Хоара.

7.Реализовать алгоритм “тернарного” поиска элемента в упорядоченном массиве, деля участок поиска на 3 приблизительно равные части. Оценить сложность алгоритма в терминах C(n).Сравнить эффективности бинарного и тернарного поиска.

8.Реализовать алгоритм поиска максимального и минимального элементов в массиве (процедура MaxMin) для произвольного n.

9.Пусть А[1..n] - массив целых чисел, упорядоченный по возрастанию (A[i] < A[i+1]). Реализовать алгоритм поиска такого номера i, что A[i] = i методом “разделяй и властвуй”. Оценить сложность алгоритма.

10-12. Применить для решения задач 3-5 параграфа 8 метод “разделяй и властвуй”.

13.Реализовать алгоритм процедуры Reverse “на месте”, формируя обратную подстановку в массиве A.


a1

 a2

 a3

 a4

 a5

 a6

a7

 a8

a2

a3

a5

a8

a3

a5

 a5

 a1

 a2

 a3

 a4

 M

 a6

 a7

 a8

a2

a3

M

a8

a3

M

M

 a5

 a3

 a4

 M

 a6

 a7

 a8

a3

a6

a8

a3

 a6

a3

 a1

 a2

a2

 a5   a3

 A[2i]

 A[2i+1]

A[i]

 45

13

24

31

11

28

49

40

19

27


 

А также другие работы, которые могут Вас заинтересовать

38340. Менеджмент. Сутність менеджменту 1.29 MB
  Планування в організації. В українському законодавстві організації які мають статус юридичної особи називають підприємствами товариствами асоціаціями об’єднаннями тощо. За способом і метою утворення організації поділяють на формальні та неформальні. За кількістю цілей виділяють прості організації мають одну ціль і складні організації ставлять перед собою комплекс взаємопов’язаних цілей яких в економіці переважна більшість.
38341. Менеджмент как теория управления 74.87 KB
  Управление с точки зрения философии это функция биологических социальных технических организационных систем которые обеспечивает сохранение их структуры и поддерживает определенный режим деятельности; с точки зрения экономических понятий – это процесс распределения движения ресурсов в организации с заранее заданной целью по заранее разработанному плану с непрерывным контролем результатов. 2 менеджмент это процесс достижения целей организации с помощью других людей. Менеджер это человек который занимает постоянную управляющую...
38342. Бизнес-планирование инвестиционных проектов 34.5 KB
  Бизнесплан это стандартный документ в котором детально обосновывается концепция инвестиционного проекта приводятся основные технические экономические финансовые и социальные характеристики. Бизнесплан позволяет обобщить результаты которые будут достигнуты в результате внедрения инвестиционного проект определить его эффективность и жизнеспособность установить направления возможного детального развития. Бизнесплан является основанием для получения финансовых ресурсов правовой и организационной поддержки.
38344. ПРАВО ВНЕШНИХ СНОШЕНИЙ 118.5 KB
  Институтом этой отрасли является право на внешние сношения вытекающее из суверенитета государства право на участие в жизни международного сообщества на основе суверенного равенства. Право государства на внешние сношения основано на международноправовых нормах и существует независимо от внутреннего права которое может обходить область внешних сношений молчанием. Согласно принципу невмешательства государства не имеют права вмешиваться не только во внутренние но и во внешние дела другого государства входящие в его суверенную...
38345. ШПАРГАЛКИ З ПРАВОЗНАВСТВА 673 KB
  Загальна характеристика основних галузей права України Державне конституційне право провідна галузь права та законодавства що криє в собі систему правових норм інститутів і нормативноправових актів які закріплюють і регулюють відносини народовладдя основи конституційного ладу України правового статусу людини і громадянина територіального устрою системи державних органів та організації місцевого самоврядування в Україні. Розглядають такі види підзаконних нормативноправових актів залежно від суб'єктів що їх видали: ...
38346. Педагогическая практика преподавателя экономики 57.5 KB
  8 Литература 10 Введение Прохождение практики по специальности студентовбакалавров является неотъемлемой частью процесса подготовки высококвалифицированных специалистов в высших учебных заведениях. Продолжительность практики 2 недели с 16 по 29 мая 2011 года. Целью данной практики является подготовка студентабакалавра к ведению самостоятельной практической деятельности на должности преподавателя экономических дисциплин закрепление уже приобретенных знаний и навыков и соединить их с широким спектром...
38347. Предпринимательство в переходной экономике 66.5 KB
  Типы предприятий в переходной экономике. Особенности эволюции крупных предприятий . Взаимоотношения предприятий в переходной экономике Предпринимательство инициативная самостоятельная деятельность граждан направленная на...