Алгоритмы - построение и анализ (1021735), страница 10
Текст из файла (страница 10)
Обзоры по алгоритмам можно также найти в книгах Напс~Ьоой о]' ТЬеоге!!са! Сотршег 5с!елсе, Ро!ите А [302] и СЯС Налс!Ьоо!с оп А!8огйЬть алс! ТЬеогу о!'Сотришг!оп [24]. Обзоры алгоритмов, применяющихся в вычислительной биологии, можно найти в учебниках Гасфилда (ОпкбеЫ) [136], Певзнера (Речгпег) [240], Сетубала (Бе1иЬа!) и Мейдениса (МеЫап(в) [272], а также Вотермена (9!!а!еппап) [309]. ГЛАВА 2 Приступаем к изучению В этой главе мы ознакомимся с основными понятиями, с помощью которых на протяжении всей книги будет проводиться разработка и анализ алгоритмов.
В начале главы исследуется алгоритм сортировки вставками. Он предназначен для решения задачи сортировки, поставленной в главе 1. Для формулирования алгоритмов мы используем псевдокод (который должен быть понятен читателям, имеющим опыт программирования). Для каждого алгоритма обосновывается его корректность и анализируется время работы. В ходе анализа указанного алгоритма вводятся обозначения, используемые для указания зависимости времени работы алгоритма от количества сортируемых элементов.
После обсуждения сортировки вставками описывается метод декомпозиции, основанный на принципе "разделяй и властвуй". Этот подход используется для разработки различных алгоритмов; в данном случае с его помощью будет сформулирован алгоритм, получивший название сортировки слиянием. В конце главы анализируется время работы этого алгоритма сортировки.
2.1 Сортировка вставкой Наш первый алгоритм, алгоритм сортировки методом вставок, предназначен для решения задачи сортировки (зогйпд ргоЫеш), сформулированной в главе 1. Приведем еще раз эту формулировку. Вход: последовательность из и чисел (ам аз,...,а ). Выход: перестановка (изменение порядка) (ама~з,...,а'„) входной последовательности таким образом, что для ее членов выполняется соотношение а' <а' < <а'„. 58 Часть 1. Основы Рнс. 2.1. Сортировка карт методом вставок Сортируемые числа также известны под названием ключи (кеуз). В этой книге алгоритмы обычно описываются в виде псевдокода, который во многих отношениях похож на языки программирования С, Рааса! и 1ача. Тем, кто знаком хотя бы с одним из этих языков, не потребуется много усилий на чтение алгоритмов.
От обычного кода псевдокод отличается тем, что он выразителен, а также лаконично, точно и понятно описывает алгоритм. Иногда в качестве такового выступает литературный язык, поэтому не удивляйтесь, если в инструкции "настоящего" кода встретите обычную фразу или предложение. Другое различие между псевдокодом и обычным кодом заключается в том, что в псевдокоде, как правило, не рассматриваются некоторые вопросы, которые приходится решать разработчикам программного обеспечения. Такие вопросы, как абстракция данных, модульность и обработка ошибок часто игнорируются, чтобы более выразительно передать суть, заложенную в алгоритме. Наше изучение алгоритмов начинается с рассмотрения сортяироаки встиавюй (шзеп1оп зоп).
Этот алгоритм эффективно работает при сортировке небольшого количества элементов. Сортировка вставкой напоминает способ, к которому прибегают игроки для сортировки имеющихся на руках карт. Пусть вначале в левой руке нет ни одной карты, и все они лежат на столе рубашкой вверх. Далее со стола берется по одной карте, каждая из которых помещается в нужное место среди карт, которые находятся в левой руке. Чтобы определить, куда нужно поместить очередную карту, ее масть и достоинство сравнивается с мастью и достоинством карт в руке. Допустим, сравнение проводится в направлении слева направо (рис. 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 3 4 5 6 а) 4 б ! 3 ! 2 3 4 5 б б) ' ' 6 ! 3 ! 2 3 4 5 6 в) 2 45л ! 3 ! 2 3 4 5 6 ! 2 3 4 5 б )! 3 13 3 3 Д Рис.
2.2. Выполнение алгоритма 1мзвктюм Болт нал массивом А = (5,2,4,6,1,3) На рис. 2.2 продемонстрировано, как этот алгоритм работает для массива А = (5,2,4,6, 1, 3). Элементы массива обозначены квадратиками, над которыми находятся индексы, а внутри — значения соответствую)цих элементов. Части а-д этого рисунка соответствуют итерациям цикла 1ог в строках 1-8 псевдокода.
В каждой итерации черный квадратик содержит значение ключа, которое сравнивается со значениями серых квадратиков, расположенных слева от него (строка псевдокода 5). Серыми стрелками указаны те значения массива, которые сдвигаются на одну позицию вправо (строка 6), а черной стрелкой — перемещение ключа (строка 8). В части е показано конечное состояние сортируемого массива. 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], ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
