// 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;

begin

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

begin

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).

Рис. 3 – Вкладка таблицы квартир

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

На вкладке «Квартиры» можно изменить только колонки: «Номер квартиры», «Стоимость квартиры», «Признак приват.». Остальные колонки рассчитываются по таблицам «Атрибуты квартир (С)» и «СХЕМА» следующим образом:

Три первых колонки определяются исходя из данных таблицы «СХЕМА». Колонка «Жилая площадь» = сумма площадей всех комнат, взятых из таблицы С.

Колонка «Общая площадь» =атр. 4 + атрибуты 7–9 из таблицы С.

Одновременно после ввода / изменения номера квартиры выдается информационное сообщение (см. рис. 4)

Рис. 4 – Информационное сообщение

В случае попытки редактирования колонок №№2–5 выдается следующее сообщение (см. рис. 5).

Рис. 5 – Сообщение о невозможности редактирования ячейки

При переходе на вкладку «СХЕМА» отображается следующее окно (см. рис. 6)

Рис. 6 – Вкладка схемы квартир «СХЕМА»

Здесь также можно редактировать значения, удалять их и добавлять новые, сортировать и искать определенные значения.

Третья вкладка «ГК (Р)» содержит атрибуты таблицы главных квартиросъемщиков квартир (см. рис. 7).

Рис. 7 – Вкладка таблицы главных квартиросъемщиков ГК(Р)

В данной вкладке как и в прдедыдущих можно радактировать атрибуты, удалять их, добавлять новые, сортировать и искать определенные значения.

В четвертой вкладке находится таблица жителей квартир – членов семей главных квартиросъемщиков (А). (см. рис. 8)

Рис. 8 – Вкладка таблицы жителей квартир – членов семей главных квартиросъемщиков (А)

На пятой вкладке находится таблица (С) с атрибутами квартир (С). (см. рис. 9)

Рис. 9 – Вкладка таблицы (С) с атрибутами квартир

Из всех вкладок доступны кнопки «Сохранить в файл» и «Загрузить из файла» с помощью которых можно сохранить данные всех вкладок в текстовый файл *.dat и загрузить данные из файла.

Для формирования отчета формы Ф5 необходимо нажать на кнопку «Отчет Ф5», при этом открывается новое окно с отчетными данными (см. рис. 10). Закрыть окно можно нажав на кнопку «ОК».

Рис. 9 – Вкладка таблицы (С) с атрибутами квартир

Заключение

В процессе разработки данного курсового проекта были изучены и закреплены знания по физическим размещениям структур данных и методам их обработки (сортировки). В среде Delphi была разработана информационная система начальника жилищно-эксплуатационной службы. При создании программы не использовались компоненты баз данных данной среды Delphi.

Тестирование данного продукта показало полноту реализованных функций и отсутствие ошибок и недочётов в программе. Были изучены базовая структура данных типа вектор и метод быстрой сортировки QuickSort.

Литература

Приложение 1

Листинги программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

StdCtrls, ExtCtrls, math, Grids, Buttons, Mask, Calendar, ComCtrls,

Spin, MyTypes, Unit2;

Type

TInputForm = class(TForm)

BitBtn1: TBitBtn;

OpenDialog1: TOpenDialog;

SaveDialog1: TSaveDialog;

LoadButton: TButton;

SaveButton: TButton;

PageControl1: TPageControl;

TabSheet1: TTabSheet;

TabSheet2: TTabSheet;

TabSheet3: TTabSheet;

StringGrid1: TStringGrid;

DelBtn: TBitBtn;

AddBtn: TBitBtn;

StringGrid2: TStringGrid;

SortBtn: TBitBtn;

TabSheet4: TTabSheet;

TabSheet5: TTabSheet;

StringGrid3: TStringGrid;

StringGrid4: TStringGrid;

StringGrid5: TStringGrid;

Label1: TLabel;

KSpinEdit: TSpinEdit;

Label2: TLabel;

MSpinEdit: TSpinEdit;

FindBtn: TBitBtn;

CopyBtn: TBitBtn;

FButton: TButton;

procedure FormCreate (Sender: TObject);

procedure LoadButtonClick (Sender: TObject);

procedure SaveButtonClick (Sender: TObject);

procedure PageControl1Change (Sender: TObject);

procedure AddBtnClick (Sender: TObject);

procedure SGDblClick (Sender: TObject);

procedure DelBtnClick (Sender: TObject);

procedure SortBtnClick (Sender: TObject);

procedure KSpinEditChange (Sender: TObject);

procedure MSpinEditChange (Sender: TObject);

procedure SGKeyPress (Sender: TObject; var Key: Char);

procedure FormDestroy (Sender: TObject);

procedure CopyBtnClick (Sender: TObject);

procedure FindBtnClick (Sender: TObject);

procedure FButtonClick (Sender: TObject);

private

{Private declarations}

public

{Public declarations}

 //Fz: file of TVector; // Файл типа запись

KPod, M: integer; // Количество подъездов и этажей

People: TVector; // Вектор – члены семей ГК

GK: TVector; // Вектор – главные квартиросъемщики

Scheme: TVector; // Вектор – СХЕМА

FlatAtr: TVector; // Вектор – Атрибуты квартир

KVART: TVector; // Вектор – КВАРТ

Ft: TextFile; // Текстовой файл

FileNameT: string[200]; // Имя файла

FSGVector: array [1..10] of TStringGrid;

procedure FillStringGrid (SG: TStringGrid; Vec: TVector);

function GetVec: TVector;

procedure ReadVec (var Vec: TVector);

procedure WriteVec (Vec: TVector); // Запись вектора в файл

end;

var

InputForm: TInputForm;

Implementation

{$R *.DFM}

procedure TInputForm. FormCreate (Sender: TObject);

begin

KPod:=2; M:= 3;

 // –

Kvart:= TVector. Create;

Kvart. Cols:= 7;

Kvart. Names[1]:= 'Номер квартиры';

Kvart. Names[2]:= 'число комнат';

Kvart. Names[3]:= 'номер этажа';

Kvart. Names[4]:= 'жилая площадь (кв. м.)';

Kvart. Names[5]:= 'общая площадь (кв. м.)';