Моделирование алгоритма работы сортировки элементов и метода поиска образца в упорядоченной информации

r">2⁶⁵ < 21! < 2⁶⁶,

ясно  также, что и в любом другом случае необходимо не менее 66 сравнений; следовательно,

5(21) = 66. (10)

(При  сортировке с помощью бинарных  вставок понадобилось бы 74 сравнения.) В общем случае сортировка  посредством вставок и слияния  для п элементов выглядит следующим образом.

i) Сравнить [п/2] непересекающихся пар элементов.   (Если п нечетно, то один элемент не участвует в сравнениях.)

ii) Рассортировать [п/2] больших элементов пар, найденных на шаге (i), посредством вставок и слияния.

iii) Для элементов введем обозначения a₁, а₂,.. , a[n/2] , b₁, b_2, . . ., b[n/2] , как в (7), =где а₁ <= а₂ <= . . . <= a[n/2] и b_i <= a_i при 1 <= i <= [n/2]; назовем b₁ и все элементы а главной цепочкой. Не трогая элементов b_j при j > [n/2], вставим посред-ством бинарных вставок в главную цепочку остальные элементы Ь в следующем порядке:

   Наша  цель — сформировать последовательность (t₁,t₂,t₃,t₄, . . .) = (1,3,5,11, ...), присутствующую в (11), таким образом, чтобы каждый из элементов b_tk,b_tk-1, . . . ,b_tk_₁+1 можно было вставить в главную цепочку не более чем за к сравнений. Обобщая (7)-(9), получим диаграмму

на которой  главная цепочка до at_k-1 включительно содержит 2t_k-₁ + (t_k — t_k-1 — 1) элементов. Это число должно быть меньше 2^к; для нас лучше всего положить его равным 2^к — 1, и тогда

Поскольку t₁ = 1, для удобства можно положить t₀ = 1. В итоге, суммируя члены геометрической прогрессии, найдем

(Любопытно,  что точно такая же последовательность  возникла при изучении алгоритма вычисления наибольшего общего делителя двух целых чисел; см. упр. 4.5.2-36.)

   Пусть F{n) — число сравнений, необходимых для сортировки п элементов посредством вставок и слияния. Ясно, что

где функция  G описывает объем работы, выполняемой на шаге (iii). Если tk-1 <= т <= t_k, то, суммируя по частям, получаем

Положим

 

и тогда = (0, 1, 2, 5, 10, 21,...). В упр. 13 показано, что

   F(n) — F(n - 1) = к тогда и только тогда, когда W_k < n <= W_k+1, (17) а последнее условие эквивалентно неравенствам

или к + 1 < lg3n  <= к + 2; следовательно,

(Эта формула получена А. Хадьяном (A. Hadian) [Ph. D. thesis, Univ. of Minnesota (1969), 38-42].) Отсюда вытекает, что функция F(n) выражается на удивление простой формулой

которая очень похожа на формулу (3) для метода бинарных вставок. В замкнутом виде эту сумму можно найти в упр. 14.

   Воспользовавшись (19), нетрудно построить таблицу значений функции F(n); имеем

Обратите  внимание на то, что..F(n) = [lgn!] при 1 <= n <= 11 и при 20 <= п <= 21; таким образом, при этих значениях п сортировка посредством вставок и слияния оптимальна:

   Задачу  нахождения функции S(n) поставил Гуго Штейнгауз (Hugo Steinhaus) во втором издании своей классической книги Mathematical Snapshots (Oxford University Press, 1950, 38-39)*. Он описал метод бинарных вставок, который является наилучшим способом сортировки га элементов при условии, что га-й элемент не рассматривается до тех пор, пока не рассортированы первые га — 1 элементов; он  

 

Таблица 1

ЗНАЧЕНИЯ ФАКТОРИАЛОВ  В ДВОИЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ

