Каждый элемент одного вектора занимает 16 байт памяти. Соответственно FArr будет занимать (100*100)*16=160000 байт.
Логическая схема структуры вектора имен FNames:
0
1
2
…
101
3
100
Каждый элемент вектора занимает 101 байт памяти. Соответственно вектор FNames будет занимать 100*101 =10100 байт.
Основной операцией обработки структуры в данном программном обеспечении является сортировка QuickSort (по заданию на курсовое проектирование).
Быстрая сортировка (quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си - широко известный алгоритм сортировки, разработанный английским Информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем О (n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.
Алгоритм
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного - справа от него. Обычный алгоритм операции:
1. Два индекса - l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
2. Вычисляется индекс опорного элемента m.
3. Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.
4. Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше опорного.
5. Если r = l - найдена середина массива - операция разделения закончена, оба индекса указывают на опорный элемент.
6. Если l < r - найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.
Этот алгоритм в применении к нашему вектору FArr реализован следующи методом класса TVector:
// Процедура сортировки вектора по индексу SortId с режимом xMode
// xMode = 1 - по возрастанию
// xMode = 2 - по убыванию
// xMode = 0-использовать текущий режим SortMode и затем поменять его
procedure TVector. Sort (xMode: integer = 0);
procedure QSort (l, r: Integer);
function Less (var x, y: Variant): boolean;
begin
if (X < Y) and (SortMode=1) // по возрастанию
then Less:=true
else Less:=false;
end;
var
i, j, x: integer;
y: TVarMas; //Variant;
i:= l; j:= r; x:= (l+r) DIV 2;
repeat
while Less (FArr[i] [SortId], FArr[x] [SortId]) do i:= i + 1;
while Less (FArr[x] [SortId], FArr[j] [SortId]) do j:= j - 1;
if i <= j then
y:= FArr[i];
FArr[i]:= FArr[j];
FArr[j]:= y;
i:= i + 1; j:= j - 1;
until i > j;
if l < j then QSort (l, j);
if i < r then QSort (i, r);
begin {QuickSort};
if xMode<>0
then SortMode:= xMode;
QSort (1, Size);
if xMode=0 then // Поменяем режим сортировки
if SortMode = 1
then SortMode:=2 else SortMode:=1;
Оценка эффективности
QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка»), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь меняются местами наиболее удалённые друг от друга элементы массива.
· Лучший случай. Для этого алгоритма самый лучший случай - если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения CN = 2CN/2+N. Это дало бы наименьшее время сортировки.
· Среднее. Даёт в среднем O (n log n) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
· 2CN/2 покрывает расходы по сортировке двух полученных подмассивов; N - это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно CN = N lg N.
· Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.Худший случай даёт O (n?) обменов, но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов.
Данное програмное обеспечение имеет интуитивно понятный интерфейс и использует все возможности среды Delphi.
Программа имеет пять вкладок. При первоначальном запуске активируется первая - вкладка «Квартиры» (см. рис. 3).
Рис. 3 - Вкладка таблицы квартир
На каждой вкладке с элементами таблицы можно выполнить операции добавления новой строки, удаление существующей, изменение значения ячеек, а также сортировки текущего столбца и поиска заданного значения в текущем столбце. Сортировка выполняется методом быстрой сортировки QuickSort. При выполнении сортировки вначале выполняется сортировка по возрастанию, при следующем нажатии кнопки «Сортировка» выполняется сортировка по убыванию и т.д.
На вкладке «Квартиры» можно изменить только колонки: «Номер квартиры», «Стоимость квартиры», «Признак приват.». Остальные колонки рассчитываются по таблицам «Атрибуты квартир (С)» и «СХЕМА» следующим образом:
Три первых колонки определяются исходя из данных таблицы «СХЕМА». Колонка «Жилая площадь» = сумма площадей всех комнат, взятых из таблицы С.
Колонка «Общая площадь» =атр. 4 + атрибуты 7-9 из таблицы С.
Одновременно после ввода / изменения номера квартиры выдается информационное сообщение (см. рис. 4)
Рис. 4 - Информационное сообщение
Страницы: 1, 2, 3
