- •Аннотация
- •Условия использования
- •Оглавление
- •Содержание
- •Только для взрослых
- •Десять лет спустя
- •Чему нас учат семья и школа?
- •Крошка сын к отцу пришел
- •Азбучные истины
- •Что я могу еще сказать?
- •Благодарности
- •Детям до 16-ти
- •Глава 1 Путь далек у нас с тобою…
- •Компьютер
- •Компилятор
- •Личный багаж
- •Компьютерная литература
- •В здоровом теле – здоровый дух
- •Вместе весело шагать по просторам!
- •Повторение – мать учения
- •Соглашения
- •Итоги
- •Глава 2 Вместо теории
- •Миф о думающих машинах
- •Загадочные коды
- •Языки программирования и компиляторы
- •Следующий шаг –
- •Итоги
- •Глава 3 Консольный интерфейс
- •Что такое интерфейс?
- •Консольный интерфейс
- •Прикосновение к консольному интерфейсу
- •А почему не «окна»?
- •Итоги
- •Глава 4 Оружие – к бою!
- •Оружейный прилавок
- •Free Pascal
- •Настройка ярлыка
- •Free Pascal
- •Установка справочной системы
- •Итоги
- •Глава 5 Программа номер один
- •Постановка задачи
- •Создание файла
- •Наполнение файла
- •Компиляция
- •Процедура вывода (печати)
- •Запуск программы
- •Итоги
- •Глава 6 Подготовка к следующему штурму
- •Еще об исходных файлах
- •Управление окном редактора
- •Борьба с ошибками
- •Итоги
- •Глава 7 Развиваем успех
- •Операторы и разделители
- •Программа, стой!
- •Алгоритмы
- •Блок-схемы
- •Итоги
- •Глава 8 Постоянные и переменные
- •Константы
- •Идентификаторы
- •Переменные
- •Ввод и вывод данных
- •Итоги
- •А слабо?
- •Глава 9 Переменные: продолжение знакомства
- •Представьтесь, пожалуйста!
- •Из пустого в порожнее
- •Сцепление строк
- •Инициализация переменных
- •Типизированные константы
- •Итоги
- •А слабо?
- •Глава 10 Условный оператор
- •Стой! Кто идет?
- •Вопрос ребром
- •Пост номер один
- •Неполный условный оператор
- •Пост номер два
- •Итоги
- •А слабо?
- •Глава 11 Операторный блок
- •Операторные скобки
- •Красиво жить не запретишь
- •Комментарии
- •Итоги
- •Глава 12 Цикл с проверкой в конце
- •Подтянем дисциплину
- •Нанимаем репетитора
- •Вежливый часовой
- •Досрочный выход из цикла
- •Итоги
- •Глава 13 Правда и кривда
- •Есть ли жизнь на Марсе?
- •Информация и её мерило
- •Булевы переменные
- •Ввод и вывод булевых данных
- •Логические выражения
- •С высоты птичьего полета
- •Парад логических операций
- •Итоги
- •А слабо?
- •Глава 14 Дважды два – четыре
- •Поможем братьям нашим меньшим
- •Числа и действия с ними
- •Алгоритм экзаменатора
- •Экзаменатор, первый вариант
- •Итоги
- •А слабо?
- •Глава 15 Айда в Монте-Карло!
- •Куда ни глянь – то процедура, то функция!
- •Госпожа удача
- •Итоги
- •А слабо?
- •Глава 16 Делу время, а потехе час
- •Потемкинская лестница
- •Итоги
- •А слабо?
- •Глава 17 И вновь за парту
- •Цикл со счетчиком
- •Итоги
- •Глава 18 Аз, Буки
- •Символьный тип данных
- •Индексация
- •Длина строки
- •Распечатка строки
- •Итоги
- •Глава 19 Процедуры и функции: разделяй и властвуй
- •Снежный ком
- •Описание процедур
- •Процедуры с параметрами
- •Итоги
- •Глава 20 Процедуры: первый опыт
- •Мухи – налево, котлеты – направо!
- •Сверху вниз
- •Первые раны
- •Глобальные и локальные
- •Локально – это разумно!
- •Неподдающаяся строка
- •Итоги
- •Глава 21 Отладка
- •Отладчик
- •Жучки, вылезайте!
- •Ссылка на переменную
- •Итоги
- •Глава 22 О передаче параметров
- •Процедура обмена
- •Замена символов в строке
- •О передаче строк
- •Итоги
- •Глава 23 Функции
- •Объявление функции
- •Пример функции
- •Подсчет символов в строке
- •Возврат строк
- •Когда результат не важен
- •Неявная переменная Result
- •Итоги
- •Глава 24 Криптография
- •Секреты Юлия Цезаря
- •Суть проблемы
- •О кодировании символов
- •Чудесные превращения
- •Шифрование символа
- •Расшифровка символа
- •Итоги
- •А слабо?
- •Глава 25 Текстовые файлы
- •Файлы хорошие и разные
- •Формат текстовых файлов
- •Доступ к текстовым файлам
- •Чтение из файла
- •Последовательный доступ к файлу
- •Самореклама
- •Цикл с проверкой в начале
- •Итоги
- •Глава 26 Я не читатель, — я писатель!
- •Запись в текстовый файл
- •Пример записи в файл
- •Завершение шпионского проекта
- •Итоги
- •А слабо?
- •Глава 27 Дайте кораблю минутный отдых!
- •Ошибка ошибке рознь
- •Фатальные ошибки
- •«Простительные» ошибки
- •Опции компилятора
- •Обработка ошибок ввода-вывода
- •Директивы компилятора
- •Директиву – в студию!
- •Парад директив
- •Итоги
- •А слабо?
- •Глава 28 Редактор и справочная система
- •Небьющиеся окна
- •Буфер обмена
- •Справочная система
- •Итоги
- •Глава 29 Читайте по-новому
- •Полицейская база данных, версия 1
- •Полицейская база данных, версия 2
- •Итоги
- •Глава 30 Журнальная история
- •Статистика знает все?
- •Строим планы
- •Барабаним по клавишам
- •Первый блин
- •Блин второй
- •Спецификатор ширины поля
- •«Развесные» числа
- •Итоги
- •Глава 31 Финал журнальной истории
- •Буква за буквой
- •Нелишняя предосторожность
- •Достройка программы
- •Испытание
- •Итоги
- •Глава 32 Порядковые типы данных
- •Типы данных: простые и сложные
- •Целое братство
- •Капля, переполняющая чашу
- •Инкремент и декремент
- •Диапазоны
- •Перечисления
- •Порядковые типы
- •Разумный контроль
- •Итоги
- •Глава 33 Вещественные числа
- •Изображение вещественных чисел
- •Вывод вещественных чисел
- •Типы вещественных чисел
- •Сравнение вещественных чисел
- •Типы данных пользователя
- •Совместимость и преобразование типов
- •Размеры переменных и типов данных
- •Итоги
- •Глава 34 Структура программы
- •Управляющие структуры
- •Структура программы
- •Структура процедур и функций
- •Обмен данными с подпрограммами
- •Встроенные процедуры и функции
- •Что дальше?
- •Итоги
- •А слабо?
- •Глава 35 Множества
- •В директорском кабинете
- •Первым делом, первым делом – оцифровка
- •Множества глазами математика
- •Числовые множества
- •Мощность множества, полные и неполные множества
- •Итоги
- •Глава 36 Множества в Паскале
- •Объявление множеств
- •Присвоение значений множествам
- •Операции с множествами
- •Сравнение множеств
- •Проверка на вхождение элемента в множество (операция IN)
- •Решение директорской задачи
- •Итоги
- •А слабо?
- •Глава 37 Ввод и вывод множеств
- •Вывод множества в текстовый файл
- •Ввод множества из текстового файла.
- •Директорская задача, первый вариант
- •Директорская задача, второй вариант
- •Итоги
- •Глава 38 Множества «в бою»
- •Активисты, шаг вперед!
- •Подвиг контрразведчика
- •В тридевятом царстве
- •Решето Эратосфена
- •Мелочь, а приятно
- •Итоги
- •А слабо?
- •Глава 39 Командная игра (массивы)
- •Снежная лавина
- •А где же волшебная палочка?
- •Массивы вокруг нас
- •Объявление массивов
- •Доступ к элементам (индексация)
- •Ввод и вывод массивов
- •Ошибки индексации
- •Итоги
- •Глава 40 Пристрелка на знакомых мишенях
- •Вопрос-ответ – добиваемся гибкости
- •Полицейская база данных – ускоряем поиск
- •Еще раз о статистике
- •Итоги
- •Глава 41 По порядку, становись!
- •Пиратская справедливость
- •Пузырьковая сортировка
- •Электронная делёжка
- •Возвращение на футбольное поле
- •Итоги
- •Глава 42 Кто ищет, тот всегда найдет
- •Где эта улица, где этот дом?
- •Последовательный поиск
- •Двоичный поиск
- •Исследование двоичного поиска
- •Ах, время, время!
- •Логарифмы? Это просто!
- •Итоги
- •Глава 43 Сортировка по-взрослому
- •Сортировка выбором
- •Быстрая сортировка
- •Процедура быстрой сортировки
- •О рекурсии и стеке
- •Алгоритмы, на старт!
- •Итоги
- •Глава 44 Строки
- •Строка – особый род массива
- •Укороченные строки
- •Операции со строками
- •Подсчет слов в строке
- •Контекстная замена
- •Итоги
- •Глава 45 Очереди и стеки
- •Вовочка в потоке событий
- •Танцевальный кружок
- •Скитания товарного вагона
- •Сортировочная горка
- •Итоги
- •Глава 46 Огромные числа
- •Сколько звезд на небе?
- •Сложение «в столбик» никто не отменял
- •Великая стройка
- •Длинная арифметика
- •Итоги
- •А слабо?
- •Глава 47 Системы счисления
- •Из тьмы веков
- •Число и его изображение
- •Десятичная система
- •Двоичная система
- •Шестнадцатеричная система
- •Другие системы счисления
- •Изображение числа в заданной системе счисления
- •Обратное преобразование
- •Итоги
- •Глава 48 Железная логика
- •Два взгляда на компьютерные «кирпичики»
- •Логические операции в регистрах
- •Сдвиги влево и вправо
- •Итоги
- •Глава 49 Сложные массивы
- •На поклон к Науке
- •Имперское строительство
- •Крестики-нолики
- •Итоги
- •А слабо?
- •Глава 50 Неспортивные рекорды (записи)
- •Кушать подано!
- •Записи
- •Второй тайм
- •Дополнительное время
- •Итоги
- •Глава 51 Указатели в море памяти
- •Погружение в оперативную память
- •«Планировка» памяти
- •Указатели, первое знакомство
- •Объявление указателей
- •Копирование указателей, пустой указатель
- •Сравнение и проверка указателей
- •Разыменование указателей
- •Нетипичный указатель
- •Примеры с указателями
- •Итоги
- •Глава 52 Динамические переменные
- •Аппетит является к обеду
- •Одолжите памяти немножко!
- •Выделение памяти
- •Освобождение памяти
- •Предупреждён – значит, вооружен
- •Итоги
- •Глава 53 Массив указателей
- •Базу данных – в кучу
- •Сортировка массива указателей
- •Итоги
- •А слабо?
- •Глава 54 Односвязные списки
- •Чудесное сочетание
- •Проблема курицы и яйца
- •Вяжем список
- •Распечатка списка
- •Поиск в несортированном списке
- •Сортированные списки
- •Поиск в сортированном списке
- •Итоги
- •Глава 55 Слова, слова, слова…
- •Частотный анализ текста
- •Слово за слово
- •Структура записи
- •Алгоритм
- •А слабо?
- •Глава 56 И снова очереди, и снова стеки…
- •Шутить изволите?
- •Танцуют все!
- •Итоги
- •Глава 57 Графомания
- •Видимое представление графа
- •Внутреннее представление графа
- •Ввод и вывод графа
- •Итоги
- •Глава 58 По графу шагом марш!
- •Империя номер два
- •Структура узла
- •В рассыпную!
- •Аты-баты
- •Итоги
- •Глава 59 Крупные проекты
- •О модулях и разделении труда
- •Модули
- •Дробление модуля – «смертельный» номер
- •Компиляция проекта
- •Инициализация модуля
- •Структура модуля
- •О совпадении имен
- •Сборочный цех
- •Фирменные библиотеки
- •Динамически загружаемые библиотеки (DLL)
- •Итоги
- •Глава 60 Мелкие хитрости
- •Включаемые файлы
- •Условная компиляция
- •Итоги
- •Глава 61 «Кубики» программиста (ООП)
- •Фокус-покус
- •Вместо паяльника
- •На трех китах
- •Инкапсуляция
- •Наследование
- •Приборостроение
- •Гражданское строительство
- •Динамические объекты
- •Полиморфизм
- •Сокрытие полей и методов
- •Итоги
- •Глава 62 Самое интересное только начинается!
- •Крупицы мастерства
- •Программисты, на старт!
- •Приложение А Установка и настройка IDE Borland Pascal
- •Borland Pascal, состав дистрибутива
- •Borland Pascal
- •Установка
- •Организация рабочей папки
- •Создание и настройка ярлыка
- •Пробный запуск
- •Предварительная настройка
- •Русификация консольного окна
- •Turbo Pascal School Pak
- •Приложение Б Консольная программа в среде Delphi
- •Создание пустого консольного приложения
- •Настройка и сохранение консольного приложения
- •Русификация консольного приложения
- •Приложение В Особенности IDE Pascal ABCNet
- •Приложение Ж Директивы управления компиляцией
- •Приложение З Назначение пунктов меню
- •Приложение И Стандартная кодировка символов MS-DOS
- •Приложение К Некоторые встроенные процедуры и функции
- •Приложение М Пример олимпиадной задачи
- •Библиография
Глава 43 Сортировка по-взрослому
в эту же процедуру, но в другое место — следующее за вызовом. Окончательный выход из процедуры в главную программу случится только по завершении сортировки всего массива!
Напрашивается вопрос: какова судьба локальных переменных и параметров при повторных входах в процедуру? Ведь они изменятся, а это должно нарушить работу процедуры. Параметры и локальные переменные действительно изменяются, но это не путает алгоритм. Почему?
Разгадка в том, что при каждом входе в процедуру для её параметров и локальных переменных выделяется новый участок памяти. Теперь это будут уже другие параметры и локальные переменные, но с прежними названиями. Однако предыдущие их значения не теряются, а сохраняются в памяти, называемой стеком
(Stack).
Что такое стек и как он работает? Случалось ли вам паковать рюкзак или глубокую сумку? Тогда вы знакомы со стеком. Все, что уложено в рюкзак, будет извлекаться из него в обратном порядке. Так же устроен и стек: при каждом вызове процедуры память для параметров и локальных переменных выделяется на его вершине. Эти новые значения временно закрывают предыдущие значения параметров, и так происходит при каждом входе в процедуру.
При выходе из неё последние значения параметров и локальных переменных удаляются с вершины стека, и тогда вновь открываются ранее скрытые. Так процедура «вспоминает» о неоконченной работе, и продолжает действия с параметрами, сохраненными в стеке ранее. В некоторый момент стек пустеет (когда все вещи из рюкзака вынуты), и тогда происходит окончательный выход из процедуры в главную программу.
Механизм стековой памяти заложен в конструкцию процессора, и он не требует участия программиста. Стек используется для любых процедур и функций, а не только рекурсивных.
Но стоп! О стеке поговорим позже, а сейчас займемся делом. Введите программу P_43_2 и убедитесь в её правильной работе.
Алгоритмы, на старт!
Теперь в нашем распоряжении есть три процедуры сортировки, не устроить ли состязание между ними? На старт вызываются:
∙BubbleSort — «пузырьковая» сортировка,
∙SelectionSort — сортировка выбором,
∙QuickSort — быстрая сортировка.
Время «спортсменов» мы будем засекать не по часам. И вы знаете, почему: мы сравниваем алгоритмы, а не компьютеры. В 42-й главе, где сравнивались
324
Глава 43 Сортировка по-взрослому
алгоритмы поиска, мы оценивали время по количеству выполненных шагов. Поступим и здесь похожим образом. Вспомним, в чем состоит сортировка? — в сравнениях и перестановках. И много-много раз... Значит, трудоемкость сортировки можно оценить количеством этих двух операций — сравнений и перестановок, надо их только посчитать.
Что ж, дело нехитрое, сейчас посчитаем, — перед вами программа для наших опытов (P_43_3). Количество сравнений и перестановок будем накапливать в переменных C1 и C2. Обратите внимание на их тип — EXTENDED, — это переменные действительного типа. Почему не длинное целое? При сортировке больших массивов может потребоваться столь много операций, что не хватит целочисленной переменной, — она переполнится, «лопнет», и результат исказится. Потому выбран тип EXTENDED.
Далее в программе следуют знакомые вам процедуры сортировки, — это наши «спортсмены». В их тела «вживлены» дополнительные операторы для подсчета сравнений (C1) и перестановок (C2), — они мною подчеркнуты. Наконец, главная программа, — она вызывает по очереди каждую из процедур и печатает количество сравнений и перестановок. Здесь равные условия для соревнующихся создаются загодя сформированным случайным массивом Arr0, который копируется в массив Arr перед каждой сортировкой.
Вам осталось лишь задать размер массива константой CSize, скомпилировать и запустить программу.
325
|
|
|
|
|
Глава 43 |
|
|
|
|
|
|
Сортировка по-взрослому |
|
|
|
|
|
|||
|
{ P_43_3 |
- Сравнение алгоритмов сортировки } |
|
|||
|
const CSize=100; |
{ размер массивов } |
|
|||
|
type |
TNumbers = array [1..CSize] of Integer; |
|
|||
|
var |
Arr0 : TNumbers; |
{ несортированный массив-заготовка } |
|
||
|
|
Arr |
: TNumbers; |
{ сортируемый массив } |
|
|
|
|
C1, C2 : extended; |
{ счетчики сравнений и перестановок } |
|
{ BubbleSort "пузырьковая" сортировка } procedure BubbleSort(var arg: TNumbers); var i, j, t: Integer;
begin
for i:= 1 to CSize-1 do
for j:= 1 to CSize-i do begin C1:=C1+1; { подсчет сравнений } if arg[j] > arg[j+1] then begin
C2:=C2+1; { подсчет перестановок }
t:= arg[j]; arg[j]:= arg[j+1]; arg[j+1]:= t;
end;
end;
end;
{ SelectionSort – сортировка выбором } procedure SelectionSort(var arg: TNumbers); var L, R, T: Integer;
begin
for L := 1 to CSize-1 do
for R := CSize downto L+1 do begin C1:=C1+1; { подсчет сравнений } if arg[L] > arg[R] then begin
C2:=C2+1; { подсчет перестановок }
T:= arg[L]; arg[L]:= arg[R]; arg[R]:= T;
end;
end;
end;
{ QuickSort – Быстрая сортировка }
procedure QuickSort(var arg: TNumbers; aL, aR: Integer); var
L, R, Mid, T: Integer;
begin |
|
L:= aL; |
R:= aR; |
326
Глава 43 Сортировка по-взрослому
Mid:= (arg[L] + arg[(L + R) div 2] + arg[R]) div 3; repeat
while arg[L] < Mid do begin L:=L+1; C1:=C1+1 end; while arg[R] > Mid do begin R:=R-1; C1:=C1+1 end; if L <= R then begin
if arg[L]>arg[R] then begin
C2:=C2+1; { подсчет перестановок }
t:= arg[L]; arg[L]:= arg[R]; arg[R]:= t;
end;
L:=L+1; R:=R-1;
end;
until L > R;
if R > aL then QuickSort(arg, aL, R); if L < aR then QuickSort(arg, L, aR);
end;
const CFName = 'P_43_3.out';
var i: integer; |
|
|
|
F: text; |
|
|
|
begin |
|
|
|
Assign(F,CFName); |
Rewrite(F); |
|
|
for i:=1 to CSize do Arr0[i]:=1+Random(10000); |
|||
Writeln(F, 'Размер массива = ', CSize); |
|
||
Writeln(F, 'Алгоритм |
Количество |
Количество'); |
|
Writeln(F, 'сортировки |
сравнений |
перестановок'); |
|
C1:=0; C2:=0; |
{ очистить счетчики } |
|
|
Arr:= Arr0; |
{ заполнить сортируемый массив } |
||
BubbleSort(Arr); |
|
|
|
Writeln(F, 'Пузырьковая:', C1:12:0, C2:12:0); |
|||
C1:=0; C2:=0; |
{ очистить счетчики } |
|
|
Arr:= Arr0; |
{ заполнить сортируемый массив } |
||
SelectionSort(Arr); |
|
|
|
Writeln(F, 'Выбором |
|
:', C1:12:0, C2:12:0); |
|
C1:=0; C2:=0; |
{ очистить счетчики } |
|
|
Arr:= Arr0; |
{ заполнить сортируемый массив } |
||
QuickSort(Arr, 1, CSize); |
|
||
Writeln(F, 'Быстрая |
|
:', C1:12:0, C2:12:0); |
|
Writeln('OK !'); Readln; |
|
||
Close(F); |
|
|
|
end. |
|
|
|
327
Глава 43 Сортировка по-взрослому
Вот что получилось для массива из 1000 элементов.
Размер массива = 1000
Алгоритм |
|
Количество |
Количество |
сортировки |
|
сравнений |
перестановок |
Пузырьковая: |
499500 |
248061 |
|
Выбором |
: |
499500 |
80887 |
Быстрая |
: |
5871 |
2417 |
Я провел три опыта с массивами из 100, 1000 и 10000 элементов, а результаты занес в две таблички. Что сказать по этому поводу?
Табл. 9 – Количество сравнений в разных методах сортировки
Размер массива |
«Пузырьковая» |
Сортировка |
Быстрая |
|||||||
сортировка |
выбором |
сортировка |
||||||||
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
100 |
|
4 |
950 |
|
4 |
950 |
|
417 |
|
1 |
000 |
|
499 |
500 |
|
499 |
500 |
5 |
871 |
|
10 |
000 |
49 |
995 |
000 |
49 |
995 |
000 |
79 |
839 |
Из табл. 9 следует, что по количеству сравнений сортировка выбором не лучше «пузырька». Зато быстрая сортировка оправдывает свое название, — выигрыш составляет от 10 до 600 раз! И чем больше массив, тем заметней этот разрыв.
Табл. 10 – Количество перестановок в разных методах сортировки
Размер массива |
«Пузырьковая» |
Сортировка |
Быстрая |
|||||||
сортировка |
выбором |
сортировка |
||||||||
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
100 |
|
2 |
305 |
|
|
805 |
|
141 |
|
1 |
000 |
|
248 |
061 |
|
80 |
887 |
2 |
417 |
|
10 |
000 |
24 |
903 |
994 |
6 |
154 |
077 |
31 |
011 |
А что с количеством перестановок (табл. 10)? Здесь сортировка выбором все же обгоняет «пузырек», — преимущество составляет от 3-х до 4-х раз. Так что фермеру Лефту в сметливости не откажешь. И все же этому «спортсмену» далеко до изобретения Райта! В сравнении с «пузырьком» выигрыш стократный, и стремительно растет с ростом размера массива. Слава, слава фермеру Райту! Кстати, историки выяснили его настоящее имя: им оказался англичанин Чарльз Хоар.
328
Глава 43 Сортировка по-взрослому
BubbleSort
SelectionSort |
QuickSort |
Рис. 96 – Кто здесь чемпион?
Итак, с чемпионом все ясно (рис. 96), но в чем секрет его успеха? Сравним чемпиона с отставшими. Чем больше массив, тем дольше он сортируется, — это справедливо для любого алгоритма. Долгие методы обрабатывают весь массив N раз, где N — размер массива. Поэтому их трудоемкость пропорциональна произведению N•N. По этой формуле вычисляют площадь квадрата, потому такую зависимость называют квадратичной.
Иное дело — чемпион. Дробя массив на мелкие участки, быстрый алгоритм уменьшает число прохождений всего массива до величины Log2N. Поэтому его трудоемкость растет пропорционально произведению N•Log2N. Опять логарифм? Да, мы помним его по двоичному поиску. Поскольку логарифм числа растет очень медленно, это объясняет чемпионство QuickSort (рис. 97).
Трудоемкость
Квадратичная
N x N
Разница в трудоемкости
N x Log2N
Размер массива N
Рис. 97 – Рост трудоемкости сортировки с ростом размера массива
329