Сортировка вставками

§1. Сортировка вставками Основная идея алгоритма: сортируемая последовательность рассматривается как состоящая из двух частей – уже отсортированной и ещё неотсортированной; на каждом шаге алгоритма первый элемент неотсортированной части вставляется в нужное место отсортированной части; тем самым неотсортированная часть уменьшается до тех пор, пока не станет пустой. 1 2 3 4 5 6 7 8 9 10 I n s e r t S o r t ( i n / out {a[i]}n−1 ) i←1 while i < n: elem ← a[i] loc ← i − 1 w h i l e loc ≥ 0 and a[loc] > elem : a[loc + 1] ← a[loc] loc ← loc − 1 a[loc + 1] ← elem i←i+1 1 Пример. InsertSort ([10 , loc: ? 10 i: ? 8 9 n: 4 11 8, 9, loc: ? 10 elem: ? 11]) i: 1 8 9 n: 4 11 10 i: 1 8 9 10 elem: ? n: 4 11 elem: 8 3. elem ← a [i] loc: 0 10 8 9 n: 4 11 2. i < n ? i: 1 8 i: 1 elem: ? 1. i ← 1 loc: ? loc: ? 9 n: 4 11 elem: 8 4. loc ← i − 1 loc: 0 10 i: 1 8 9 n: 4 11 elem: 8 5. loc ≥ 0 and a [loc] > elem ? 2 loc: 0 10 i: 1 10 n: 4 9 11 loc: -1 10 elem: 8 6. a [loc + 1] ← a [loc] loc: -1 8 i: 1 10 9 n: 4 11 elem: 8 9. a [loc + 1] ← elem i: 1 10 n: 4 9 11 loc: -1 10 i: 1 10 n: 4 9 11 elem: 8 elem: 8 7. loc ← loc − 1 8. loc ≥ 0 and a [loc] > elem ? loc: -1 8 i: 2 10 9 n: 4 11 elem: 8 10. i ← i + 1 loc: -1 8 i: 2 10 9 n: 4 11 elem: 8 11. i < n ? 3 loc: -1 8 i: 2 10 9 n: 4 11 loc: 1 8 elem: 9 8 i: 2 10 10 10 9 n: 4 11 loc: 1 8 elem: 9 12. elem ← a [i] loc: 1 i: 2 n: 4 11 elem: 9 15. a [loc + 1] ← elem 8 i: 2 10 10 10 9 n: 4 11 elem: 9 13. loc ← i − 1 loc: 0 i: 2 n: 4 11 elem: 9 16. loc ← loc − 1 14. loc ≥ 0 and a [loc] > elem ? loc: 0 8 i: 2 10 10 n: 4 11 elem: 9 17. loc ≥ 0 and a [loc] > elem ? 4 loc: 0 8 i: 2 9 10 n: 4 11 loc: 0 8 elem: 9 8 i: 3 9 10 9 10 n: 4 11 loc: 0 8 elem: 9 18. a [loc + 1] ← elem loc: 0 i: 3 n: 4 11 elem: 11 21. elem ← a [i] 8 i: 3 9 10 9 10 n: 4 11 elem: 9 19. i ← i + 1 loc: 2 i: 3 n: 4 11 elem: 11 22. loc ← i − 1 20. i < n ? loc: 2 8 i: 3 9 10 n: 4 11 elem: 11 23. loc ≥ 0 and a [loc] > elem ? 5 loc: 2 8 i: 3 9 10 n: 4 11 elem: 11 24. a [loc + 1] ← elem loc: 2 8 i: 4 9 10 n: 4 11 elem: 11 25. i ← i + 1 loc: 2 8 i: 4 9 10 n: 4 11 elem: 11 26. i < n ? 6 §2. Применение модели машины с произвольным доступом к памяти Анализ алгоритма заключается в предсказании объёма требуемых для его работы вычислительных ресурсов. Чаще всего нас интересует время работы алгоритма и объём используемой оперативной памяти. Для оценки времени работы алгоритма используют гипотетический компьютер, называемый машиной с произвольным доступом к памяти (Random Access Machine, или RAM) и обладающий следующими свойствами: 1. каждая простая операция (+, ?, −, =, проверка условия, вызов подпрограммы) выполняется ровно за один шаг; 2. циклы и подпрограммы не считаются простыми операциями: они рассматриваются как композиции операций, составляющих их тела; 3. каждое обращение к памяти выполняется ровно за один шаг. 7 Пример. e l e m := A [ i ] Шаги: 1. чтение i; 2. умножение i на размер элемента массива; 3. прибавление адреса начала массива; 4. чтение A[i]; 5. запись в elem. Пример. while i < N do Шаги: 1. чтение i; 2. чтение N; 3. операция <; 4. проверка условия. 8 Пример. while ( l o c >= 0 ) and ( A [ l o c ] > e l e m ) do Шаги: 1. чтение loc; 2. операция >=; 3. проверка условия (если «ложь», то закончить); 4. чтение loc; 5. умножение loc на размер элемента массива; 6. прибавление адреса начала массива; 7. чтение A[loc]; 8. чтение elem; 9. операция >; 10. проверка условия. 9 Пример. Сортировка вставками procedure I n s e r t i o n S o r t (A : n: elem , l o c : i n t e g e r ; array of integer ) integer ; var i , begin i := 1 ; w h i l e i < n do begin e l e m := A [ i ] ; l o c := i − 1 ; w h i l e ( l o c >= 0 ) and ( A [ l o c ] > e l e m ) do begin A [ l o c +1] := A [ l o c ] ; l o c := l o c −1 end ; A [ l o c +1] := e l e m ; i := i +1 end end 10 Пример. Сортировка вставками (с указанием количества шагов) procedure I n s e r t i o n S o r t (A : n: elem , l o c : i n t e g e r ; array of integer ) integer ; var i , begin (∗ 1 ∗) i := 1 ; (∗ 4 ∗) w h i l e i < n do begin (∗ 5 ∗) e l e m := A [ i ] ; (∗ 3 ∗) l o c := i − 1 ; (∗ 3|10 ∗) w h i l e ( l o c >= 0 ) and ( A [ l o c ] > e l e m ) do begin (∗ 9 ∗) A [ l o c +1] := A [ l o c ] ; (∗ 3 ∗) l o c := l o c −1 end ; (∗ 6 ∗) A [ l o c +1] := e l e m ; (∗ 3 ∗) i := i +1 end end 11 Имея набор входных данных, мы можем вычислить, за сколько шагов выполнится алгоритм. Однако, для оценки качества алгоритма требуется знать, как он поведёт себя на всех наборах входных данных. Определение. Сложность алгоритма в наилучшем (наихудшем) случае – это функция, задающая зависимость минимального (максимального) количества шагов машины с произвольным доступом к памяти, выполняющей данный алгоритм, от размера входных данных. Задание. Получить выражение для сложности алгоритма сортировки вставками в наилучшем и наихудшем случае: Cmin (n) =? Cmax (n) =? 12 Решение (наилучший случай – данные отсортированы по возрастанию) Внутренний цикл – всегда 10 шагов. Одна итерация внешнего цикла: 4 + 5 + 3 + 10 + 6 + 3 = 31 шаг. Внешний цикл выполняется n − 1 раз, если n > 0, поэтому  5, n = 0; Cmin (n) = 1 + 4 + 31(n − 1) = 31n − 26, n > 0. 13 Решение (наихудший случай – данные отсортированы по убыванию) Одна итерация внутреннего цикла: 10 + 9 + 3 = 22 шага. Внутренний цикл выполняется i раз за время 22i + 3, поэтому одна итерация внешнего цикла: 4 + 5 + 3 + (22i + 3) + 6 + 3 = 22i + 24 шагов. Внешний цикл выполняется n − 1 раз, если n > 0, поэтому    5, n = 0;   Cmax (n) =    1+4+ n−1 P (22i + 24) = 5 + 24 (n − 1) + 22 n−1 P i= i=1 i=1     n (n − 1)   = 11n2 + 13n − 19, = 24n − 19 + 22 × 2 n > 0. Проверка. Cmin (1) = Cmax (1) = 5. 14 §3. Асимптотическая сложность алгоритма В этом параграфе будем рассматривать только функции, областью определения которых являются целые неотрицательные числа. При этом эти функции не могут принимать отрицательных значений. Определение. Функция g (n) является асимптотической верхней границей для функции f (n), если можно найти положительные константы c и n0 такие, что для любого n ≥ n0 справедливо f (n) ≤ c · g (n). Для некоторой функции g (n) обозначение O (g (n)) (читается «о большое от g от n») означает множество функций, для которых g (n) является асимптотической верхней границей: O (g (n)) = {f (n) | (∃c, n0 > 0) : ∀n ≥ n0, f (n) ≤ c · g (n) }. f (n) ∈ O (g (n)) принято записывать, как f (n) = O (g (n)) или f (n) - g (n). 15 Определение. Функция g (n) является асимптотической нижней границей для функции f (n), если можно найти положительные константы c и n0 такие, что для любого n ≥ n0 справедливо f (n) ≥ c · g (n). Для некоторой функции g (n) обозначение Ω (g (n)) (читается «омега большое от g от n») означает множество функций, для которых g (n) является асимптотической нижней границей: Ω (g (n)) = {f (n) | (∃c, n0 > 0) : ∀n ≥ n0, f (n) ≥ c · g (n) }. f (n) ∈ Ω (g (n)) принято записывать, как f (n) = Ω (g (n)) или f (n) % g (n). Замечание. f (n) - g (n) ⇐⇒ g (n) % f (n). Задание. Доказать, что 31n − 26 = Ω (n).   Задание. Доказать, что 11n2 + 13n − 19 = O n2 . 16 Если одновременно f (n) - g (n) и f (n) % g (n), то говорят, что f (n) является асимптотически точной оценкой функции g (n). При этом g (n) тоже является асимптотически точной оценкой функции f (n) Для некоторой функции g (n) обозначение Θ (g (n)) (читается «тета большое от g от n») означает множество функций, для которых g (n) является асимптотически точной оценкой: Θ (g (n)) = {f (n) | (f (n) - g (n)) ∧ (f (n) % g (n)) }. f (n) ∈ Θ (g (n)) принято записывать, как f (n) = Θ (g (n)) или f (n) ' g (n). Теорема (об асимптотике многочлена) Для любого многочлена p (n) = d P i=0  aini, где ai – константы и ad > 0,  справедливо: p (n) = Θ nd . Константа – это  полином нулевой степени, поэтому константы обозначаются как Θ n0 или Θ (1). 17 Определение. Асимптотическая сложность алгоритма в наилучшем (наихудшем) случае – это асимптотическая нижняя (верхняя) граница сложности алгоритма в наилучшем (наихудшем случае). Пример. Асимптотическая сложность алгоритма вставками:  сортировки  в наилучшем случае Ω (n), в наихудшем – O n2 . В общем случае асимптотическая сложность алгоритма в наилучшем случае доказывается значительно сложнее, чем в наихудшем случае. 18 Рассмотрим примеры задач, алгоритмы решения которых имеют разную асимптотическую сложность в наихудшем случае. Задача. Дано дерево, состоящее из n узлов, соединённых дугами. Необходимо найти ближайшего общего предка некоторой пары узлов. Дерево подвергается предварительной обработке, выполняемой за O (n) – линейная сложность. После этого можно найти ближайшего общего предка для любой пары узлов за время O (1) – константная сложность. Задача. Дана отсортированная последовательность из n элементов. Нужно найти в этой последовательности некоторый элемент. Задача решается методом деления пополам за O (lg n) – логарифмическая сложность. 19 Задача. Отсортировать последовательность из n элементов. Используя алгоритм пирамидальной сортировки или алгоритм сортировки слиянием, мы можем отсортировать любую последовательность, допускающую обращение к произвольному элементу за константное время, за O (n lg n) – квазилинейная сложность; используя сортировку вставками, мы можем отсортировать любую последовательность, даже не допускающую   обращение к произвольному элементу за константное время, за O n2 – квадратичная сложность. Задача. Имеется n работников и n заданий. Каждого работника можно поставить на выполнение любого задания. Однако стоимость выполнения задания различна для разных пар «работник-задание». Необходимо распределить по одному заданию на каждого работника так, чтобы суммарная стоимость была минимальна.   Задача решается так называемым «венгерским алгоритмом» за O n3 – кубическая сложность.  Вообще, сложность O nd  называется полиномиальной. 20 Задача. (Задача коммивояжёра) Имеется набор городов и матрица расстояний между всеми парами городов. Нужно найти кратчайший путь, который проходит через каждый город ровно по одному разу, а также начинается и заканчивается в одном и том же   городе. 2 n Алгоритм Хельда-Карпа решает задачу за O n 2 . Вообще, сложность O (cn) называется экпоненциальной. 21 §4. Размещения, перестановки и сочетания Пусть имеется конечное множество Q = {q0, q1, . . . , qn−1}. Определение 4.1. Размещение на множестве Q по m элементов – это кортеж p ∈ Qm. Если один и тот же элемент q присутствует в размещении p более чем в одном экземпляре, то говорят, что p – размещение с повторениями. В противном случае, p – размещение без повторений. 22 Правило произведения. Если объект a можно выбрать x способами, и если после каждого такого выбора объект b можно выбрать y способами, то выбор пары ha, bi в указанном порядке можно осуществить xy способами. Утверждение 4.1. Количество размещений на множестве Q по m элеm ментов с повторениями равно Aem n = n , где n – размер множества Q. 1 . База индукции: m = 1: Ae1 n=n=n . m−1 = nm−1 . Пусть Aen К любому размещению на множестве Q по m−1 элементов с повторениями можно добавить любой из n элементов. em−1 · n = nm.C Тогда по правилу произведения Aem n = An 23 Для записи алгоритма, вычисляющего размещения, нам понадобится, чтобы на множестве Q было определено отношение строгого порядка ≺, то есть чтобы q0 ≺ q1 ≺ . . . ≺ qn−1. Отношение строгого порядка может быть выбрано совершенно произвольно – нам всего лишь нужен способ всегда одинаково перечислять элементы любого подмножества множества Q. Если R ⊆ Q, то цикл, перечисляющий элементы R по порядку ≺, мы будем записывать на псевдокоде как 1 2 for each q ∈ R что −то с д е л а т ь с q 24 Алгоритм вычисления всех размещений на множестве Q по m элементов с повторениями: 1 2 4 5 6 7 8 9 PermutRep ( i n Q , i n m ) P e r m u t R e p _ r e c ( Q , m , hi ) PermutRep_rec ( i n Q , i n m , i n p) if m = 0: что −то с д е л а т ь с p else : f o r each q ∈ Q : P e r m u t R e p _ r e c ( Q , m − 1 , hp, qi ) Из утверждения 4.1 следует, что алгоритм выполняется за время Θ (nm). 25 Утверждение 4.2. Количество размещений на множестве Q по m элементов без повторений равно n! m , где n – размер множества Q. An = (n − m)! n! = n = . . База индукции: m = 1: A1 n (n − 1)! m−1 = Пусть An n! . (n − (m − 1))! К любому размещению на множестве Q по m−1 элементов без повторений можно добавить любой из n − (m − 1) элементов. n! m−1 · (n − (m − 1)) = Тогда по правилу произведения Am = A .C n n (n − m)! 26 Алгоритм вычисления всех размещений на множестве Q по m элементов без повторений: 1 2 4 5 6 7 8 9 Per mut ( i n Q , i n m ) P e r m u t _ r e c ( Q , m , hi ) Permut_rec ( i n Q , i n m , i n p) if m = 0: что −то с д е л а т ь с p else : f o r each q ∈ Q : P e r m u t _ r e c ( Q \ {q} , m − 1 , hp, qi ) Из утверждения 4.2 следует, что алгоритм выполняется за время ! n! Θ . (n − m)! 27 Определение 4.2. Перестановка множества Q – это размещение на множестве Q по n элементов без повторений, где n – размер множества Q. Количество перестановок Pn = An n= n! = n! (n − n)! Можно дать другое определение перестановки: Определение 4.2.1. Перестановка множества Q – это биекция множества Q на себя. Перестановку hqx, qy , . . . , qz i в q0 q1 . . . вать в виде P = qx qy . . . рамках ! определения 4.2.1 принято записыqn−1 . qz Здесь q0 отображается в qx, q1 – в qy , и т.д. 28 Определение 4.3. Сочетание на множестве Q по m элементов – это mэлементное подмножество множества Q. Утверждение 4.3. Количество сочетаний на множестве Q по m элементов равно n! Cnm = , где n – размер множества Q. (n − m)! · m! . Очевидно, что из элементов одного сочетания по m элементов можно составить Pm различных перестановок по m элементов. Am n! n m m m Поэтому An = Cn · Pm, откуда Cn = = . C Pm (n − m)! · m! 29 Алгоритм вычисления всех сочетаний на множестве Q по m элементов: 1 2 4 5 6 7 8 9 10 11 12 13 Comb ( i n Q , i n m ) Comb_rec ( Q , m , ∅ ) Comb_rec ( i n Q , i n m , i n c ) if m = 0: что −то с д е л а т ь с c else : Q0 ← Q f o r each q ∈ Q : i f |Q0| < m : break Q0 ← Q0 \ {q} Comb_rec ( Q0 , m − 1 , c ∪ {q} ) Из утверждения! 4.3 следует, что алгоритм выполняется за время n! . Θ n − m ! · m! ( ) 30 §5. Постановка задачи сортировки Обозначения. Пусть дана последовательность натуральных чисел {ai}n−1 , тогда: – запись a [i] обозначает обращение к i-тому элементу последовательности; – запись a [i : j ] обозначает подпоследовательность, начинающуюся с i-того элемента, и заканчивающуюся j-тым элементом; – операция обмена a [i] ↔ a [j ] означает, что i-тый и j-тый элементы меняются местами. Запись Nulln обозначает последовательность нулей длины n. Пример. Пусть даны последовательности A ← h5, 4, 6, 7, 2i и B ← h8, 9i. Тогда присваивание A [1 : 2] ← B превратит последовательность A в h5, 8, 9, 7, 2i. Если затем выполнить обмен A [1] ↔ A [3], то мы получим последовательность h5, 7, 9, 8, 2i. 31 Пусть множество Nn = {0, 1, . . . , n − 1}. В алгоритмах сортировки мы будем работать с перестановками множества Nn, которые будем понимать как последовательности (кортежи), составленные из n различных натуральных чисел, принадлежащих множеству Nn. ! 0 1 2 3 – перестановка множества N4. 1 3 0 2 P [0] = 1, P [1] = 3, P [2] = 0, P [3] = 2. Пример. P = В алгоритмах мы будем обращаться с перестановками как с обычными последовательностями. 32 Обозначение. Операция инверсии перестановки P записывается как ¬P и перестановки P:  означает «переворот»  ∀i = 0, n − 1 : ¬P [P [i]] = i. Пример. Пусть P = 0 1 2 3 1 2 3 0 ! , тогда ¬P = 0 1 2 3 3 0 1 2 ! . Обозначение. Мы будем использовать обозначение Idn для перестановки  множества  Nn такой, что ∀i = 0, n − 1 : Idn [i] = i. Очевидно, что Idn = ¬Idn. 33 Пусть имеется совокупность из n значений, которые нужно упорядочить: r0, r1, . . . , rn−1. Мы будем называть эти значения записями. Каждая запись ri имеет ключ ki, который управляет процессом сортировки. Ключ может быть составной частью записи, а может вычисляться на основе записи. На множестве ключей вводится отношение строгого порядка C (читается «предшествует »), которое: 1. асимметрично: x C y ⇒y 6 x; 2. транзитивно: (x C y ) ∧ (y C z ) ⇒ x C z. (Из асимметричности следует антирефлексивность: x 6 x.) При этом из отношения C можно построить отношение нестрогого порядка E, если добавить рефлексивность: x E y ⇔ (x C y ) ∨ (x = y ). 34 Задача сортировки последовательности записей hr0, r1, . . . , rn−1i, имеющих ключи k0, k1, . . . , kn−1, заключается в поиске перестановки ! 0 1 ... n − 1 P= такой, что kx0 E kx1 E . . . E kxn−1 . x0 x1 . . . xn−1 Пример." Дана# совокупность " # матриц: " # " # 1 2 3 1 0 1 3 0 r0 = , r1 = , r2 = и r3 = . 3 4 0 5 3 7 0 5 Ключи – определители матриц: k0 = −2, k1 = 15, k2 = −3, k3 = 15. Отношение порядка на множестве ключей – порядок на множестве целых чисел. ! 0 1 2 3 Тогда решение задачи сортировки: P = . 2 0 1 3 Замечание. Классическая постановка задачи сортировки подразумевает, что алгоритм сортировки ничего не знает ни о природе записей, ни о природе ключей. Алгоритм может лишь сравнивать между собой ключи, соответствующие записям. 35 Сортировка называется устойчивой, если она не меняет взаимного расположения записей, имеющих равные ключи, т.е., другими словами, для любых двух записей ri и rj таких, что ki = kj , справедливо, что i < j ⇒ P [ i] < P [ j ] . Пример. Пусть последовательность h103, 12, 93, 35, 14i сортируется по возрастанию младшей цифры числа. Тогда устойчивый алгоритм сортировки всегда даст последовательность h12, 103, 93, 14, 35i, а неустойчивый может поменять местами 103 и 93. 36 Пусть записи r0, r1, . . . , rn−1 имеют ключи k0, k1, . . . , kn−1, и на множестве ключей введено отношение строгого порядка C. Введём отношение ≺⊆ Nn ×Nn (читается «меньше») следующим образом: i ≺ j ⇔ ki C k j . Тогда алгоритм сортировки вставками можно переписать как 1 2 3 4 5 6 7 8 9 I n s e r t S o r t ( i n ≺ , i n n , out P ) P ←Idn i←1 while i < n: loc ← i − 1 w h i l e loc ≥ 0 and P[loc + 1] ≺ P[loc] : P[loc + 1] ↔ P[loc] loc ← loc − 1 i←i+1 Этот алгоритм очевидно устойчив. Дело в том, что операция обмена в строке 7 никогда не будет применена к равным записям. 37 §6. Пузырьковая сортировка Пусть дана последовательность натуральных чисел h5, 4, 7, 2, 3, 6i. Пройдём по ней слева направо, сравнивая соседние элементы и меняя их местами, если они расположены не в порядке возрастания: 1. h4 , 5 , 7, 2, 3, 6i; 2. h4, 5 , 7 , 2, 3, 6i; 3. h4, 5, 2 , 7 , 3, 6i; 4. h4, 5, 2, 3 , 7 , 6i; 5. h4, 5, 2, 3, 6 , 7 i. В результате максимальное число 7 переместилось в крайнее правое положение, т.е. туда, где оно должно находиться в отсортированной последовательности. Кроме того, поменялись местами числа 5 и 4, что тоже сделало последовательность более упорядоченной. 38 Повторим проход по последовательности h4, 5, 2, 3, 6, 7i ещё раз, но теперь не будем рассматривать число 7, так как его положение всё равно не изменится: 1. h4 , 5 , 2, 3, 6, 7i; 2. h4, 2 , 5 , 3, 6, 7i; 3. h4, 2, 3 , 5 , 6, 7i; 4. h4, 2, 3, 5 , 6 , 7i. Мы убеждаемся, что число 6 занимает своё место в отсортированной последовательности. Обратим также внимание на то, что последний обмен был совершён нами на третьем шаге (поменялись 5 и 3). Тем самым мы можем сделать вывод, что число 5 тоже находится на правильном месте, и в дальнейшем мы его уже можем не рассматривать. 39 Следующий проход по последовательности h4, 2, 3, 5, 6, 7i не затрагивает числа 5, 6 и 7: 1. h2 , 4 , 3, 5, 6, 7i; 2. h2, 3 , 4 , 5, 6, 7i. Здесь мы выясняем, что число 4 находится там, где оно должно располагаться в отсортированной последовательности. Для верности выполним ещё один проход, чтобы убедиться, что числа 2 и 3 расположены правильно. 40 Алгоритм сортировки пузырьком: 1 BubbleSort ( in ≺ , i n n , out P ) 2 P ←Idn 3 t←n−1 4 while t > 0: 5 bound ← t 6 t←0 7 i←0 8 w h i l e i < bound : 9 i f P[i + 1] ≺ P[i] : 10 P[i + 1] ↔ P[i] 11 t←i 12 i←i+1 Сортируемая последовательность, как и в случае сортировки вставками, делится на две части: отсортированную и неотсортированную. Переменная t на момент проверки условия вшешнего цикла всегда содержит индекс последней записи неотсортированной части, то есть на каждой итерации цикла неотсортированная последовательность содержит записи с индексами от 0 до t. 41 i: ? 5 10 t: ? 9 n: 4 i: ? 8 5 bound: ? 10 t: 3 9 n: 4 i: ? 8 5 bound: ? 1. t ← n − 1 i: 0 5 t: 0 n: 4 10 9 8 bound: 3 3. bound ← t, t ← 0, i←0 i: 0 5 t: 0 n: 4 10 9 8 bound: 3 4. i < bound ? n: 4 10 t: 3 9 8 bound: ? 2. t > 0 ? i: 0 5 t: 0 n: 4 10 9 8 bound: 3 5. P [i + 1] ≺ P [i] ? 42 i: 1 5 n: 4 10 t: 0 9 8 bound: 3 6. i ← i + 1 i: 1 5 t: 0 n: 4 9 10 8 bound: 3 9. P [i + 1] ↔ P [i] i: 1 5 n: 4 10 t: 0 9 8 bound: 3 7. i < bound ? i: 1 5 t: 1 n: 4 9 10 8 bound: 3 10. t ← i i: 1 5 n: 4 10 t: 0 9 8 bound: 3 8. P [i + 1] ≺ P [i] ? i: 2 5 t: 1 n: 4 9 10 8 bound: 3 11. i ← i + 1 43 i: 2 5 n: 4 9 t: 1 10 8 bound: 3 12. i < bound ? i: 2 5 t: 2 9 i: 2 5 10 8 bound: 3 13. P [i + 1] ≺ P [i] ? i: 3 10 5 bound: 3 t: 2 15. t ← i 9 t: 1 n: 4 8 n: 4 9 i: 2 5 8 10 bound: 3 14. P [i + 1] ↔ P [i] i: 3 10 5 bound: 3 t: 2 16. i ← i + 1 9 t: 1 n: 4 8 n: 4 n: 4 9 8 10 bound: 3 17. i < bound ? 44 i: 3 5 9 t: 2 n: 4 i: 0 10 5 bound: 3 t: 0 8 18. t > 0 ? i: 0 5 t: 0 9 i: 1 10 5 bound: 2 t: 0 21. P [i + 1] ≺ P [i] ? i: 0 10 5 bound: 2 t: 0 8 19. bound ← t, t ← 0, i←0 n: 4 8 9 n: 4 9 i: 1 10 5 bound: 2 t: 0 22. i ← i + 1 9 8 10 bound: 2 20. i < bound ? n: 4 8 n: 4 n: 4 9 8 10 bound: 2 23. i < bound ? 45 i: 1 5 9 t: 0 n: 4 i: 1 10 5 bound: 2 t: 0 8 24. P [i + 1] ≺ P [i] ? i: 2 5 t: 1 8 i: 2 10 5 bound: 2 t: 1 27. i ← i + 1 i: 1 10 5 bound: 2 t: 1 9 25. P [i + 1] ↔ P [i] n: 4 9 8 n: 4 8 i: 2 10 5 bound: 2 t: 1 28. i < bound ? 8 9 10 bound: 2 26. t ← i n: 4 9 n: 4 n: 4 8 9 10 bound: 2 29. t > 0 ? 46 i: 0 5 8 t: 0 n: 4 i: 0 10 5 bound: 1 t: 0 9 30. bound ← t, t ← 0, i←0 i: 1 5 t: 0 8 i: 1 10 5 bound: 1 t: 0 33. i ← i + 1 i: 0 10 5 bound: 1 t: 0 9 31. i < bound ? n: 4 9 8 n: 4 8 i: 1 10 5 bound: 1 t: 0 34. i < bound ? 8 9 10 bound: 1 32. P [i + 1] ≺ P [i] ? n: 4 9 n: 4 n: 4 8 9 10 bound: 1 35. t > 0 ? 47 Наилучший случай для алгоритма сортировки пузырьком – это когда данные уже отсортированы. Тогда внешний цикл имеет одну итерацию, а вложенный цикл – (n − 1) итераций. Тем самым в наилучшем случае асимптотическая сложность алгоритма составляет Ω (n). В наихудшем случае данные отсортированы в обратном порядке («по убыванию»). Тогда внешний цикл работает n раз, а вложенный цикл – от (n−1) до 1 раза. Поэтому в наихудшем случае асимптотическая сложность  алгоритма составляет O n2 . Сортировка пузырьком устойчива по тем же соображениям, что и сортировка вставками. 48 §7. Сортировка прямым выбором Основная идея алгоритма сортировки прямым выбором: 1. находим максимальную запись в сортируемой последовательности; 2. меняем её местами с последней записью, тем самым максимальная запись занимает подобающее её место в последовательности; 3. повторяем вышеприведённые шаги для остатавшейся последовательности (лишённой последней записи). 1 SelectSort ( in ≺ , i n n , out P ) 2 P ←Idn 3 j ←n−1 4 while j > 0: 5 k←j 6 i←j−1 7 while i ≥ 0: 8 i f P[k] ≺ P[i] : 9 k←i 10 i←i−1 11 P[j] ↔ P[k] 12 j ←j−1 49 i: ? 7 n: 4 3 9 k: ? 1 j: ? i: ? 7 n: 4 3 9 k: ? 1 j: 3 1. j ← n − 1 i: 2 7 k: 3 n: 4 3 9 1 j: 3 3. k ← j, i ← j − 1 i: 2 7 n: 4 3 9 k: 3 4. i ≥ 0 ? 1 j: 3 i: ? 7 n: 4 3 9 1 k: ? j: 3 2. j > 0 ? i: 2 7 k: 3 n: 4 3 9 1 j: 3 5. P [k] ≺ P [i] ? 50 i: 2 7 n: 4 3 9 k: 2 1 j: 3 6. k ← i k: 2 n: 4 3 7 n: 4 3 9 k: 2 1 j: 3 7. i ← i − 1 i: 1 7 i: 1 9 1 j: 3 9. P [k] ≺ P [i] ? i: 0 7 k: 2 n: 4 3 9 1 j: 3 10. i ← i − 1 i: 1 7 n: 4 3 9 k: 2 1 j: 3 8. i ≥ 0 ? i: 0 7 k: 2 n: 4 3 9 1 j: 3 11. i ≥ 0 ? 51 i: 0 7 n: 4 3 9 k: 2 1 j: 3 12. P [k] ≺ P [i] ? i: -1 7 k: 2 n: 4 3 1 9 j: 3 15. P [j ] ↔ P [k] i: -1 7 n: 4 3 9 k: 2 1 j: 3 13. i ← i − 1 i: -1 7 k: 2 n: 4 3 1 9 j: 2 16. j ← j − 1 i: -1 7 n: 4 3 9 k: 2 1 j: 3 14. i ≥ 0 ? i: -1 7 k: 2 n: 4 3 1 9 j: 2 17. j > 0 ? 52 i: 1 7 n: 4 3 1 k: 2 9 j: 2 18. k ← j, i ← j − 1 i: 1 7 n: 4 3 1 k: 1 21. k ← i 9 j: 2 i: 1 7 n: 4 3 1 k: 2 9 j: 2 19. i ≥ 0 ? i: 0 7 k: 1 n: 4 3 1 9 j: 2 22. i ← i − 1 i: 1 7 n: 4 3 1 k: 2 9 j: 2 20. P [k] ≺ P [i] ? i: 0 7 k: 1 n: 4 3 1 9 j: 2 23. i ≥ 0 ? 53 i: 0 7 n: 4 3 1 k: 1 9 j: 2 24. P [k] ≺ P [i] ? i: -1 7 k: 0 n: 4 3 1 9 j: 2 27. i ≥ 0 ? i: 0 7 n: 4 3 1 k: 0 9 j: 2 25. k ← i i: -1 1 k: 0 7 7 n: 4 3 1 k: 0 9 j: 2 26. i ← i − 1 n: 4 3 i: -1 9 j: 2 28. P [j ] ↔ P [k] i: -1 1 k: 0 n: 4 3 7 9 j: 1 29. j ← j − 1 54 i: -1 1 n: 4 3 7 k: 0 9 j: 1 30. j > 0 ? i: 0 1 k: 1 n: 4 3 7 9 j: 1 33. P [k] ≺ P [i] ? i: 0 1 n: 4 3 7 k: 1 9 j: 1 31. k ← j, i ← j − 1 i: -1 1 k: 1 n: 4 3 7 9 j: 1 34. i ← i − 1 i: 0 1 n: 4 3 7 k: 1 9 j: 1 32. i ≥ 0 ? i: -1 1 k: 1 n: 4 3 7 9 j: 1 35. i ≥ 0 ? 55 i: -1 1 k: 1 n: 4 3 7 9 j: 1 36. P [j ] ↔ P [k] i: -1 1 k: 1 n: 4 3 7 9 j: 0 37. j ← j − 1 i: -1 1 k: 1 n: 4 3 7 9 j: 0 38. j > 0 ? Время работы алгоритм сортировки прямым выбором практически не зависит от конкретных значений в сортируемой последовательности. Асимп  тотическая сложность алгоритма – Θ n2 . Алгоритм неустойчив. 56 §8. Сортировка подсчётом сравнений Идея алгоритма сортировки подсчётом сравнений: i-тый ключ в окончательно отсортированной последовательности превышает ровно i − 1 остальных ключей. Нужно сравнить попарно все ключи и для каждого отдельного ключа подсчитать, сколько ключей меньше него. 57 1 2 3 4 5 6 7 8 9 10 11 12 13 C o u n t S o r t ( i n ≺ , i n n , out P ) count ← N u l l n j←0 while j < n − 1: i←j+1 while i < n: if i≺j: count[j] ← count[j] + 1 else : count[i] ← count[i] + 1 i←i+1 j ←j+1 P ← ¬count 58 §9. Пирамидальная сортировка Пусть дана последовательность натуральных чисел {ai}n−1 и задано от0 ношение строгого порядка ≺ ⊆ Nn × Nn. Говорят, что элемент a [i] последовательности является корнем пирамиды, если выполняются два условия: 1. 2i + 1 < n ⇒ ¬ (a [i] ≺ a [2i + 1]) ∧ (a [2i + 1] – корень пирамиды); 2. 2i + 2 < n ⇒ ¬ (a [i] ≺ a [2i + 2]) ∧ (a [2i + 2] – корень пирамиды). Пример. (a [2] – корень пирамиды, если ≺ совпадает с порядком на N) a = h1, 5, 7, 2, 3, 6, 7, 9, 7, 4, 8, 4, 5, 6i. Пирамида с корнем a [i] – это подпоследовательность, в которую входит элемент a [i], пирамида с корнем a [2i + 1] (если 2i + 1 < n) и пирамида с корнем a [2i + 2] (если 2i + 2 < n). Для пирамиды с корнем a [i] элементы a [2i + 1] и a [2i + 2] являются корнями левой и правой дочерних подпирамид, соответственно (если эти элементы существуют). 59 Пример. (представление пирамиды в виде дерева) a = h10, 10, 8, 9, 4, 6, 7, 8, 9, 3, 1, 2, 5i h=3 a[0]=10 h=2 h=1 h=0 a[3]=9 a[7]=8 a[8]=9 a[1]=10 a[2]=8 a[4]=4 a[5]=6 a[6]=7 a[11]=2 a[12]=5 a[9]=3 a[10]=1 Высота пирамиды, состоящей из n элементов: blog2 nc. Количество «нелистовых» элементов пирамиды: bn/2c. l m h+1 На любом «этаже» высоты h находится не более n/2 элементов. Здесь bxc и dxe обозначают округление вниз и вверх до ближайшего целого числа. 60 Алгоритм Heapify переупорядочивает элементы последовательности таким образом, чтобы её i-тый элемент являлся корнем пирамиды. Алгоритм работает при условии, что элементы a [2i + 1] и a [2i + 2] уже являются корнями пирамид (если эти элементы существуют). 1 Heapify ( in ≺ , i n i , i n n , i n / out P ) 2 loop : 3 l ← 2i + 1 4 r ←l+1 5 j←i 6 i f l < n and P[i] ≺ P[l] : 7 i←l 8 i f r < n and P[i] ≺ P[r] : 9 i←r 10 if i=j: 11 break 12 P[i] ↔ P[j] На каждой итерации цикла алгоритм спускается на «этаж» ниже. В худшем случае цикл завершается, когда мы оказываемся на нижнем «этаже». Отсюда сложность алгоритма Heapify: O (h), где h – высота пирамиды с корнем в a [i]. 61 Алгоритм BuildHeap проходит по всем элементам, которые могут являться «нелистовыми» элементами пирамиды, снизу вверх и вызывает для них Heapify. 1 2 3 4 5 B u i l d H e a p ( i n ≺ , i n n , i n / out P ) i ← bn/2c − 1 while i ≥ 0: H e a p i f y (≺ , i , n , P ) i←i−1 Верхнюю оценку сложности алгоритма BuildHeap можно записать как   blog n P2 nc O (h). h+1 2 h=0 l m h+1 Действительно, на «этаже» высотой h находятся максимум n/2 эле- ментов, для каждого из которых алгоритм Heapify отрабатывает за время O (h). Высоты «этажей» изменяются от 0 до blog2 nc. То, что в формуле учитываются не только «нелистовые» элементы, не должно нас смущать, так как мы даём верхнюю границу сложности. 62 Упростим выражение для верхней оценки сложности:  blog P2 nc h=0 blog P2 nc n 2h+1  O (h) < blog P2 nc n h+1 h=0 2 · c · h для некоторого c > 0. ∞ h c · n blog c·n P P2 nc h ·c·h= < . h+1 h h 2 2 2 2 2 h=0 h=0 h=0 n Существует формула: ∞ P k=0 kxk = x ( 1 − x) 2 . Она выводится путём дифферен- цирования обоих частей формулы для суммы геометрической прогрессии. ∞ k 1/2 P Подставляя x = 1/2, получаем = = 2. 2 k (1 − 1/2) k=0 2 Тем самым   blog n P2 nc O (h) < c · n. h+1 2 h=0 Получается, что асимптотическая сложность алгоритма BuildHeap: O (n). 63 Основная идея пирамидальной сортировки: 1. преобразуем сортируемую последовательность в пирамиду с помощью BuildHeap, при этом максимальный элемент становится первым; 2. переставляем первый и последний элемент, при этом максимальный элемент попадает на своё место; 3. применяем Heapify для первого элемента последовательности, лишённой последнего элемента, чтобы восстановить пирамиду; 4. повторяем предыдущие два шага до тех пор, пока длина сортируемой последовательности не уменьшится до 1. 1 2 3 4 5 6 7 8 H e a p S o r t ( i n ≺ , i n n , out P ) P ←Idn BuildHeap (≺ , n , P ) i←n−1 while i > 0: P[0] ↔ P[i] H e a p i f y (≺ , 0 , i , P ) i←i−1 Сложность алгоритма: O (n lg n). Алгоритм неустойчивый. 64 §10. Сортировка слиянием Пусть дана последовательность натуральных чисел {ai}n−1 и известно, что подпоследовательности a [k : l] и a [l + 1 : m] отсортированы в соответствии с некоторым отношением строгого порядка ≺ ⊆ Nn × Nn. Пример. (n = 12, отношение ≺ совпадает с порядком на N) 0 , 7, 20, 15 , 2, 3 50, 40, 35, 3, 6, 8, 9 | {z } | {z } a [3 : 6] a [7 : 9] Одна из двух троек помечена «штрихом», чтобы они различались. Необходимо выполнить слияние a [k : l] и a [l + 1 : m], то есть сформировать подпоследовательность a [k : m] таким образом, чтобы она была составлена из элементов a [k : l] и a [l + 1 : m] и при этом устойчиво отсортирована. Пример. (наша последовательность после слияния) 50, 40, 35, |2, 3, 30,{z 6, 7, 8, 9}, 20, 15 a [3 : 9 ] 65 Запишем алгоритм слияния двух подпоследовательностей. Основная идея алгоритма: мы двигаемся сразу вдоль обеих подпоследовательностей, сравниваем их текущие элементы и копируем наименьший во вспомогательную последовательность. 1 Merge ( i n ≺ , i n k , i n l , i n m , i n / out P ) 2 T − в с п о м о г а т е л ь н а я посл −ть р а з м е р а m − k + 1 3 i←k ( с ч ё т ч и к по P[k : l] ) 4 j ←l+1 ( с ч ё т ч и к по P[l + 1 : m] ) 5 h←0 ( с ч ё т ч и к по T ) 6 while h < m − k + 1: 7 i f j ≤ m and ( i = l + 1 o r P[j] ≺ P[i] ) : 8 T [h] ← P[j] 9 j ←j+1 10 else : 11 T [h] ← P[i] 12 i←i+1 13 h←h+1 14 P[k : m] ← T [0 : h − 1] Алгоритм устойчив, так как в случае P [j ] = P [i] срабатывают строки 11..12. Асимптотическая сложность алгоритма: Θ (m − k + 1). 66 Алгоритм сортировки слиянием – рекурсивный. Его основная идея: – разбиваем сортируемую последовательность напополам; – рекурсивно вызываем алгоритм сортировки для каждой половины последовательности; – выполняем слияние получившихся отсортированных подпоследовательностей. 1 2 3 5 6 7 8 9 10 M e r g e S o r t ( i n ≺ , i n n , out P ) P ←Idn MergeSortRec (≺ , 0 , n − 1 , P ) M e r g e S o r t R e c ( i n ≺ , i n low , i n high , i n / out P ) i f low < high : med ← b(low + high) /2c M e r g e S o r t R e c ( ≺ , low , med , P ) M e r g e S o r t R e c ( ≺ , med + 1 , high , P ) Merge ( ≺ , low , med , high , P ) 67 Пусть время работы алгоритма сортировки слиянием в зависимости от длины сортируемой последовательности задаётся функцией T (n). Тогда эта функция определяется рекуррентным соотношением T (n) =  Θ (1) T (bn/2c) + T (dn/2e) + Θ (n) при n = 1, при n > 1. Действительно, при n = 1 алгоритм отрабатывает за константное время, а при n > 1 время его работы складывается из времени двух сортировок последовательностей длины n/2 и времени работы алгоритма слияния, которое линейно зависит от n. Можно доказать, что T (n) = Θ(n log2 n), откуда следует асимптотически точная оценка сложности алгоритма сортировки слиянием: Θ (n lg n). 68 Устойчивость сортировки слиянием следует из устойчивости алгоритма Merge. Достоинства сортировки слиянием по сравнению с пирамидальной сортировкой: 1. устойчивость; 2. хорошо распараллеливается на многоядерных процессорах; 3. лучше использует кэш процессора. Недостаток сортировки слиянием – использование вспомогательного блока памяти размером O (n). 69 §11. Быстрая сортировка Рассмотрим последовательность натуральных чисел {ai}n−1 и некоторое отношение строгого порядка ≺ ⊆ Nn × Nn. Выберем один из элементов последовательности и назовём его опорным элементом. Пусть q элементов последовательности меньше опорного элемента, тогда определим операцию разделения последовательности относительно выбранного опорного элемента как такое переупорядочивание элементов последовательности, что: 1. все элементы из a [0 : q − 1] меньше опорного элемента; 2. элемент a [q ] равен опорному элементу; 3. опорный элемент не превышает ни один из элементов a [q + 1 : n − 1]. Число q назовём границей разделения. Пример. Пусть a = h4, 5, 6, 7, 3, 9, 5i (опорный элемент подчёркнут). Если отношение ≺ совпадает с порядком на N, то результат разделения можно записать как h4, 3, 5, 6, 9, 7, 5i. Возможны и другие варианты разделения, например: h3, 4, 5, 6, 9, 5, 7i. 70 Алгоритм Partition осуществляет разделение подпоследовательности P [low : high] относительно элемента P [high]. Алгоритм возвращает границу разделения. 1 2 3 4 5 6 7 8 9 P a r t i t i o n ( i n ≺ , i n low , i ← low j ← low w h i l e j < high : i f P[j] ≺ P[high] : P[i] ↔ P[j] i←i+1 j ←j+1 P[i] ↔ P[high] i n high , i n / out P ) : i В процессе работы алгоритма переменная i указывает на элемент, левее которого расположены элементы, меньшие опорного. Сложность алгоритма составляет O (high − low). Алгоритм неустойчивый. 71 low: 0 4 7 high: 6 2 9 i: ? 3 1 low: 0 5 4 j: ? 7 high: 6 2 9 i: 0 3 1 low: 0 5 j: 0 4 7 i: 1 high: 6 2 9 3 1 j: 0 3. i ← i + 1 low: 0 5 4 7 i: 1 9 3 1 j: 1 4. j ← j + 1 2 9 1 5 j: 0 low: 0 5 3 2. P [i] ↔ P [j ] high: 6 2 7 i: 0 1. i ← low, j ← low low: 0 4 high: 6 4 7 i: 1 high: 6 2 9 3 1 5 j: 2 5. j ← j + 1 72 low: 0 4 2 high: 6 7 9 i: 1 3 1 low: 0 5 j: 2 low: 0 2 i: 2 9 3 1 j: 4 9. j ← j + 1 7 9 3 1 low: 0 5 low: 0 5 4 2 i: 2 4 j: 2 9 7 7 9 3 1 5 j: 3 8. j ← j + 1 high: 6 3 2 high: 6 i: 2 7. i ← i + 1 high: 6 7 2 i: 2 6. P [i] ↔ P [j ] 4 4 high: 6 1 low: 0 5 j: 4 10. P [i] ↔ P [j ] 4 2 i: 3 high: 6 3 9 7 1 5 j: 4 11. i ← i + 1 73 low: 0 4 2 high: 6 3 9 i: 3 7 1 low: 0 5 j: 5 low: 0 2 i: 4 1 7 9 j: 6 15. j ← j + 1 3 1 7 9 low: 0 5 j: 5 low: 0 5 4 2 i: 4 4 2 i: 4 13. P [i] ↔ P [j ] high: 6 3 2 i: 3 12. j ← j + 1 4 4 high: 6 high: 6 3 1 7 9 5 j: 5 14. i ← i + 1 high: 6 3 1 5 9 7 j: 6 16. P [i] ↔ P [high] 74 Алгоритм быстрой сортировки – рекурсивный. Его основная идея: – выполняем разделение последовательности относительно последнего элемента (этот элемент оказывается на границе разделения и тем самым попадает на своё место в отсортированной последовательности); – рекурсивно вызываем алгоритм сортировки для двух подпоследовательностей, расположенных левее и правее границы разделения. 1 2 3 5 6 7 8 9 Q u i c k S o r t ( i n ≺ , i n n , out P ) P ←Idn QuickSortRec (≺ , 0 , n − 1 , P ) Q u i c k S o r t R e c ( i n ≺ , i n low , i n high , i n / out P ) i f low < high : q ← P a r t i t i o n ( ≺ , low , high , P ) Q u i c k S o r t R e c ( ≺ , low , q − 1 , P ) Q u i c k S o r t R e c ( ≺ , q + 1 , high , P ) 75 Наилучший случай для алгоритма быстрой сортировки – это когда в результате любого разделения граница оказывается посередине разделяемой подпоследовательности. Рекуррентное соотношение для этого случая – такое же, что у сортировки слиянием. Отсюда асимптотическая нижняя граница сложности алгоритма: Ω (n lg n). Наихудший случай – когда в результате любого разделения граница указывает на начало или конец разделяемой подпоследовательности. В этом случае осмысленные действия выполняются только в одном из двух рекурсивных вызовов. Причём на каждом запуске функции сортировки сортируемая последовательность уменьшается на один элемент.   Отсюда асимптотическая верхняя граница сложности алгоритма: O n2 . На практике оказывается, что в среднем алгоритм тяготеет к нижней границе сложности. 76 §12. Сортировка за линейное время Пускай ключами записей сортируемой последовательности являются натуральные числа из Nm. Зададим функцию, отображающую множество записей R в множество ключей: key : R → Nm. Поставим задачу сортировки последовательности записей n−1 S = {si}0 следующим образом: требуется построить такую последовательность n−1 D = {di}0 , что она составлена из элементов S и, кроме того,
key (d0) ≤ key (d1) ≤ . . . ≤ key dn−1 . Замечание. Такая постановка задачи отличается от классической тем, что алгоритм сортировки имеет доступ к записям и их ключам. 77 Алгоритм сортировки распределением копирует записи из исходной последовательности в новую отсортированную последовательность. Идея алгоритма: – для каждого ключа подсчитываем количество записей, которым он соответствует; – для каждого ключа вычисляем индекс элемента в отсортированной последовательности, непосредственно перед которым может располагаться последняя запись, соответствующая этому ключу; – копируем каждую запись исходной последовательности в нужное место результирующей последовательности. Пример. (сортируем целые числа по возрастанию младшего разряда) h12, 4, 51, 42, 11, 31, 54,+32, 50i – исходная последовательность; * 0 1 2 3 4 5 6 7 8 9 1, 3, 3, 0, 2, 0, 0, 0, 0, 0 * 0 1 2 3 4 5 6 7 8 9 – количество записей для каждого ключа; + 1, 4, 7, 7, 9, 9, 9, 9, 9, 9 – индекс для каждого ключа; h50, 51, 11, 31, 12, 42, 32, 4, 54i – отсортированная последовательность. 78 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 D i s t r i b u t i o n S o r t ( i n key , i n m , i n S , i n n ) : D count ← N u l l m j←0 while j < n: k ← key(S[j]) count[k] ← count[k] + 1 j ←j+1 i←1 while i < m: count[i] ← count[i] + count[i − 1] i←i+1 D ← н о в а я п о с л е д о в а т е л ь н о с т ь з а п и с е й длины n j ←n−1 while j ≥ 0: k ← key(S[j]) i ← count[k] − 1 count[k] ← i D[i] ← S[j] j ←j−1 79 Очевидно, что сортировка распределением выполняется за время Θ (2n + m) что даёт Θ (n) в случае, когда m  n. Размер дополнительной памяти, требуемой сортировкой распределением: Θ (m + n). Благодаря тому, что в строках 14..19 исходная последовательность просматривается из конца в начало, и при этом диапазоны отсортированной последовательности, соответствующие одному ключу, заполняются также из конца в начало, алгоритм сортировки распределением – устойчивый. Сортировка распределением хорошо работает только в случае, когда множество ключей невелико. 80 В случае, если множество ключей велико, применяют следующий приём: записывают каждый ключ в системе счисления по основанию m и подвергают последовательность нескольким сортировкам распределением по каждому разряду ключа, начиная с младшего. Пример. (m = 10) 115 20 0 073 10 0 015 11 2 313 ⇒ 07 3 ⇒ 200 31 3 100 11 5 075 01 5 112 07 5 2 00 015 1 00 073 1 12 075 3 13 ⇒ 100 1 15 112 0 15 115 0 73 200 0 75 313 Этот метод называется поразрядной сортировкой. Он работает благодаря тому, что сортировка распределением – устойчивая. 81 Пусть в системе счисления по основанию m каждый ключ представлен D E кортежем a0, a1, . . . , aq−1 , где ai ∈ Nm. Зададим функцию, возвращающую нужный разряд ключа: keys : Nq → (R → Nm). Тогда алгоритм поразрядной сортировки можно записать как 1 2 3 4 5 6 R a d i x S o r t ( i n keys , i n q , i n m , i n S , i n n ) : D D←S i←q−1 while i ≥ 0: D ← D i s t r i b u t i o n S o r t ( keys(i) , m , D , n ) i←i−1 Алгоритм, очевидно, устойчив, и выполняется за время Θ (n). Замечание. Алгоритм можно без труда обобщить для случая, когда основание системы счисления различается у разных разрядов. 82 §13. Постановка задачи поиска подстроки Строка – это последовательность, элементы которой принадлежат конечному множеству, называемому алфавитом. Без потери общности можно считать, что алфавитом является конечное подмножество N. Отсюда строка – последовательность натуральных чисел. Если дана строка S, то – её i-тый элемент мы будем обозначать как S [i]; – длину строки – как len(S); – подстроку hS [j ] , S [j + 1] , . . . , S [k]i – как S [j : k]. Поиск подстроки S в строке T заключается в нахождении минимального k такого, что T [k : k + len (S ) − 1] = S (первое вхождение S в T ). В случае, если это равенство не выполняется ни для какого k, положим k = len (T ). 83 Наивный алгоритм поиска подстроки в строке: 1 2 3 4 5 6 7 B r u t e F o r c e S u b s t ( i n S , i n T , out k ) k←0 w h i l e k < len(T ) − len(S) + 1 : i f T [k : k + len(S) − 1] = S : return k ←k+1 k ← len(T ) Так как операция сравнения подстрок работает за время O (len (S )), то сложность алгоритма составляет O ((len (T ) − len (S ) + 1) · len (S )). Наихудший случай: T = aaaaaa . . . a, S = aaaa . . . ab. Достоинством алгоритма является то, что в нём как «чёрный ящик» используется операция сравнения подстрок, которая допускает эффективную реализацию на ассемблере. (При реализации на языке C эта операция кодируется как вызов функции memcmp.) 84 §14. Префиксная функция Префикс длины k строки S – это подстрока S [0 : k − 1]. Суффикс длины k строки S – это подстрока S [len (S ) − k : len (S ) − 1]. При этом, если k < len (S ), то префикс и суффикс – собственные. В приложении к поиску подстроки в строке нас будут интересовать строки, у которых собственный префикс совпадает с суффиксом. Пример. abra | {z }cad abra | {z }. k=4 Для общности будем полагать, что у любой строки префикс нулевой длины совпадает с суффиксом. 85 Пусть S – строка. Обозначим через l(S) самый длинный собственный префикс S, совпадающий с суффиксом S. Утверждение. l (l (S )) совпадает с некоторым суффиксом S. Данное утверждение иллюстрирует схема: S=• • • •} • • • • • • •} • • • • • • •} • • •} • • • • | • {z | • {z | • {z | • {z l(l(S)) | l(l(S)) {z l(S) l(l(S)) } | l(l(S)) {z l(S) } Действительно, в начале и в конце строки S располагается подстрока l(S), а в начале и в конце строки l(S) располагается подстрока l (l (S )). Следовательно, l (l (S )) располагается в начале и в конце строки S. Утверждение естественно распространяется и на l (l (l (S ))) и т.д. 86 Утверждение. Не существует префикса строки S, который бы совпадал с её суффиксом и был бы короче l (S ), но длиннее l (l (S )). Предположим, что такой суффикс x существует. Получившуюся ситуацию иллюстрирует схема: S=• • • •} • • • • • • • • • • • • • • • • • • • • • • • |• • {z • • •} | • {z | | l(l(S)) {z x | } {z l(S) } | {z l(S) l(l(S)) {z } x } Из схемы понятно, что x располагается в начале и в конце l (S ), что невозможно, потому что l (l (S )) – самый длинный собственный префикс l (S ), совпадающий с её суффиксом. 87 Префиксная функция для строки S – это функция π : Nlen(S)−1 −→ Nlen(S)−1 такая, что π (i) равно длине l (S [0 : i]). Пример. S= π= a b r a 1 c a 1 d a 1 b 2 r 3 a 4 Наивный алгоритм для вычисления префиксной функции: 1 BruteForcePrefix ( in S ): π 2 π ← н о в а я п о с л е д о в а т е л ь н о с т ь н а т . ч и с е л длины len(S) 3 π[0] ← 0 4 i←1 5 w h i l e i < len(S) : 6 k←i 7 w h i l e k > 0 and S[0 : k − 1] 6= S[i − k + 1 : i] : 8 k ←k−1 9 π[i] ← k 10 i←i+1   3 Сложность алгоритма – O (len (S )) . 88 Обозначения. Если A – строка, x – символ алфавита, то Ax – строка, полученная из A путём добавления к ней справа символа x. Если A и B – строки, то AB – результат их конкатенации. Пускай префиксная функция π построена для некоторой строки S длины n, и x – символ алфавита. Можем ли мы быстро посчитать l (Sx)? Пусть y1 = S [π (n − 1)] – первый символ строки S, следующий за префиксом l (S ). Очевидно, что если y1 = x, то l (Sx) = l (S ) x. π(n−1) n y1 • • • • • • • • • • • • • • • • • • x. | {z } l(S) Sx = • • • • • • • • •} | • • • • • • {z l(S) Если y1 6= x, то рассмотрим следующий по длине префикс строки S, совпадающий с её суффиксом: l (l (S )). Sx = • • • • •} | • • {z l(l(S)) | π(n−1) π(π(n−1)−1) n y2 • • • • • •• • • • •• • • • • • • • |• • • {z • • • •}x. l(l(S)) | {z } {z } l(S) l(S) Если y2 = π (π (n − 1) − 1) = x, то l (Sx) = l (l (S )) x. (И так далее.) 89 Основная идея алгоритма построения префиксной функции: – пусть π (0) = 0, тем самым мы построили префиксную функцию для подстроки S [0 : 0]; – на каждом шаге имеем построенную префиксную функцию для S [0 : i − 1] и вычисляем π (i) по приведённой на предыдущем слайде схеме. 1 2 3 4 5 6 7 8 9 10 11 Prefix ( in S ): π π ← н о в а я п о с л е д о в а т е л ь н о с т ь н а т . ч и с е л длины len(S) π[0] ← t ← 0 i←1 w h i l e i < len(S) : w h i l e t > 0 and S[t] 6= S[i] : t ← π[t − 1] i f S[t] = S[i] : t←t+1 π[i] ← t i←i+1 Переменная t в начале каждой итерации внешнего цикла равна π (i − 1), а в конце каждой итерации равна π (i). 90 t: ? i: ? t: 0 i: ? t: 0 i: 1 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2. i ← 1 1. π [0] ← t ← 0 t: 0 i: 1 t: 0 i: 2 t: 1 i: 2 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3. π [i] ← t 4. i ← i + 1 5. t ← t + 1 91 t: 1 i: 2 t: 1 i: 3 t: 2 i: 3 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b 1 ? ? ? ? ? ? ? ? 1 ? ? ? ? ? ? ? ? 1 ? ? ? ? ? ? ? ? 7. i ← i + 1 6. π [i] ← t t: 2 i: 3 t: 2 8. t ← t + 1 i: 4 t: 0 i: 4 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b 1 2 ? ? ? ? ? ? ? 1 2 ? ? ? ? ? ? ? 1 2 ? ? ? ? ? ? ? 9. π [i] ← t 10. i ← i + 1 11. t ← π [t − 1] 92 t: 0 t: 0 i: 4 i: 5 t: 1 i: 5 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b 1 2 ? ? ? ? ? ? 1 2 ? ? ? ? ? ? 1 2 ? ? ? ? ? ? 13. i ← i + 1 12. π [i] ← t t: 1 i: 5 t: 1 14. t ← t + 1 i: 6 t: 2 i: 6 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b 1 2 1 ? ? ? ? ? 1 2 1 ? ? ? ? ? 1 2 1 ? ? ? ? ? 15. π [i] ← t 16. i ← i + 1 17. t ← t + 1 93 t: 2 i: 6 t: 2 i: 7 t: 3 i: 7 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b 1 2 1 2 ? ? ? ? 1 2 1 2 ? ? ? ? 1 2 1 2 ? ? ? ? 19. i ← i + 1 18. π [i] ← t t: 3 i: 7 t: 3 20. t ← t + 1 i: 8 t: 4 i: 8 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b 1 2 1 2 3 ? ? ? 1 2 1 2 3 ? ? ? 1 2 1 2 3 ? ? ? 21. π [i] ← t 22. i ← i + 1 23. t ← t + 1 94 t: 4 i: 8 t: 4 i: 9 t: 2 i: 9 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b 1 2 1 2 3 4 ? ? 1 2 1 2 3 4 ? ? 1 2 1 2 3 4 ? ? 25. i ← i + 1 24. π [i] ← t t: 3 i: 9 t: 3 26. t ← π [t − 1] i: 9 t: 3 i: 10 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b 1 2 1 2 3 4 ? ? 1 2 1 2 3 4 3 ? 1 2 1 2 3 4 3 ? 27. t ← t + 1 28. π [i] ← t 29. i ← i + 1 95 t: 4 i: 10 t: 4 i: 10 t: 4 i: 11 a b a b c a b a b a b a b a b c a b a b a b a b a b c a b a b a b 1 2 1 2 3 4 3 ? 1 2 1 2 3 4 3 4 1 2 1 2 3 4 3 4 30. t ← t + 1 31. π [i] ← t 32. i ← i + 1 Чтобы оценить время работы алгоритма, воспользуемся следующими соображениями: 1. внешний цикл выполняется n − 1 раз, где n = len (S ); 2. изначально t = 0; 3. на каждой итерации внешнего цикла t может увеличиться не более, чем на единицу (строка 8), поэтому максимальное значение, которого может достигнуть t – это n − 1; 4. во внутреннем цикле t только уменьшается (строка 6), но не может стать меньше нуля, поэтому общее количество итераций внутреннего цикла за всё время работы алгоритма не может превышать n − 1. Отсюда, сложность алгоритма: O (n). 96 §15. Алгоритм Кнута-Морриса-Пратта Основная идея алгоритма: 1. формируется строка Q=S#T , где S – искомая подстрока, T – строка, в которой осуществляется поиск, а # – служебный символ, который гарантированно не встречается ни в S, ни в T ; 2. для строки Q выполняется построение префиксной функции π; 3. участок T префиксной функции сканируется для обнаружения позиции k такой, что π (k) = len (S ); тем самым k будет равно индексу последнего символа первого вхождения подстроки S в строку T . len(S) len(Q)−1 k ↓ ↓ ↓ ↓ • • • •} • • • • • • • • Q=◦ ◦ ◦ ◦ ◦} # • • • • • | • • {z | ◦ ◦ {z S S {z | } T 97 Значения префиксной функции на Q = S#T не могут превышать len (S ), потому что символ # – уникальный. Поэтому алгоритм Кнута-МоррисаПратта строит только π [0 : len (S ) − 1] и вычисляет значения π на участке T , не сохраняя их в массиве: 1 2 3 4 5 6 7 8 9 10 11 12 13 KMPSubst ( i n S , i n T , out k ) π ← P r e f i x (S ) q←0 k←0 w h i l e k < len(T ) : w h i l e q > 0 and S[q] 6= T [k] : q ← π[q − 1] i f S[q] = T [k] : q ←q+1 i f q = len(S) : k ← k − len(S) + 1 return k ←k+1 Так как для построения π [0 : len (S ) − 1] достаточно выполнить Prefix(S), алгоритм вообще обходится без построения строки Q=S#T . 98 k: ? T: a a k: ? c a a a b c d T: a a k: 0 c a a a b c d T: a a c a pi: ? ? ? pi: 1 pi: 1 S: a a b S: a a b S: a a b q: ? q: ? T: a a a a a b c d T: a a c a a a b c d T: a a c a 1 pi: 1 pi: 1 S: a a b S: a a b S: a a b 3. q ← q + 1 c d b c d k: 1 pi: q: 1 b 2. q ← 0, k ← 0 k: 1 c a q: 0 1. π ←Prefix(S) k: 0 a q: 1 4. k ← k + 1 a a q: 2 5. q ← q + 1 99 k: 2 T: a a k: 2 c a a a b c d T: a a k: 2 c a a a b c d T: a a c a pi: 1 pi: 1 pi: 1 S: a a b S: a a b S: a a b q: 2 q: 1 6. k ← k + 1 T: a a a a a b c d T: a a c a a a b c d T: a a c a 1 pi: 1 pi: 1 S: a a b S: a a b S: a a b 9. k ← k + 1 c d a b c d k: 4 pi: q: 0 b 8. q ← π [q − 1] k: 3 c a q: 0 7. q ← π [q − 1] k: 3 a q: 1 10. q ← q + 1 a q: 1 11. k ← k + 1 100 k: 5 k: 4 T: a a c a a a b c d T: a a k: 5 c a a a b c d T: a a c a pi: 1 pi: 1 pi: 1 S: a a b S: a a b S: a a b q: 2 q: 2 12. q ← q + 1 T: a a a a a b c d T: a a c a a a b c d T: a a c a 1 pi: 1 pi: 1 S: a a b S: a a b S: a a b 15. q ← q + 1 c d b c d k: 6 pi: q: 2 b 14. q ← π [q − 1] k: 6 c a q: 1 13. k ← k + 1 k: 5 a q: 2 16. k ← k + 1 a a q: 3 17. q ← q + 1 101 k: 4 T: a a c a pi: 1 S: a a b a a b c d q: 3 18. k ← k − len (S ) + 1 Очевидно, что сложность алгоритма Кнута-Морриса-Пратта: O (m + n), где m = len (S ), n = len (T ). 102 §16. Упрощённый алгоритм Бойера-Мура Работу некоторых алгоритмов поиска подстроки в строке, включая наивный алгоритм и алгоритм Бойера-Мура, можно описать как процесс сдвига искомой подстроки S вдоль строки T . Пример. (наивный алгоритм) 0 1 2 3 4 5 6 7 8 9 ... T = a b b a d a b a c b ... S = hbi a b a c → b hai b a c → b a hbi a c → hbi a b a c . . . (Жирным шрифтом выделены символы, участвовавшие в сравнении; символы в скобках – места неудачных сравнений.) В наивном алгоритме подстрока S всегда сдвигается на одну позицию вправо, и её сравнение с символами строки T выполняется слева направо. 103 На каждом шаге алгоритма Бойера-Мура строка S сопоставляется с некоторым участком строки T и сканируется справа налево. В процессе сканирования текущий символ строки S сравнивается с текущим символом строки T . k ↓ ← ← ← T = ... • • • • x ◦ ◦ ◦ • ... S= • • • • ◦ ◦ ◦ ↑ ← ← ← i (◦ – обозначение для символа, уже участвовавшего в сравнении, а • – обозначение ещё не рассмотренного символа) Эвристика – это приём в поиске решения задачи, позволяющий ограничить перебор. Алгоритм Бойера-Мура использует ряд эвристик, позволяющих сдвигать S вдоль T сразу на несколько позиций. 104 Эвристика стоп-символа. Встретив в строке T символ x = T [k] такой, что x 6= S [i], мы можем расположить строку S относительно строки T так, что последнее вхождение x в S окажется напротив T [k]. k ↓ T = ... • • • • x ◦ ◦ ◦ • • ... S= • x • • ◦ ◦ ◦ ↑ i → • x ⊗ ⊗ ⊗ ⊗ ⊗ (⊗ обозначает символ, гарантированно не равный x) В частном случае, когда x вообще не входит в S, строку S можно расположить так, чтобы S [0] оказался напротив T [k + 1]. Символ x будем называть стоп-символом. 105 Пример. (T T = a S= b [3] = b – стоп-символ) 1 2 3 4 5 6 7 8 9 ... b b b a a b a c b ... b a hci a → b b a c a . . . Пример. (T [4] = d – стоп-символ) 0 1 2 3 4 5 6 7 8 9 ... T = a b b a d a b a c b ... S = b a b a hci a → b a b a c a . . . Уже сейчас понятно, что в наилучшем случае алгоритм Бойера-Мура сработает за время O (n/m), где n = len (T ), m = len (S ). 106 Эвристика стоп-символа вовсе не всегда даёт положительный сдвиг: Пример. (T [2] = a – 0 1 2 T = a b a S= c a hbi c a b a стоп-символ) 3 4 5 6 7 8 9 ... a b a b a c b ... a b b ← . . . Пусть S [j ] = x – самое правое вхождение стоп-символа T [k] = x в строку S. Тогда для того чтобы расположить строку S относительно строки T так, чтобы S [j ] располагался напротив T [k], нужно, чтобы последний символ строки [S ] располагался напротив T [k2], где k2 = k + (len (S ) − j ) − 1. k ↓ k2 ↓ T = ... • • • •x ◦ • • • • • • ... S= •x • • ◦ ◦ ↑ j ↑ i len(S)−j z }| { •x•••• 107 Для быстрого применения эвристики стоп-символа алгоритм Бойера-Мура использует таблицу стоп-символов δ1, которая строится следующим алгоритмом: 1 2 3 4 5 6 7 8 9 10 D e l t a 1 ( i n S , i n size ) : δ1 δ1 ← н о в а я п о с л е д о в а т е л ь н о с т ь a←0 w h i l e a < size : δ1[a] ← len(S) a←a+1 j←0 w h i l e j < len(S) : δ1[S[j]] ← len(S) − j − 1 j ←j+1 р а з м е р а size Параметр size задаёт размер алфавита. Мы будем считать алфавитом множество Nsize. Элементы таблицы стоп-символов, соответствующие символам, не входящим в S, равны len (S ). 108 Запишем упрощённый алгоритм Бойера-Мура, использующий только эвристику стоп-символа: 1 2 3 4 5 6 7 8 9 10 11 12 S i m p l e B M S u b s t ( i n S , i n size , i n T , out k ) δ1 ← D e l t a 1 ( S , size ) k ← len(S) − 1 w h i l e k < len(T ) : i ← len(S) − 1 w h i l e T [k] = S[i] : if i = 0: return i←i−1 k ←k−1 k ← k+max ( δ1[T [k]] , len(S) − i ) k ← len(T ) В настоящем алгоритме Бойера-Мура используется ещё и так называемая эвристика совпавшего суффикса, которую мы рассмотрим в следующих параграфах. 109 Пример. (работа алгоритма) T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t 110 §17. Полный алгоритм Бойера-Мура Определение префиксной функции «π (i) равно длине l (S [0 : i])» можно переформулировать следующим образом: π (i) равно индексу элемента строки, левее которого расположен самый длинный собственный префикс строки S, равный суффиксу подстроки S [0 : i]. Аналогично можно дать определение суффиксной функции σ : Nlen(S)−1 −→ Nlen(S)−1: σ (i) равно индексу элемента строки, правее которого расположен самый длинный собственный суффикс строки S, равный префиксу подстроки S [i : len (S ) − 1]. Пример. S= σ= a 6 1 b 7 2 r 8 3 a 9 4 c 10 5 a 9 6 d 10 7 a 9 8 b 10 9 r 10 10 a 10 111 Алгоритм построения суффиксной функции аналогичен алгоритму Prefix и записывается как: 1 2 3 4 5 6 7 8 9 10 11 Suf fix ( in S ): σ σ ← н о в а я п о с л е д о в а т е л ь н о с т ь н а т . ч и с е л длины len(S) σ[len(S) − 1] ← t ← len(S) − 1 i ← len(S) − 2 while i ≥ 0: w h i l e t < len(S) − 1 and S[t] 6= S[i] : t ← σ[t + 1] i f S[t] = S[i] : t←t−1 σ[i] ← t i←i−1 112 Подстрока occ = S [j : j + m − 1] называется правдоподобным вхождением суффикса suf = S [len (S ) − m : len (S ) − 1] в S, если occ = suf , j > 0 и S [j − 1] 6= S [len (S ) − m − 1]. Пример. ababab – нет правдоподобных вхождений суффиксов. Пример. abc |{z} ab dab – одно правдоподобное вхождение суффикса ab. Пример. c |{z} ab d |{z} ab ab – несколько правдоподобных вхождений суффикса ab. 113 Эвристика совпавшего суффикса. Если при сопоставлении строки S с очередным участком строки T суффикс S [i : len(S) − 1] совпал с подстрокой T [k : k + (len (S ) − i) − 1], то возможны два случая: Случай 1. S [j ] – начало самого правого правдоподобного вхождения совпавшего суффикса в S; k ↓ T = • • • • • • S= • • ◦ ◦ ◦ ↑ j • • • ◦ ◦ ◦ ◦ • • • • • • • • • • • ... • h◦i ◦ ◦ ◦ ↑ i → • • ◦ ◦ ◦ • • • ◦ ◦ ◦ k ← k − j + len (S ) Очевидно, k увеличивается не менее, чем на len (S ) − i. Пример. (случай 1: k 0 1 2 3 T = a b a a S = c a hbi a → c a ← 2 − 1 + 5 = 6) 4 5 6 7 8 9 ... b a b a c b ... b b a b . . . 114 Случай 2. не существует правдоподобного вхождения совпавшего суффикса в строке S, но имеется собственный суффикс S [j + 1 : len(S) − 1] совпавшего суффикса, равный префиксу строки S: k ↓ T = • • • • • • • ◦ ◦ S= ? ? • • • h◦i ◦ ↑ i ◦ ◦ ? ? • • • • • • • • • • ... ? ? ↑ j → ? ? • • • • ◦ ◦ ? ? k ← k − i + j + len (S ) Очевидно, k увеличивается не менее, чем на len (S ) − i. Пример. (случай 2: k ← 4 − 4 + 5 + 9 = 14) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 . . . T = a b c a a c a b c a b c a b c ... S = a b c a hbi c a b c → a b c a b c a b c . . . 115 Для быстрого применения эвристики совпавшего суффикса алгоритм Бойера-Мура использует таблицу δ2, которая строится следующим алгоритмом: 1 D e l t a 2 ( i n S ) : δ2 2 δ2 ← н о в а я п о с л е д о в а т е л ь н о с т ь р а з м е р а len(S) 3 σ ← S u f f i x (S ) 4 i←0 5 t ← σ[0] 6 w h i l e i < len(S) : 7 while t < i: 8 t ← σ[t + 1] 9 δ2[i] ← −i + t + len(S) −− случай 2 10 i←i+1 11 i←0 12 w h i l e i < len(S) − 1 : 13 t←i 14 w h i l e t < len(S) − 1 : 15 t ← σ[t + 1] 16 i f S[i] 6= S[t] : 17 δ2[t] ← −(i + 1) + len(S) −− случай 1 18 i←i+1 116 Замечание. Алгоритм Delta2 гарантирует, что для любого i от 0 до len(S) − 1 справедливо, что δ2 [i] ≥ len (S ) − i. Пример. (вычисление δ2 для строки «abcabdab») Суффиксная функция (строка 3): 1 1 1 2 3 4 5 2 3 4 2 3 4 5 b 9 d 5 6 S= a b c a b d a σ= 5 6 7 5 6 7 7 После первого цикла (строки 6..10): 5 7 b 7 6 7 6 7 a c a a S= b b d b δ2 = 13 12 11 10 9 8 9 8 После третьего цикла (строки 12..17): S= a δ2 = 13 b 12 c 11 a 10 a 9 b 1 117 Полный алгоритм Бойера-Мура отличается от упрощённого использованием таблицы δ2: 1 2 3 4 5 6 7 8 9 10 11 12 13 BMSubst ( i n S , i n size , i n T , out k ) δ1 ← D e l t a 1 ( S , size ) δ2 ← D e l t a 2 ( S ) k ← len(S) − 1 w h i l e k < len(T ) : i ← len(S) − 1 w h i l e T [k] = S[i] : if i = 0: return i←i−1 k ←k−1 k ← k+max ( δ1[T [k]] , δ2[i] ) k ← len(T ) В строке 12 строка S сдвигается относительно строки T не менее, чем на одну позицию вправо, так как δ2 [i] ≥ len (S ) − i. 118 Пример. (работа алгоритма) T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t −−−−−−−− э в р и с т и к а стоп −с и м в о л а −−−−−−− T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t −−−−−−−− э в р и с т и к а стоп −с и м в о л а −−−−−−− T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t −−−−−−−− э в р и с т и к а стоп −с и м в о л а −−−−−−− T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t −−−− э в р и с т и к а с о в п а в ш е г о суффикса −−−− T = which ‘ f i n a l l y ‘ h a l t s ‘ ‘ ‘ at ‘ that ‘ p o i n t S = at ‘ t h a t 119 §18. Дерево отрезков Пусть дана последовательность значений {vi ∈ V }n−1 и некоторая бинар0 ная операция + : V × V −→ V , обладающая свойством ассоциативности: (x + y ) + z = x + (y + z ). Требуется уметь многократно вычислять значения r P i=l vi = vl + vl+1 + . . . + vr на разных интервалах от l до r. При этом последовательность не является фиксированной, т.е. время от времени значения её элементов могут изменяться. Пример. Дана последовательность целых чисел. Требуется вычислять суммы чисел на разных интервалах или требуется находить максимальное число на разных интервалах. 120 Мы будем называть отрезком от a до b и обозначать как [a : b] значение b P vi, вычисленное на последовательности {vi}n−1 . i=a Дерево отрезков – это множество отрезков, построенное по следующим правилам: 1. в множестве содержится отрезок [0 : n − 1], который называется корнем дерева; 2. если множеству принадлежит отрезок [a : b], и a 6= b, то множеству  a+b ; при также принадлежат отрезки [a : m] и [m + 1 : b], где m = 2 этом отрезки [a : m] и [m + 1 : b] называются дочерними по отношению к отрезку [a : b]; 3. никаких других отрезков в множестве нет. Отрезок [a : b] в дереве T мы будем обозначать как T [a : b]. 121 Пример. (дерево отрезков для последовательности натуральных чисел h2, 3, 5, 1, 0, 4, 7, 6, 2, 4i с операцией сложения) [0:9]=33 [0:2]=10 [0:1]=5 [0:0]=2 [2:2]=5 [1:1]=3 [3:3]=1 [0:4]=11 [5:9]=22 [3:4]=1 [5:7]=17 [4:4]=0 [5:6]=11 [5:5]=4 [8:9]=5 [7:7]=6 [8:8]=2 [9:9]=3 [6:6]=7 122 1 2 4 5 6 7 8 9 10 11 12 13 14 15 SegmentTree_Query ( i n T , i n n , v ←query (T , l , r , 0 , n − 1) query ( in T , in l , in r , i f l = a and r = b : v ← T [a, b] else :   a+b m← 2 if r ≤ m: v ←query (T , else i f l > m: v ←query (T , else : v ←query (T , query (T , in a , in l , in r ): v in b): v l , r , a , m) l , r , m + 1 , b) l , m , a , m) + m + 1 , r , m + 1 , b) 123 1 2 3 5 6 7 8 9 10 11 12 S e g m e n t T r e e _ B u i l d ( i n {vi}n−1 , out T ) T ←новое дерево отрезков b u i l d ( {vi}n−1 , 0, n−1, T) b u i l d ( i n {vi}n−1 , i n a , i n b , i n / out T ) if a = b: T [a : b] ← va else :   a+b m← 2 b u i l d ( {vi}n−1 , a, m, T) b u i l d ( {vi}n−1 , m+1, b, T) T [a : b] ← T [a : m] + T [m + 1, b] 124 1 2 4 5 6 7 8 9 10 11 12 13 SegmentTree_Update ( i n i , i n v , update (i , v , 0 , n − 1 , T ) in n , i n / out T ) u p d a t e ( i n i , i n v , i n a , i n b , i n / out T ) if a = b: T [a : b] ← v else :   a+b m← 2 if i ≤ m: update (i , v , a , m , T ) else : update (i , v , m + 1 , b , T ) T [a : b] ← T [a : m] + T [m + 1, b] 125 §19. Дерево Фенвика Изменим постановку задачи посчёта сумм на отрезках последовательности {vi ∈ V }n−1 следующим образом: пусть операция + : V × V −→ V не только ассоциативна, но и коммутативна и, более того, обратима, т.е. существует операция − : V × V −→ V такая, то (a + b = c) ⇒ (b = c − a). В этом случае можно применить более компактную структуру данных, чем дерево отрезков. Она называется бинарным индексированным деревом или деревом Фенвика. Дерево Фенвика представляет собой массив T размера n такой, что T [ i] = i P vj . j=f (i) Здесь f (i) = i − 2h(i) + 1, где h (i) – количество единиц в конце двоичной записи числа i. Можно показать, что f (i) = i& (i + 1). 126 Запрос к дереву Фенвика – O (lg n): 1 2 4 5 6 7 8 FenwickTree_Query ( i n T , i n l , i n r ) : v v ←query (T , r) − query (T , l − 1) query ( in T , in i ) : v v←0 while i ≥ 0: v ← v + T [i] i ← (i&(i + 1)) − 1 Обновление дерева Фенвика – O (lg n): 1 2 3 4 FenwickTree_Update ( i n i , while i < n: T [i] ← T [i] + δ i ← i|(i + 1) in δ , i n / out T ) 127 Построение дерева Фенвика – O (n): 1 2 3 4 6 7 8 9 10 11 12 13 14 15 F e n w i c k T r e e _ B u i l d ( i n {vi}n−1 , out T ) T ←новое дерево отрезков r ←минимальная с т е п е н ь 2 , н е меньшая , b u i l d ( {vi}n−1 , 0, r−1, T) чем n b u i l d ( i n {vi}n−1 , i n l , i n r , i n / out T ) : sum sum ← 0 bound ←min ( r , n ) w h i l e l < bound :   l+r m← 2 n−1 sum ← sum+ b u i l d ( {vi}0 , l, m, T) l ←m+1 if r < n: sum ← sum + vr T [r] ← sum 128 §20. Разреженная таблица Пусть дана последовательность значений {vi ∈ V }n−1 и некоторая бинар0 ная операция min : V × V −→ V , обладающая двумя свойствами: 1. ассоциативность: min (min (x, y ) , z ) = min (x, min (y, z )); 2. идемпотентность: min (x, x) = x. Требуется уметь многократно вычислять значения r  
min vi = min vl , min vl+1, . . . min vr−1, vr . . .  i=l на разных интервалах от l до r. 129 Разреженная таблица – это матрица ST размером n × (blog2 nc + 1) такая, i+2j −1 что ST [i, j ] = min vk . k=i Здесь i = 0, n − 1, j = 0, blog2 nc, причём i + 2j − 1 < n. Другими словами, j-тый столбец таблицы хранит минимумы всех отрезков, длины которых равны 2j . Причём в конце каждого столбца имеется 2j − 1 незаполненных элементов. Построение разреженной таблицы выполняется следующим образом: 1. заполнение нулевого столбца: ST [i, 0] = vi. 2. заполнение каждого следующего (j-того)столбца:  ST [i, j ] = min ST [i, j − 1], ST [i + 2j−1, j − 1 . Запросы к разреженной таблице выполняются за одно действие: r   j min vi = min ST [l, j], ST [r − 2 + 1, j] , где j = blog2 (r − l + 1)c. i=l 130 Для эффективной работы разреженной таблицы требуется уметь быстро считать логарифмы. Удобнее всего заранее заполнить таблицу логарифмов для всех возможных длин отрезков: 1 2 3 4 5 6 7 8 C o m p u t e L o g a r i t h m s ( i n m , out lg ) lg ←новый м а с с и в целых ч и с е л р а з м е р а 2m i←1, j ←0 while i < m: w h i l e j < 2i : lg[j] ← i − 1 j ←j+1 i←i+1 Запрос к разреженной таблице – O (1): 1 2 3 S p a r s e T a b l e _ Q u e r y ( i n ST , i n l , j ← lg[r − l + 1] v ←min ( ST [l, j] , ST [r − 2j + 1, j] ) in r , i n lg ) : v 131 Построение разреженной таблицы – O (n lg n): 1 2 3 5 6 7 8 10 11 12 13 14 15 16 S p a r s e T a b l e _ B u i l d ( i n {vi}n−1 , i n lg , out ST ) m ← lg[n] + 1 ST ← н о в а я матрица размером n × m i←0 while i < n: ST [i, 0] ← vi i←i+1 j←1 while j < m: i←0 w h i l e i ≤ n − 2j : ST [i, j] =min ( ST [i, j − 1] , ST [i + 2j−1, j − 1] ) i←i+1 j ←j+1 132 §21. Алгоритм Кадана Пусть дана последовательность целых чисел {ai}n−1 . Требуется найти r P ai – максимальна. такие индексы l и r, что сумма i=l 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Kadane ( i n {ai}n−1 , out l , out r ) l ← 0 , r ← 0 , maxsum ← a0 start ← 0 , sum ← 0 i←0 while i < n: sum ← sum + ai i f sum > maxsum : maxsum ← sum l ← start r←i i←i+1 i f sum < 0 : sum ← 0 start ← i 133