Весь массив просмотрен и совпадения не обнаружено.

Это дает нам линейный алгоритм:

i: = 1;

WHILE (i < = N) and (a[i] <> x) DO i: = i + 1; (5.1)

Обратите внимание, что порядок элементов в логическом выражении имеет существенное значение. Инвариант цикла, т.е. условие, выполняющееся перед каждым увеличением индекса i, выглядит так:

(1 ≤ i ≤ N) & (A k: 1 ≤ k < i: a_k ≠ x) (5.2)

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

((i = N + 1) OR (а_i = х)) & (A k: 1 ≤ k < i: a_k ≠ х)

Это условие не только указывает на желаемый результат, но из него же следует, что если элемент найден, то он найден вместе с минимально возможным индексом, т.е. это первый из таких элементов. Равенство i = N + 1 свидетельствует, что совпадения не существует.

Совершенно очевидно, что окончание цикла гарантировано, поскольку на каждом шаге значение i увеличивается, и, следовательно, оно, конечно же, достигнет за конечное число шагов предела N + 1; фактически же, если совпадения не было, это произойдет после N + 1 шагов.

Ясно, что на каждом шаге требуется увеличивать индекс и вычислять логическое выражение. А можно ли эту работу упростить и таким образом убыстрить поиск? Единственная возможность - попытаться упростить само логическое выражение, ведь оно состоит из двух членов. Следовательно, единственный шанс на пути к более простому решению - сформулировать простое условие, эквивалентное нашему сложному. Это можно сделать, если мы гарантируем, что совпадение всегда произойдет. Для этого достаточно в конец массива поместить дополнительный элемент со значением х. Назовем такой вспомогательный элемент «барьером», ведь он охраняет нас от перехода за пределы массива. Теперь массив будет описан так: a: ARR AY [1 ..N + 1] OF INTEGER и алгоритм линейного поиска с барьером выглядит следующим образом:

i:= 1; a[N + 1]: = x;

WHILE (a[i] <> x) DO i: = i + 1; (5.3)

Результирующее условие, выведенное из того же инварианта, что и прежде:

(а _i = х)) & (A k: 1 ≤ k < i: a_k ≠ х)

Ясно, что равенство i = N + 1 свидетельствует о том, что совпадения (если не считать совпадения с барьером) не было.

 

· ТЕМА 2. ПОИСК ДЕЛЕНИЕМ ПОПОЛАМ (ДВОИЧНЫЙ ПОИСК)

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

A k: 1 ≤ k ≤ N: a_{k - 1} ≤ a_k (5.4)

Основная идея - выбрать случайно некоторый элемент, предположим a_m, и сравнить его с аргументом поиска х. Если он равен х, то поиск заканчивается, если он меньше х, то мы заключаем, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска; если же он больше х, то исключаются индексы больше и равные т. Это соображение приводит нас к следующему алгоритму (он называется «поиском делением пополам»). Здесь две индексные переменные L и R отмечают соответственно левый и правый конец секции массива а, где еще может быть обнаружен требуемый элемент.

L: = 1; R: = N; found: = FALSE; (5.5)

WHILE (L< =R) and NOT found DO

BEGIN

m: = (L + R) DIV 2; { выбираем любой элемент между элементами с номерами L и R }

IF a[m]=x THEN found: = TRUE ELSE

IF a[m] < x THEN L: = m + 1 ELSE R: =m – 1;

END;

IF found THEN writeln(‘ искомый элемент ‘, a [m]);

Инвариант цикла, т.е. условие, выполняющееся перед каждым шагом, таков:

(L ≤ R) & (A k: 1 ≤ k < L: a_k < х) & (A k: R < k ≤ N: a_k > х) (5.6)

из чего выводится результат

found OR ((L > R) & (A k: 1 ≤ k < L: a_k < х) & (A k: R < k ≤ N: a_k > х))

откуда следует

(a_m = x) OR (A k: 1 ≤ k ≤ N: a_k ≠ х).

Выбор m совершенно произволен в том смысле, что корректность алгоритма от него не зависит. Однако на его эффективность выбор влияет. Ясно, что наша задача - исключить на каждом шагу из дальнейшего поиска, каким бы ни был результат сравнения, как можно больше элементов. Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива. В результате максимальное число сравнений равно log₂ (N), округленному до ближайшего целого. Таким образом, приведенный алгоритм существенно выигрывает по сравнению с линейным поиском, ведь там ожидаемое число сравнений - N / 2.