же сделал предположение о том, что метод  бинарных вставок оптимален и  в общем случае. Несколько лет  спустя Штейнгауз сообщил [Calcutta Math. Soc. Golden Jubilee Commemoration 2 (1959), 323-327], что двое его коллег, С. Трибула (S. Trybula) и Чжен Пинг (P. Czen), "недавно" опровергли его предположение и нашли значения S(n) при п < 11. Вероятно, Трибула и Чжен Пинг независимо пришли к сортировке посредством вставок и слияния, о чем вскоре появилась публикация Ford, Johnson, АММ 66 (1959), 387-389.

   После открытия сортировки посредством вставок  и слияния первым неизвестным значением функции S(n) оставалось 5(12). Из табл. 1 видно, что число 12! довольно близко к 2²⁹, поэтому существование 29-шаговой процедуры сортировки 12 элементов весьма маловероятно. Для решения этого вопроса Марком Уэлсом (Mark Wells) был предпринят продолжительный вычислительный эксперимент (продолжавшийся на компьютере Maniac II около 60 ч), который показал, что S(12) = 30 [Рrос. IFIP Congress 65 2 (1965), 497-498]. Итак, процедура вставок и слияний оказывается оптимальной и при п = 12. 

2. Алгоритм  поиска.Бинарные атрибуты

   Поучительно рассмотреть частный случай, когда все атрибуты могут иметь только два значения. По сути, это противоположность комбинированных атрибутов, поскольку любое значение можно представить как двоичное число и рассматривать индивидуальные биты этого числа как отдельные атрибуты. В табл. 1 показан типичный файл с атрибутами "Да"-"Нет" В этом примере записи содержат рецепты домашнего печенья, а атрибуты определяют используемые ингредиенты. Например, миндальные вафли с ромом сделаны из масла, муки, молока, орехов и сахарного песка. Если рассматривать табл. 1 как матрицу из нулей и единиц, то транспонированная матрица будет представлять собой инвертированный файл в виде битовых строк.

   Правый столбец табл. 1 используется для указания специальных, редко используемых продуктов. Они могут быть закодированы более эффективно, без отдельного столбца для каждого из них. То же самое справедливо для столбца "Кукурузный крахмал" Кроме того, можно найти более эффективный путь кодирования столбца "Мука" поскольку мука встречается во всех рецептах, кроме рецепта приготовления меренги. Однако пока оставим этот вопрос и просто проигнорируем столбец "Специальные ингредиенты"

   Будем определять базовый запрос к файлу бинарных атрибутов как запрос на все записи, в одних столбцах которых содержатся нули, в других — единицы и в остальных столбцах — произвольные величины. Используя символ "*" для обозначения любого значения, базовый запрос можно представить в виде последовательностей символов 0, 1 и "*" Например, представим человека, который захотел печенья с кокосом и у которого аллергия на шоколад, который ненавидит анис и у которого дома закончился ванилин. Тогда его запрос может быть сформулирован так:

*0****0**1*******************0.                  (10)

Из  табл. 1 становится понятно, что его  желания совпадают с его возможностями  в случае ароматных палочек с  черносливом.

      Прежде чем приступить к организации  файла для базовых запросов, рассмотрим один важный специальный момент, когда в запросе отсутствуют нули, а есть только 1 и "*". Такой запрос можно назвать включающим (inclusive query), поскольку он запрашивает записи, которые включают некоторое множество атрибутов (если предположить, что 1 означает наличие определенного атрибута, а 0 — его отсутствие). Например, в табл. 1 два рецепта одновременно содержат и пекарный порошок, и пищевую соду — глазированные имбирные пряники и старинное сахарное печенье.

   В некоторых приложениях достаточно использовать специальные включающие запросы, например в ручных карточных системах наподобие карт с перфорацией по краям или карт свойств. Система карт с перфорацией по краям для табл. 1 будет иметь по одной карточке на каждый рецепт с вырезами, соответствующими каждому ингредиенту (рис. 46). Обработка включающего запроса сводится к складыванию карточек аккуратной стопкой и введению спиц в положениях, соответствующих конкретным ингредиентам. После ввода спиц все карточки с определенными атрибутами выпадают из стопки.

