Песни о Паскале — страница 59 из 112

Табл. 8 – двоичные логарифмы некоторых чисел

N	Log2 N	N	Log2 N	N	Log2 N	N	Log2 N
2	1	32	5	512	9	8192	13
4	2	64	6	1024	10	16384	14
8	3	128	7	2048	11	32768	15
16	4	256	8	4096	12	65536	16

По таблице можно оценить как среднее, так и худшее время двоичного поиска: среднее время равно двоичному логарифму от размера массива, а худшее – на единицу больше.

А как определить логарифмы других чисел, например, числа 50? Поскольку оно лежит между 32 и 64, его логарифм должен быть где-то между 5 и 6? Так оно и есть: логарифм 50 равен приблизительно 5,64 (это я на калькуляторе посчитал). Но, поскольку мы применяем логарифмы для подсчета шагов поиска, то погрешностью в доли шага можно пренебречь. К чему мелочиться? Будем считать, что логарифм числа 50 тоже равен 6. Мало того, назначим это значение логарифма всем числам в промежутке от 33 до 64.

На рис. 93 сопоставлен рост числа с ростом его логарифма. Когда число увеличивается вдвое, его логарифм возрастает лишь на единицу. Вот почему с ростом размера массива время двоичного поиска растет так медленно (что очень радует нас!).

Рис.93 – Сравнение времени линейного и двоичного поиска

Итоги

• Компьютерные базы данных (БД) содержат разнородную информацию, отдельные элементы которой связаны общим индексом.

• Поиск в массиве состоит в определении индекса искомого элемента; зная индекс, можно извлечь всю прочую информацию о нужном объекте.

• Для поиска применяют два способа: последовательный перебор и двоичный поиск.

• Последовательный перебор (линейный поиск) очень прост, но время поиска пропорционально размеру массива, что для больших объёмов данных бывает неприемлемо.

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

А слабо?

А). Будет ли линейный поиск работать быстрее в сортированном массиве? Проверьте на практике.

Б) Сколько шагов двоичного поиска потребуется в массиве из миллиона элементов? А из миллиарда? Сравните с трудоемкостью линейного поиска.

В) Напишите полицейскую базу данных, содержащую номера автомобилей и сведения о владельцах. Данные должны вводиться из файла, каждая строка которого содержит номер автомобиля и сведения о владельце, например:

123 Горбунков С.С., ул. Тепличная, д. 21, тел. 11-22-33
35 Стелькин И.Н., ул. Тенистая, д. 5, тел. 33-22-11

Примените массивы и учтите опыт обработки классного журнала.

Г) Отсортируйте полицейскую базу данных и напишите программу для двоичного поиска в ней.

Д) Папа Карло опасался Буратино, и прятал спички в сейфе. Код замка из четырех цифр он доверил лишь своему приятелю – честному малому Джузеппе, который не поддавался ни на какие уговоры деревянного мальчишки. Тогда тот пустился на хитрость. Ладно, – предложил Буратино, – не можешь открыть мне код, – не надо. Давай тогда в игру сыграем: я буду спрашивать, а ты отвечай только «да» или «нет». Первый вопрос был таким: код замка больше 5000? Через несколько минут Буратино уже рылся в папином сейфе. Сделайте программу для быстрого угадывания числа методом Буратино. Роль Буратино (угадывающего) должен исполнять компьютер.

Глава 43Сортировка по-взрослому

Наше новейшее открытие – быстрый, как ракета, двоичный поиск. Но работает он лишь в сортированном массиве. Так в чем вопрос? Разве сортировка «пузырьком» нам не покорилась? Увы! «Пузырек» насколько же нетороплив, насколько и прост. Много ли проку от быстрого поиска, если выигрыш времени съест сортировка? Так ускорим её!

"Фермерская" сортировка

Отчего так медленно «всплывают пузырьки»? Не оттого ли, что мы сравниваем и обмениваем соседние элементы? Уяснить тонкости сортировки нам поможет правдивая история из жизни двух друзей.

Некий фермер — левша по имени Лефт — удостоился чести поставлять арбузы к столу Его Величества. Желая превзойти конкурентов и сохранить за собой королевский заказ, Лефт решил отбирать из урожая самые крупные ягоды (арбуз — это ягода). Выложив арбузы в длинный ряд, Лефт занялся их сортировкой. Работая в одиночку, он применил единственный доступный ему способ — «пузырёк». После трёх дней мучительных сравнений и перестановок Лефт понял, что без помощника ему не обойтись.

