Песни о Паскале

Деревенец Олег Виленович

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; { заполнить сортируемый массив }

FarmSort(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.

Вот что получилось для массива из 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

А

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

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

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

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

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

Итоги

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

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

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

А слабо?