Рис. 46. Карта с перфорацией по краям.

   Система, основанная на картах свойств, работает с инвертированным файлом аналогичным  образом: имеется по одной карте  для каждого атрибута и отверстия  в карте пробиваются в позициях, которые соответствуют записям, содержащим этот атрибут. Таким образом, одна стандартная перфокарта шириной 80 позиций может использоваться для хранения информации о том, какие из 12 х 80 = 960 записей имеют данный атрибут. Для обработки включающего запроса отбираются карты свойств для определенных атрибутов и накладываются одна на другую. Луч света, проходя через позиции, в которых на всех картах имеются отверстия, покажет искомый результат. Это напоминает обработку логического запроса путем пересечения инвертированных битовых строк, как объяснялось выше. 
 
 
 

4. Практическая  часть

4.1 . Блок схема   алгоритма сортировки  массива чисел  посредством вставоки  и слияния.     Блок схема алгоритма процедуры Button2.click.

4.2 . Схема  программы  сортировки массива чисел посредством вставок и слияния. Схема программы процедуры Button2.click.

 

4.3. Блок схема поиска через бинарные атрибуты заданного образца в упорядоченном массиве.

4. Схема программы поиска через бинарные атрибуты заданного образца в упорядоченном массиве

4.5 Описание алгоритма задания элементов массива

Блок 1 является начальным.Во 2 блоке происходит разбитие массива пополам.В 3 блоке полученные части формируем в новые массивы.В 4 блоке вводится конечное значение элементов,полученных при разделении.В блоке 5 происходит формирование массива b.В блоке 6 обнуляем счетчик j.В боке 7 вводится конечно значение элементов,полученных при разделении для второй части элементов.В блоке 8 происходит формирование массива c.В блоке 9 задается конечное значение элементов массива.В блоке 10 происходит запись первого элемента массива в буфер.В блоке 11 проверяем условие,чтобы выбранный элемент был положительный и был больше буфера.В 12 блоке при истинном условии мы перемещаем следующий элемент на место выбранного,при этом сдвигая массив вправо.В блоке 13 при ложном условии происходит присвоенее следующему элементу значение буфера.В блоках с 14 по 18 происходит те же действия,что и в блоках с 9 по 13,но со второй частью разбитого массива.В 21 блоке происходит присвоение элементов начального значнеия для дальнейшего сортирования массива.В 22 блоке при условии,что количество символов в первой части отсортированного массива и во второй части не превышает длинну символов в нём.При ложном условии переходим в конец программы.

Описание  алгоритма поиска заданного образца

Блок 1 является начальным.Во 2 блоке присваиваем образцу значение Edit.В 3 блоке устанавливаем начальное значение найденного элемента – ложное.В 4 блоке вводится конечное значение элементов по всей строке.В 5 блоке устанавливаем значение нужного элемента на True. В 6 блоке устанавливаем условие,при котором разрядность не будет больше шестнадцатиричной и найденный элемент будет True.В 7 блоке при истинном условии блока 6 идет проверка элемента в двоичном коде с нужным нам,при истинном значении переходим к блоке 8.При ложном – 9.В 11 блоке проверяем найденный элемент на нужным нам.При истинном условии переходим к блоку 12,в котором выводим индекс найденного элемента.При ложном условии переходим к блоку 13,где найденный элемент – ложный и в 14 блоке выводим в memo “заданный образец не найден”.В 15 блоке при условии,что найденный элемент – True,мы выводим его индекс в блоке 16 и завершаем цикл в конечном блоке. 

4.6 Текст программы, выполняющей сортировку массива посредством вставок и слияния 

unit Unit2;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, Grids, StdCtrls, ExtCtrls;