Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 11
Текст из файла (страница 11)
Чтобы определить, куда нужно поместить очередную карту, ее масть и достоинство сравнивается с мастью и достоинством карт в руке. Допустим, сравнение проводится в направлении слева направо (рис. 2.1). В любой момент времени карты в левой руке будут рассортированы, и это будут те карты, которые первоначально лежали в стопке на столе. Глава 2. Приступаем к изучению 59 Псевдокод сортировки методом вставок представлен ниже под названием 1мзнкт)ом Яокт. На его вход подается массив А [1..],, содержащий последовательность из п сортируемых чисел (количество элементов массива А обозначено в этом коде как 1епдбй [А].) Входные числа сортируюпася без использования дополнительной памяти: их перестановка производится в пределах массива, и объем используемой при этом дополнительной памяти не превышает некоторую постоянную величину.
По окончании работы алгоритма 1мзвкт)ом Зонт входной массив содержит отсортированную последовательность: 1мзект)ом Болт(А) 1 1ог 2' — 2 2о 1епдгй[А] 2 йо кеу — А[7] 3 с Вставка элемента А[7] в отсортированную с последовательность А [1..7' — 1] 4 в -7 — 1 5 и)Н1е в > О и А[а] > кеу 6 41о А[в+ 1] — А[в] 7 — в — 1 8 А[в+ 1] — кеу Инварианты цикла и корректность сортировки вставкой На рис.
2.2 продемонстрировано, как этот алгоритм работает для массива А = (5,2,4,6, 1, 3). Элементы массива обозначены квадратиками, над которыми находятся индексы, а внутри — значения соответствую)цих элементов. Части а-д этого рисунка соответствуют итерациям цикла 1ог в строках 1-8 псевдокода. В каждой итерации черный квадратик содержит значение ключа, которое сравнивается со значениями серых квадратиков, расположенных слева от него (строка псевдокода 5). Серыми стрелками указаны те значения массива, которые сдвигаются на одну позицию вправо (строка 6), а черной стрелкой — перемещение ключа (строка 8).
В части е показано конечное состояние сортируемого массива. ! 2 3 4 5 6 а) 4 б ! 3 ! 2 3 4 5 б б) ' ' 6 ! 3 ! 2 3 4 5 6 в) 2 4'л ! 3 ! 2 3 4 5 6 ! 2 3 4 5 б )! 3 13 3 3 Д Рис. 2.2. Выполнение алгоритма 1мзвктюм Болт нал массивом А = (5,2,4,6,1,3) 60 Часть!. Основы Индекс т' указывает "текущую карту*', которая помещается в руку. В начале каждой итерации внешнего цикла 1ог с индексом у массив А состоит из двух частей.
Элементы А (1..у — 1] соответствуют отсортированным картам в руке, а элементы А [у + 1..п] — стопке карт, которые пока что остались на столе. Заметим, что элементы А [1..у — 1] изначально тоже находились на позициях от 1 до у — 1, но в другом порядке, а теперь они отсортированы. Назовем это свойство элементов А [1..) — 1] инвариантам цикла (1оор 1пчаг)апт) и сформулируем его еще раз. В начале каждой итерации цикла 1ог из строк 1-8 подмассив А [1.. у — 1] содержит те же элементы, которые были в нем с самого начала, но расположенные в отсортированном порядке. Инварианты цикла позволяют понять, корректно ли работает алгоритм.
Необходимо показать, что инварианты циклов обладают следующими тремя свойствамн. Инициализация. Они справедливы перед первой инициализацией цикла. Сохранение. Если онн истинны перед очередной итерацией цикла, то остаются истинны и после нее.
Завершение. По завершении цикла инварианты позволяют убедиться в правильности алгоритма. Если выполняются первые два свойства, инварианты цикла остаются истинными перед каждой очередной итерацией цикла. Обратите внимание на сходство с математической индукцией, когда для доказательства определенного свойства для всех элементов упорядоченной последовательности нужно доказать его справедливость для начального элемента этой последовательности, а затем обосновать шаг индукции. В данном случае первой части доказательства соответствует обоснование того, что инвариант цикла выполняется перед первой итерацией, а второй части — доказательство того, что инвариант цикла выполняется после очередной итерации (шаг индукции).
Для наших целей третье свойство самое важное, так как нам нужно с помощью инварианта цикла продемонстрировать корректность алгоритма. Оно также отличает рассматриваемый нами метод от обычной математической индукции, в которой шаг индукции используется в бесконечных последовательностях.
В данном случае по окончании цикла "индукция" завершается. Рассмотрим, соблюдаются ли эти свойства для сортировки методом включений. Инициализация. Начнем с того, что покажем справедливость инварианта цикла перед первой итерацией, т.е. при у' = 2'. Таким образом, подмножество элементов А [1..у — 1] состоит только из одного элемента А [1], сохраняющего ' Если рассматривается цикл Гог, момент времени, когда проверяется справедливость инварианта цикла перел первой итерацией, наступает сразу после начального присваивания значения индексу Глава 2. Приступаем к изучению 61 исходное значение.
Более того, в этом подмножестве элементы рассортированы (тривиальное утверждение). Все вышесказанное подтверждает, что инвариант цикла соблюдается перед первой итерацией цикла. Сохранение. Далее, обоснуем второе свойство: покажем, что инвариант цикла сохраняется после каждой итерации. Выражаясь неформально, можно сказать, что в теле внешнего цикла Гог происходит сдвиг элементов А [у — Ц, А [7' — 2], А [7' — 3], ...
на одну позицию вправо до тех пор, пока не освободится подходящее место для элемента А [7] (строки 4 — 7), куда он и помещается (строка 8). При более формальном подходе к рассмотрению второго свойства потребовалось бы сформулировать и обосновать инвариант для внутреннего цикла туЫ1е. Однако на данном этапе мы предпочитаем не вдаваться в такие формальные подробности, поэтому будем довольствоваться неформальным анализом, чтобы показать, что во внешнем цикле соблюдается второе свойство. Завершение. Наконец, посмотрим, что происходит по завершении работы цикла. При сортировке методом включений внешний цикл гог завершается, когда 7' превышает и, т.е.
когда з = гг + 1. Подставив в формулировку инварианта цикла значение и + 1, получим такое утверждение: в подмножестве элементов А [1..п] находятся те же элементы, которые были в нем до начала работы алгоритма, но расположенные в отсортированном порядке. Однако подмножество А [1..п] и есть сам массив А1 Таким образом, весь массив отсортирован, что и подтверждает корректность алгоритма. Метод инвариантов циклов будет применяться далее в данной главе, а также в последующих главах книги. Соглашения, принятые при составлении псевдокода При составлении псевдокода использовались следующие соглашения.
1. Структура блоков указывается с помощью отступов. Например, тело цикла 1ог, начало которого — в строке 1, образовано строками 2 — 8, а тело цикла ттЫ)е, который начинается в строке 5, состоит из строк 6 и 7, а строка 8 в него не входит. Стиль отступов имеет силу также в инструкциях 1т"4Ьеп-е1ве. Использование отступов вместо общепринятых указателей блочной структуры, таких как инструкции Ьей1п и епй, значительно уменьшает громоздкость.
При этом псевдокод не становится менее понятным, а даже наоборот'. цикла, но перел первой проверкой в заголовочной инструкции цикла. В листинге 1изаптюи беат зто момент, когда переменной у присвоено значение 2, но еще не выполнена проверка неравенства у ~ <меняй [А]. В реальных языках программирования, вообще говоря, не рекомендуется применять отступы для того, чтобы подчеркнуть структуру блоков, поскольку, если код разбит на несколько страниц, то сложно определить уровень вложенности блоков.
Часть!. Основы Инструкции циклов иййе, аког и гереат, а также общепринятая конструкция 11'-Фел-е!ве интерпретируются аналогично одноименным инструкциям языка Равса1з. Что касается цикла 1ог, то здесь есть одно тонкое различие: в языке Рааса) после выхода из цикла значение переменной, выступающей в роли счетчика цикла, становится неопределенным, а в данной книге счетчик сохраняет свое значение после выхода из цикла.
Таким образом, сразу после завершения цикла 1ог значение счетчика равно значению, на единицу превышающему верхнюю границу цикла. Это свойство уже использова- лось для доказательства корректности алгоритма сортировки, работающего по методу вставок. Заголовок цикла Гог, заданный в строке 1, имеет вид 1ог з - 2 то 1епдй[А], поэтому по завершении цикла т' = 1епдй[А]+1 (или, что то же самое, д = и + 1). Символ "с " указывают, что оставшаяся часть строки — это комментарий. Множественное прнсваивание, имеющее вид т - д < — е, обозначает, что значение выражения е присваивается обеим переменным з' и д; оно аналогично двум последовательным инструкциям присваивания: д — е и з Переменные (такие как з, д и кеу) являются локальными по отношению к данной процедуре.
Глобальные переменные не применяются, если это не указано явным образом. 3. 4. 5. Доступ к элементам массива осуществляется путем указания имени массива, после которого в квадратных скобках следует индекс. Например, А [з]— это обозначение з-го элемента массива А. С помощью обозначения "..*' указывается интервал значений, которые принимает индекс массива. Таким образом, обозначение А [1.. Я свидетельствует о том, что данное подмножество массива А состоит из д элементов А [1], А [2],..., А [у]. Сложные данные обычно представляются в виде объакагов, состоящих из аагрибуагов и налей.
Доступ к определенному полю осуществляется с помощью имени поля, после которого в квадратных скобках указывается имя объекта. Например, массив трактуется как объект с атрибутом 1епдй, указывающим количество его элементов. Чтобы указать количество элементов массива А, нужно написать 1епдй [А]. Несмотря на то, что квадратные скобки используются и для индексирования элементов массива, и в атрибутах объекта, их интерпретация будет понятна из контекста. Переменная, которая используется в качестве имени массива или объекта, б. 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
