Иное дело – чемпион. Дробя массив на мелкие участки, быстрый алгоритм уменьшает число прохождений всего массива до величины Log₂N. Поэтому его трудоемкость растёт пропорционально произведению N•Log₂N. Опять логарифм? Да, мы помним его по двоичному поиску. Поскольку логарифм числа растёт очень медленно, это объясняет чемпионство QuickSort (рис. 97).

Рис.97 – Рост трудоемкости сортировки с ростом размера массива

Итоги

• Двоичный поиск – это самый быстрый способ поиска, но он требует предварительной сортировки массива.

• Простые методы сортировки – BubbleSort и FarmSort – работают очень медленно, съедая всю экономию от двоичного поиска.

• QuickSort – это быстрый способ сортировки, который в сочетании с резвым двоичным поиском ускорит работу ваших программ.

А слабо?

А) Исследуйте процедуру быстрой сортировки в пошаговом режиме (задайте небольшой размер сортируемого массива). Обратите внимание на изменение границ сортируемой части.

Б) Определите количество повторных входов в процедуру QuickSort и выходов из нее. Объявите глобальную переменную, назовем её Level – «уровень». В главной программе, перед вызовом процедуры QuickSort, эту переменную надо обнулить, а внутри процедуры добавить следующие операторы.

В начале процедуры QuickSort:

begin

      Inc(Level); Writeln('Уровень на входе = ', Level);

В конце процедуры QuickSort:

      Dec(Level); Writeln('Уровень на выходе = ', Level);

end;

В) Если каждый вызов QuickSort делит массив примерно пополам, то наибольшее значение переменной Level должно составить приблизительно Log₂N (у нас размер массива задан константой CSize). Проверьте эту догадку компиляцией и запуском программы для нескольких значений CSize.

Г) В одном ряду вперемежку лежат дыни и арбузы. Могут ли фермеры отсортировать их за один проход ряда так, чтобы в начале оказались все дыни, а в конце ряда – все арбузы? Напишите такую программу, обозначив арбузы единицами, а дыни – нулями.

Глава 44

Строки

Строковый тип STRING известен нам с первых глав книги, без него компьютер не общался бы с нами на «человечьем» языке. Так изучим строки получше. В современных версиях Паскаля применяют несколько строковых типов, сейчас мы рассмотрим только короткие строки, введенные ещё в Borland Pascal (в новых версиях Паскаля этот тип называется ShortString).

Строка – особый род массива

С первого взгляда строка похожа на массив символов. Так ли это? – проверим. Известно, что строка может вместить до 255 символов. Объявим массив из 255 символов и сравним его размер с размером строки. Напомню, что функция SizeOf возвращает размер памяти, занимаемой переменной.

var S1 : array [1..255] of CHAR; { это массив из 255 символов }

      S2 : String;       { это строка длиной 255 символов }

begin

      Writeln (SizeOf(S1)); { печатает 255 }

      Writeln (SizeOf(S2)); { печатает 256 }

      Readln;

end.

Запустили программку? И что? Странно, но размер строки S2 оказался равным 256 байтам, что на единицу больше размера массива. Почему? Где прячется ещё один байтик? Ответ представлен на рис. 98.

Рис.98 – Размещение слова «PASCAL» в строковой переменной

Здесь показана внутренность строковой переменной со словом «PASCAL». Байты с 1-го по 6-й содержат буквы этого слова, а остальные байты не заняты. Но в начале массива обнаружен ещё один байт – с нулевым индексом. Он содержит число 6 – это длина слова «PASCAL». Значит, строковый тип – это массив со скрытым нулевым байтом, хранящим фактическую длину строки (эту длину возвращает функция Length).

Укороченные строки

Память – жилище переменных – всегда чем-нибудь занята. Даже пустая строка (нулевой длины) занимает 256 байтов памяти, и содержит что либо. Это «что либо» программисты называют мусором, а мусор никому не интересен. Так разумно ли отводить 256 байтов для строки, если большая её часть забита всяким вздором? Ведь память – ценный ресурс, и профессионал бережет её. К примеру, для строки, хранящей фамилию, вполне хватило бы и 20 байтов.

Это понимали и создатели Паскаля, они позаботились об экономии памяти. Строковые типы можно объявлять с указанием длины. Для этого после слова STRING в квадратных скобках указывают нужный размер строки, например:

type TStrA = string[11]; { строка для 11 символов }

      TStrB = string[31]; { строка для 31 символа }

var A : TStrA;       B : TStrB;

Здесь объявлены два строковых типа данных; первый из них вмещает до 11 символов, а второй – до 31. Соответственно переменная A будет занимать в памяти 12 байтов, а переменная B – 32 байта (с учетом нулевого байта). Согласитесь, – экономия солидная, особенно для массива из таких строк. Во всем остальном, кроме размера, короткие строки ничем не отличаются от переменных типа STRING.

А что случится при копировании длинной строки в короткую? А ничего, – не вместившиеся символы будут «отрублены». Следующая ниже программа «P_44_1» подтверждает это, испытайте её.

{ P_44_1 – укороченные строки }

var S1 : string;       { размер строки по умолчанию = 255 }

      S2 : string[5]; { размер укороченной строки = 5 символов }

begin

S1:='abc';       S2:='abcdefgh';

Writeln('Строка S1: Размер =', SizeOf(S1):4,' Длина = ', Length(S1):4,' Значение= '+S1);

Writeln('Строка S2: Размер =', SizeOf(S2):4,' Длина = ', Length(S2):4,' Значение= '+S2);

Writeln('Нулевой байт строки S1 = ', Byte(S1[0]));

Writeln('Нулевой байт строки S2 = ', Byte(S2[0]));

Readln;

end.

Операции со строками

Итак, уяснив внутреннее устройство строк, обратимся к связанным с ними операциям. Что мы умеем делать со строками сейчас? А вот что:

• вводить и выводить строки процедурами ввода и вывода;

• объединять несколько строк в одну (складывать);

• определять длину строки функцией Length;

• проверять строки на равенство и неравенство;

• обращаться к отдельным символам строки (доступ по индексу).

Учитывая важность строкового типа, разработчики Паскаля предусмотрели для строк ещё несколько процедур и функций, позволяющих:

• искать одну строку внутри другой;

• копировать часть строки в другую строку;

• вставлять одну строку внутрь другой;

• удалять часть символов из строки;

• сравнивать две строки в смысле алфавитного порядка.

Рассмотрим всё это подробней. Представленные далее объявления процедур и функций даны мною лишь для пояснений, их не надо вставлять в программы.

Поиск в строке (Pos)

Функция Pos ищет одну строку внутри другой, её объявление выглядит так: