У динамических массивов есть одно интересное свойство: новые элементы можно "засовывать" в любое место между уже включенными. Это позволяет при необходимости всегда держать динамический массив отсортированным: достаточно при поступлении нового элемента включать его не в голову или в хвост, а сразу на нужное место (Рис. 10.5).
Пусть нам необходимо держать список текстовых строк упорядоченным по алфавиту. Делается это так:
{ выделение памяти под новый элемент }
New(q);
{ ввод текстовой строки }
Readln(q^.data);
{ переменная r указывает на голову массива }
r := p;
{ цикл, пока массив не кончился и пока коды букв в просматриваемых элементах массива меньше введенных }
WHILE (r<>NIL) AND (r^.data<=q^.data) DO
r := r^.next;
{ вставка элемента }
q^.next := r^.next;
r^.next := q
Рис. 14.5. Сортировка динамических массивов.
Упорядоченность массива имеет еще одно важное преимущество: для поиска информации в упорядоченном массиве можно применить исключительно эффективный алгоритм двоичного поиска.
