Programming Taskbook 0

Глава 5. Дополнительные средства обработки массивов 
111 
Кроме методов преобразования массивов (вызываемых с применени-
ем точечной нотации) в библиотеке PascalABC.NET имеются две процеду-
ры, предназначенные для преобразования массива и принимающие этот 
массив в качестве параметра: 
procedure Reverse(a: array of T[; start, count: integer])
procedure Sort(a: array of T)
Процедура Reverse инвертирует массив a (или его часть из count эле-
ментов, начиная с индекса start). Эта процедура ранее обсуждалась и ис-
пользовалась в п. 3.7. Процедура Sort сортирует массив а; ее действие ана-
логично применению одноименного метода. 
В качестве иллюстрации одного из описанных методов преобразова-
ния рассмотрим задачу Array88. В этой задаче дан массив вещественных 
чисел, все элементы которого, кроме последнего, уже отсортированы по 
возрастанию. Требуется переместить последний элемент на новую пози-
цию в массиве таким образом, чтобы весь массив стал упорядоченным по 
возрастанию. 
Наиболее эффективное решение данной задачи требует однократного 
просмотра массива с одновременным сдвигом его элементов вправо, пока 
не будет найдена позиция p для размещения последнего элемента: 
Task('Array88'); // Вариант 1 
var a := ReadArrReal; 
var b := a[a.Length - 1]; 
var p := 0; 
for var i := a.Length - 2 downto 0 do 
if a[i] > b then 
a[i + 1] := a[i] 
else 
begin 
p := i + 1; 
break; 
end;
a[p] := b; 
a.Print; 
В алгоритме учитывается особая ситуация, при которой последний 
элемент массива (который хранится во вспомогательной переменной b) 
окажется меньше всех предыдущих элементов. В этом случае условие 
a[i] > b, проверяемое в цикле, никогда не станет ложным, поэтому значение 
переменной p останется равным 0, и после выхода из цикла значение b бу-
дет записано в начальный элемент массива. 
Возникает вопрос: насколько хуже данного варианта будет вариант, 
просто сортирующий исходный массив? Ведь в стандартной библиотеке 

---

112 
реализован весьма эффективный алгоритм сортировки! Во всяком случае, с 
точки зрения краткости решения новый вариант будет существенно более 
выигрышным: 
Task('Array88'); // Вариант 2 
var a := ReadArrReal; 
a.Sort; 
a.Print; 
Заодно можно сравнить эффективность метода Sort и аналогичного за-
проса сортировки Order (см. п. 4.2), применение которого тоже дает пра-
вильный вариант решения (обратите внимание на вызов запроса ToArray, 
преобразующего отсортированную последовательность «обратно» в мас-
сив):
Task('Array88'); // Вариант 3 
var a := ReadArrReal; 
a := a.Order.ToArray; 
a.Print; 
Заметим, что у этого варианта имеется один очевидный недостаток: 
отсортированный набор возвращается в качестве новой последовательно-
сти и при ее преобразовании в массив выделяется новый участок памяти. В 
варианте 2 выполнялась сортировка элементов самого исходного массива, 
и поэтому дополнительная память не выделялась. Таким образом, в отно-
шении использования памяти вариант 3 уступает как варианту 1, так и ва-
рианту 2. 
Для проверки быстродействия алгоритмов необходимо обрабатывать 
массивы большого размера size. Для генерации набора из size возрастаю-
щих вещественных чисел удобно использовать запрос Range (см. п. 3.5): 
Range(0.0, 1.0, size – 1). В результате будет создан набор из size веществен-
ных чисел, равномерно распределенных на отрезке [0; 1] (включая концы). 
После этого останется преобразовать полученную последовательность в 
массив запросом ToArray и изменить значение последнего элемента, поло-
жив его равным, например, 0.5 (в этом случае для решения задачи потребу-
ется переместить этот элемент в середину массива).
Полученный массив обрабатывался каждым из приведенных выше ал-
горитмов; при этом измерялось время работы алгоритма в миллисекундах 
(время, использованное на генерацию массива, не учитывалось). Програм-
ма запускалась в режиме релиза (см. замечание в п. 3.4), как и все рас-
смотренные ранее программы для проведения численного эксперимента. 
В таблице 5.2 приведены результаты работы программы, а также ин-
формация о том, во сколько раз варианты 2 и 3 работают медленнее вари-
анта 1: в столбцах с заголовками «Вар.2 / Вар.1» и «Вар.3 / Вар.1» указы-

---