Эффективность можно несколько улучшить, поменяв местами заголовки условных операторов. Проверку на равенство можно выполнять во вторую очередь, так как она встречается лишь единожды и приводит к окончанию работы. Но более существенно следующее соображение: нельзя ли, как и при линейном поиске, отыскать такое решение, которое опять бы упростило условие окончания. И мы действительно находим такой быстрый алгоритм, как только отказываемся от наивного желания кончить поиск при фиксации совпадения. На первый взгляд это кажется странным, однако при внимательном рассмотрении обнаруживается, что выигрыш в эффективности на каждом шаге превосходит потери от сравнения с несколькими дополнительными элементами. Напомним, что число шагов в худшем случае - log₂ (N). Быстрый алгоритм основан на следующем инварианте:

(A k: 1 ≤ k < L: a_k < х) & (A k: R < k ≤ N: a_k ≥ х) (5.7)

причем поиск продолжается до тех пор, пока обе секции не «накроют» массив целиком.

L:= 1; R: = N + 1;

WHILE L<R DO

BEGIN

j: = (L + R) DIV 2;

IF a [j] < x THEN L:= j + 1 ELSE R: = j;

END;

IF a [R] = x THEN writeln(‘ искомый элемент ‘, a [R]);

Условие окончания - L ≥ R, но достижимо ли оно? Для доказательства этого нам необходимо показать, что при и всех обстоятельствах разность R – L на каждом шаге убывает. В начале каждого шага L < R. Для среднего арифметического m справедливо условие L ≤ m < R. Следовательно, разность действительно убывает, ведь либо L увеличивается при присваивании ему значения m + 1, либо R уменьшается при присваивании значения m. При L = R повторение цикла заканчивается. Однако наш инвариант и условие L = R еще не свидетельствуют о совпадении. Конечно, при R = N + 1 никаких совпадений нет. В других же случаях мы должны учитывать, что элемент а [R] в сравнениях никогда не участвует. Следовательно, необходима дополнительная проверка на равенство а [R] = х. В отличие от первого нашего решения (5.5) приведенный алгоритм, как и в случае линейного поиска, находит совпадающий элемент с наименьшим индексом.

 

 

· МОДУЛЬ 3. СОРТИРОВКА

 

· ТЕМА 1. ВНУТРЕННЯЯ И ВНЕШНЯЯ СОРТИРОВКИ

В этой части мы будем обсуждать методы сортировки информации. В общей постановке задача ставится следующим образом. Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (далее мы будем называть его ключом сортировки). Тип данных ключа должен включать операции сравнения («=», «>», «<», «>=» и «<=»). Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа. Устойчивость сортировки часто бывает желательной, если речь идет об элементах, уже упорядоченных (отсортированных) по некоторым вторичным ключам (т.е. свойствам), не влияющим на основной ключ.

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

1. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.

2. Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.

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

 

· ТЕМА 2. МЕТОДЫ ВНУТРЕННЕЙ СОРТИРОВКИ

Естественным условием, предъявляемым к любому методу внутренней сортировки является то, что эти методы не должны требовать дополнительной памяти: все перестановки с целью упорядочения элементов массива должны производиться в пределах того же массива. Мерой эффективности алгоритма внутренней сортировки являются число требуемых сравнений значений ключа (C) и число перестановок элементов (M).

Заметим, что поскольку сортировка основана только на значениях ключа и никак не затрагивает оставшиеся поля записей, можно говорить о сортировке массивов ключей.

Методы сортировки «на том же месте» можно разбить в соответствии с определяющими их принципами на три основные категории:

1. Сортировки с помощью включения (by insertion).

2. Сортировки с помощью выбора (by selection).

3. Сортировки с помощью обменов (by exchange).

Сортировка включением

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями. Идея алгоритма очень проста. Пусть имеется массив ключей a[1], a[2],..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i – 1], a[i – 2]...) и до тех пор, пока для очередного элемента слева a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i + 1] (пока не будет достигнута верхняя граница массива).

Легко видеть, что в лучшем случае (когда массив уже упорядочен) для выполнения алгоритма с массивом из n элементов потребуется n – 1 сравнение и 0 пересылок. В худшем случае (когда массив упорядочен в обратном порядке) потребуется n(n – 1)/2 сравнений и столько же пересылок. Таким образом, можно оценивать сложность метода простых включений как O(n ² ).

Можно сократить число сравнений, применяемых в методе простых включений, если воспользоваться тем фактом, что при обработке элемента a[i] массива элементы a[1], a[2],..., a[i – 1] уже упорядочены, и воспользоваться для поиска элемента, с которым должна быть произведена перестановка, методом двоичного деления. В этом случае оценка числа требуемых сравнений становится O(n log n). Заметим, что поскольку при выполнении перестановки требуется сдвижка на один элемент нескольких элементов, то оценка числа пересылок остается O(n² ).