Сортировать урожай следующего года он позвал своего соседа и приятеля по имени Райт. Вдвоем они стали работать новым, придуманным Лефтом способом. Лефт стал у первого арбуза, а его приятель Райт побежал в конец ряда. Оттуда Райт стал продвигаться навстречу Лефту, сравнивая арбузы с тем, у которого прохлаждался Лефт (арбузы взвесили заранее, а вес нацарапали на кожуре). Когда Райт находил арбуз легче того, у которого стоял Лефт, их меняли местами: друзья просто швыряли арбузы друг другу.

Наконец Райт вплотную подошел к Лефту, и тогда на месте, где стоял Лефт, оказался самый легкий арбуз. Лефт шагнул ко второму арбузу, а Райт снова побежал в конец ряда, и всё повторилось. По окончании второго цикла на втором месте в ряду, где стоял Лефт, очутился второй по величине арбуз. Теперь первые два арбуза были отсортированы, и Лефт соизволил шагнуть к третьему. К сумеркам, совершив N-1 таких циклов, друзья закончили работу. Лефт, свежий как огурчик, ступил, наконец, к последнему арбузу, недоумевая, отчего его приятель Райт едва волочит ноги?

Рис. 94 – Сортировка массива с встречным движением индексов

Пусть друзья отдыхают, а мы поразмыслим, много ли толку в изобретении Лефта? Поскольку при каждом обмене арбузы перемещались на большое расстояние, то возможно, что таких обменов потребовалось меньше, чем при «пузырьке». Пока это лишь догадка, которую предстоит проверить. А пока соорудим и испытаем процедуру сортировки, придуманную Лефтом, назовём её FarmSort — «фермерская» сортировка.

Программа с процедурой перед вами. Введите её и проверьте, действительно ли процедура Лефта сортирует массив, не ошибся ли фермер?

{ P_43_1 проверка "фермерской" сортировки }

const
      CSize=10; { размер массива }
type
      TNumbers = array [1..CSize] of Integer; { тип для массива }
var
      Arr : TNumbers;       { сортируемый массив }

      { Процедура "фермерской" сортировки }
procedure FarmSort(var arg: TNumbers);
var L, R, T: Integer;
begin
for L := 1 to CSize-1 do
      { Сдвигаем правый индекс влево }
      for R := CSize downto L+1 do begin
      { Если левый элемент оказался больше правого,
      то меняем элементы местами }
      if arg[L] > arg[R] then begin
      { Перестановка элементов массива }
      T:= arg[L]; arg[L]:= arg[R]; arg[R]:= T;
      end;
      end;
end;

      { Процедура распечатки массива, arg – строка сообщения }
procedure ShowArray(const arg: string);
var i: integer;
begin
      Writeln(arg);
      for i:=1 to CSize do Writeln(Arr[i]);
      Readln;
end;
var i: integer;
begin
      { Заполняем массив случайными числами }
      for i:=1 to CSize do Arr[i]:=1+Random(1000);
      ShowArray('До сортировки:');
      FarmSort(Arr);
      ShowArray('После сортировки:');
end.

Быстрая сортировка

«Здесь что-то не так, – стучало в голове Райта, пока он челноком мотался из конца в конец ряда, – почему я бегаю, а он стоит? Это несправедливо! К следующему урожаю я придумаю лучший способ сортировки!».

Через год Лефт опять позвал Райта на помощь.

Хорошо, – согласился Райт, – но теперь командовать буду я.

Пройдясь вдоль ряда, Райт прикинул на глазок вес среднего по величине арбуза. «Запомни этот вес, – сказал он Лефту, – и ступай к началу ряда», – а сам отправился в другой конец. «Теперь иди ко мне, пока не найдешь арбуз тяжелее указанного мною». Лефт так и сделал, – найдя первый такой арбуз, он остановился и крикнул об этом Райту. «Теперь моя очередь!» – отозвался Райт и стал двигаться навстречу Лефту, попутно отыскивая арбуз, легче среднего. Дойдя до такого арбуза, Райт остановился и скомандовал: «Меняем арбузы местами!», – и друзья швырнули арбузы друг дру