Олег Деревенец - Песни о Паскале

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

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

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

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

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

begin

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

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

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

end;

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

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

Строковый тип 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.

Здесь показана внутренность строковой переменной со словом «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 ищет одну строку внутри другой, её объявление выглядит так:

function Pos(SubS: string; S: string): Integer;

Функция принимает два параметра:

• SubS – подстрока, которую ищут (то есть фрагмент строки);

• S – строка, в которой ищут.

Если искомый фрагмент SubS найден, функция возвращает его позицию – индекс первого символа SubS внутри строки S, а иначе возвращает ноль. Если строка S содержит несколько искомых фрагментов, возвращается индекс первого из них. Вот примеры.