y:= FArr[i];

FArr[i]:= FArr[j];

FArr[j]:= y;

i:= i + 1; j:= j – 1;

end;

until i > j;

if l < j then QSort (l, j);

if i < r then QSort (i, r);

end;

begin {QuickSort};

if xMode<>0

then SortMode:= xMode;

QSort (1, Size);

if xMode=0 then // Поменяем режим сортировки

begin

if SortMode = 1

then SortMode:=2 else SortMode:=1;

end;

end;

Оценка эффективности

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь меняются местами наиболее удалённые друг от друга элементы массива.

· Лучший случай. Для этого алгоритма самый лучший случай – если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C_N = 2C_N/2 +N. Это дало бы наименьшее время сортировки.

· Среднее. Даёт в среднем O (n log n ) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.

· 2C_N/2 покрывает расходы по сортировке двух полученных подмассивов; N – это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно C_N = N lg N.

· Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.

· Худший случай даёт O (n ²) обменов, но количество обменов и, соответственно, время работы – это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов.

Да

5. Руководство пользователя

Данное программное обеспечение имеет интуитивно понятный интерфейс и использует все возможности среды Delphi.

Программа имеет пять вкладок. При первоначальном запуске активируется первая – вкладка «Квартиры» (см. рис. 3).