Песни о Паскале - [93]

Табл. 10 – Количество перестановок в разных методах сортировки

Размер массива	Пузырьковая сортировка	Фермерская сортировка	Быстрая сортировка
100	2 305	805	141
1 000	248 061	80 887	2 417
10 000	24 903 994	6 154 077	31 011

А что с количеством перестановок (табл. 2)? Здесь «фермерская» сортировка всё же в 3—4 раза обгоняет «пузырёк». Так что фермеру Лефту в сметливости не откажешь. И всё же этому «спортсмену» далеко до изобретения Райта! В сравнении с «пузырьком» выигрыш стократный, и стремительно растёт с ростом размера массива. Слава, слава фермеру Райту! Кстати, историки выяснили его настоящее имя: это англичанин Чарльз Хоар.

Рис.96 – Кто здесь чемпион?

Итак, с чемпионом все ясно (рис. 96), но в чем секрет его успеха? Сравним чемпиона с отставшими. Чем больше массив, тем дольше он сортируется, – это справедливо для любого алгоритма. Долгие методы обрабатывают весь массив N раз, где N – размер массива. Поэтому их трудоемкость пропорциональна произведению N•N. По этой формуле вычисляют площадь квадрата, и такую зависимость называют квадратичной.

Иное дело – чемпион. Дробя массив на мелкие участки, быстрый алгоритм уменьшает число прохождений всего массива до величины 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 в квадратных скобках указывают нужный размер строки, например: