8.3.2. Программа сортировки «индексов» массива

«Сортировка индексов» - результатом сортировки является последовательность (массив) целочисленных переменных {k_i}, i=1, 2, ...n, где число k_i указывает порядковый номер объекта a_ki , который должен находиться на i-ом месте в отсортированной совокупности.

Пример программы, помещающей результаты сортировки массива действительных чисел в специальный массив индексов K[].

Program N8;

Type T=array[1..4] of real;

Const a:T=(30, 40, -20, 30);

Var K: array[1..4] of integer; {массив для размещения значений индексов}

Var i, j, ii, N: integer;

Begin

N:=4;

for i:=1 to N do K[i]:=i; {первоначально, содержимое массива K[]

совпадает с естественной номерацией неупорядоченного

содержимого (информации) массива a[]}

for ii:=1 to N-1 do {ii – счетчик повторных просмотров

элементов массива}

for i:=1 to N-ii do { i – номер первого из пары просматриваемых

индексов }

if (a[K[i]]<a[K[i+1]])=false then {информация объекта с индексом

K[i+1], т.е. дествительное числоa [K[i+1]], должно находится

левее информации объекта с индексом K[i], т.е. левее

действительного числа a[K[i]] }

begin j:=K[i]; K[i]:=K[i+1]; K[i+1]:=j end;

{ печать содержимого массива a[] в

Упорядоченном (отсортированном) виде}

for i:=1 to N do WRITE(a[K[i]]:5:0);

End.

Трассировка программы:

Значения счетчиков циклов i и ii	Текущее содержимое массива K
	k[1]	k[2]	k[3]	k[4]
ii=1 i=1 (нет переписей)	1	2	3	4
i=2 (перепись 2 и 3)	1	3	2	4
i=3 (перепись 2 и 4)	1	3	4	2
ii=2 i=1 (перепись 1 и 3)	3	1	4	2
i=2 (перепись 1 и 4)	3	4	1	2
ii=3 i=1 (нет переписей)	3	4	1	2

Метод «сортировки индексов», сохраняя первоначальную структуру сортируемой информации, требует дополнительно всего 2n байт памяти ЭВМ.

8.4. Алгоритм быстрого поиска информации в линейно упорядоченном массиве

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

Задача: в упорядоченном, по операции сравнения Р, массиве информационных объектов {a_i}, i=1, 2, ...n, для заданного объекта b, найти два соседних элемента a_j и a_j+1 , для которых P(aj,b)=true и P(b,a_j+1)=true, т.е. объект a_j предшествует b объекту и b предшествует a_j+1.

Частные случаи решения:

1). Объект b может предшествовать всем элементам массива, что имеет место если P(b,a₁)=true,

2). Все элементы массива могут предшествовать объекту b, что будет наблюдаться если P(a_n,b)=true.

Алгоритм решения задачи.

1). Проверяем частные случаи. Если один из них выполняется, то задача решена. В противном случае, объект b находится правее объекта a₁ и левее объекта a_n. Запоминаем номера (индексы) элементов, ограничивающих область локализации объекта b: i_min=1 и i_max=n.

2). Вычисляем i-номер (индекс) объекта a_i расположенного в центре области локализации i=( i_min + i_max ) div 2 (целочисленное деление !).

3). Если P(a_i,b)=true, т.е. объект a_i действительно располагается левее объекта b, то изменяем i_min=i, в противном случае изменяем i_max=i.

Размер области локализации объекта b сокращен в два раза!

4). Повторяем выполнение пунктов (2) и (3) K- раз, где K=[Log₂n], т.е. K- наименьшее целое число удовлетворяющее неравенству n≤2^K.

Примеры количественной оценки алгоритма:

1. Для поиска нужной информации в массиве из n=500 элементов требуется проведения всего K=9 проверок, т.к. размеры области локализации решения (i_max -i_min ) последовательно сокращаются:

imax -imin	499	250	125	63	32	16	8	4	2	1
K	0	1	2	3	4	5	6	7	8	9

Для решения этой же задачи с неупорядоченными данными пришлось бы сделать 1000 проверок, т.е. в сто раз больше.

2. Для поиска адреса человека в миллионном городе, по его Ф.И.О., требуется выполнить всего двадцать проверок в упорядоченном списке соответствующей базы данных.