Таблица 5.1

Пример сортировки методом простого включения

В реальном процессе поиска подходящего места удобно, чередуя сравнения и движения по последовательности, как бы просеивать a [ i ], т.е. a [ i ] сравнивается с очередным элементом a [ j ], а затем либо a [ i ] вставляется на свободное место, либо a [ j ] сдвигается (передается) вправо и процесс «уходит» влево. Обратите внимание, что процесс просеивания может закончиться при выполнении одного из двух следующих различных условий:

1. Найден элемент a [ j ] с ключом, меньшим чем ключ у a [ i ].

2. Достигнут левый конец готовой последовательности.

FOR i: = 2 TO N DO BEGIN

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

WHILE (a[j – 1] > x) AND (j > 1) DO BEGIN

a[j]: = a[j – 1];

j: =j – 1

END;

a[j]: = x;

END;

Обменная сортировка

Простая обменная сортировка (в просторечии называемая «методом пузырька») для массива a[1], a[2],..., a[n] работает следующим образом. Начиная с начала массива сравниваются два соседних элемента (a[ i ] и a[ i + 1]). Если выполняется условие a[ i ] > a[ i + 1], то значения элементов меняются местами. Процесс продолжается для a[ i + 1] и a[ i + 2] и т.д., пока не будет произведено сравнение a[ n – 1] и a[ n ]. Понятно, что после этого на месте a[ n ] окажется элемент массива с наибольшем значением. На втором шаге процесс повторяется, но последними сравниваются a[ n – 2] и a[ n – 1]. И так далее. На последнем шаге будут сравниваться только текущие значения a[1] и a[2]. Понятна аналогия с пузырьком, поскольку наименьшие элементы (самые «легкие») постепенно «всплывают» к верхней границе массива.

Для метода простой обменной сортировки требуется число сравнений n(n – 1)/2, минимальное число пересылок 0, а среднее и максимальное число пересылок - O(n ² ).

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

i: = 0;

REPEAT

fl: = TRUE; i: = i + 1;

FOR j: = 1 TO n – i DO

IF a[j] > a[j + 1] THEN BEGIN

fl: = FALSE; x: = a[j];

a[j]: = a[j + 1]; a[j + 1]: = x

END;

UNTIL fl;

Метод пузырька работает неравноправно для «легких» и «тяжелых» значений. Легкое значение попадает на нужное место за один шаг, а тяжелое на каждом шаге опускается по направлению к нужному месту на одну позицию.

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

{шейкер-сортировка по убыванию}

L: = 2; R: = n; k: = n;

REPEAT

FOR j: = R DOWNTO L DO

IF a[j – 1] < a[j] THEN BEGIN

x: = a[j]; a[j]: = a[j – 1]; a[j – 1]: = x; k: = j

END;

L: = k + 1;

FOR j: = L TO R DO

IF a[j – 1] < a[j] THEN BEGIN

x: = a[j]; a[j]: = a[j – 1]; a[j – 1]: = x; k: = j

END;

R: = k – 1;

UNTIL L>R;

Шейкерная сортировка позволяет сократить число сравнений (по оценке Кнута средним числом сравнений является (n ² – n(const + ln n)), хотя порядком оценки по-прежнему остается n ² . Число же пересылок, вообще говоря, не меняется. Шейкерную сортировку рекомендуется использовать в тех случаях, когда известно, что массив «почти упорядочен».

Сортировка выбором

При сортировке массива a[1], a[2],..., a[n] методом простого выбора среди всех элементов находится элемент с наименьшим значением a[i], и a[1] и a[i] обмениваются значениями. Затем этот процесс повторяется для получаемых подмассивов a[2], a[3],..., a[n],... a[j], a[j + 1],..., a[n] до тех пор, пока мы не дойдем до подмассива a[n], содержащего к этому моменту наибольшее значение. Работа алгоритма иллюстрируется примером в таблице 5.2.

Таблица 5.2

Пример сортировки простым выбором

Для метода сортировки простым выбором требуемое число сравнений - n(n – 1)/2. Порядок требуемого числа пересылок (включая те, которые требуются для выбора минимального элемента) в худшем случае составляет O(n2). Однако порядок среднего числа пересылок есть O(n*ln(n)), что в ряде случаев делает этот метод предпочтительным.

FOR i: = 1 TO n – 1 DO BEGIN

x: = a[i]; k: = i;

FOR j: = i + 1 TO n DO

IF a[j]<x THEN BEGIN x: = a[j]; k: = j END;

a[k]: = a[i]; a[i]: = x;

END;

Сравнение прямых методов внутренней сортировки

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

Таблица 5.3