Разработать программу для сортировки элементов динамического массива, используя сортировку обменами, сортировку выбором, сортировку включением и быструю сортировку.
Реализовать в одной программе возможность обработки массивов, содержащих данные следующих типов:
Подпрограммы сортировки реализовать в отдельном модуле.
Ввод осуществляется из файла, вывод – в файл. Имена файлов передаются через параметры программы.
Определить как меняется время сортировки массива в зависимости от следующих параметров:
Замеры времени необходимо проводить на данных большого объёма (от 1000 элементов массива).
Для того, чтобы легко можно было изменить тип данных для массивов, надо в программе ввести собственный тип, который будет принимать необходимое значение.
type
TElem = integer;
| Класс | Имя | Смысл | Тип | Структура |
|---|---|---|---|---|
| Входные данные | x | Исходный массив | TElem | одномерный массив |
| n | Количество элементов массива | цел. | простая переменная | |
| Выходные данные | x | Тот же массив после сортировки | TElem | одномерный массив |
| Класс | Имя | Смысл | Тип | Структура |
|---|---|---|---|---|
| Входные данные | x | Исходный массив | TElem | одномерный массив |
| n1, n2 | Начальный и конечный индекс обрабатываемой части | цел. | простая переменная | |
| Выходные данные | x | Тот же массив после сортировки | TElem | одномерный массив |
| № теста | Входные данные | Ожидаемые результаты | Смысл теста |
|---|---|---|---|
| 1 |
тип – целый n = 5 a = {0, 2, 5, 9, 19} |
a = {0, 2, 5, 9, 19} | Числа расположены в правильном порядке. |
| 2 |
тип – целый n = 6 a = {55, 48, 42, 31, 24, 13} |
a = {13, 24, 31, 42, 48, 55} | Числа расположены в обратном порядке. |
| 3 |
тип – строка n = 10 a = {‘write’, ‘sort’, ‘read’, ‘program’, ‘knight’, ‘dog’, ‘close’, ‘cat’, ‘back’, ‘any’} |
a = {‘any’, ‘back’, ‘cat’, ‘close’, ‘dog’, ‘knight’, ‘program’, ‘read’, ‘sort’, ‘write’} | Строки расположены в обратном порядке. |
| 4 |
тип – целый n = 6 a = {3, 5, 56, 12, 1, 44} |
a = {1, 3, 5, 12, 44, 56} | Числа расположены в случайном порядке. |
| 5 |
тип – строка n = 6 a = {‘3’, ‘5’, ‘56’, ‘12’, ‘1’, ‘44’} |
a = {‘1’, ‘12’, ‘3’, ‘44’, ‘5’, ‘56’} | Строки расположены в случайном порядке. |
| 6 |
тип – целый n = 9 a = {8, 23, 5, 65, 44, 10, 1, 12, 55} |
a = {1, 5, 8, 10, 12, 23, 4,4, 55, 65} | Числа расположены в случайном порядке. |
| 7 |
тип – строка n = 9 a = {‘8’, ‘23’, ‘5’, ‘65’, ‘44’, ‘10’, ‘1’, ‘12’, ‘55’} |
a = {‘1’, ‘10’, ‘12’, ‘23’, ‘44’, ‘5’, ‘55’, ‘65’, ‘8’} | Строки расположены в случайном порядке. |
Для того чтобы хорошо протестировать программу сортировки, а также выявить зависимость времени от различных параметров, необходимо тестировать программу на исходных данных больших объемов. Вы можете загрузить файлы с исходными данными, содержащими 1000 чисел в прямом порядке, 5000 чисел в прямом порядке, 10000 чисел в прямом порядке, 20000 чисел в прямом порядке, 1000 чисел в обратном порядке, 5000 чисел в обратном порядке, 10000 чисел в обратном порядке, 20000 чисел в обратном порядке, 1000 чисел в случайном порядке, 5000 чисел в случайном порядке, 10000 чисел в случайном порядке, 20000 чисел в случайном порядке. В файлах записаны числа, но их можно использовать и как строки.
Данные по времени в зависимости от различных параметров удобно представить в виде таблицы. Но, поскольку параметров достаточно много, отобразить все зависимости сразу трудно. Можно отдельно вынести зависимость времени от объёма исходных данных, рассматривая при этом худший случай – когда данные расположены в обратном порядке и используя целый тип. Поэтому для выявления зависимостей заполним две таблицы.
| Метод | Объём данных | |||
|---|---|---|---|---|
| 1000 | 5000 | 10000 | 20000 | |
| Сортировка обменами | ||||
| Сортировка выбором | ||||
| Сортировка включением | ||||
| Быстрая сортировка | ||||
| Упорядоченность | Метод | Тип данных | |
|---|---|---|---|
| integer | string | ||
| Данные расположены в требуемом порядке |
Сортировка обменами | ||
| Сортировка выбором | |||
| Сортировка включением | |||
| Быстрая сортировка | |||
| Данные расположены в обратном порядке |
Сортировка обменами | ||
| Сортировка выбором | |||
| Сортировка включением | |||
| Быстрая сортировка | |||
| Данные расположены в случайном порядке |
Сортировка обменами | ||
| Сортировка выбором | |||
| Сортировка включением | |||
| Быстрая сортировка | |||
Желательно сделать несколько замеров времени и записать среднее значение.
Методы сортировки были рассмотрены на лекции. Поскольку при сортировке новый массив не создаётся, для того, чтобы отсортировать один и тот массив несколькими способами, необходимо предварительно скопировать неотсортированные данные в другой массив. Для копирования динамического массива используется функция Copy.
Алгоритмы сортировки совпадают для всех типов данных, а процедуру ввода для типа Variant придётся немного модифицировать.
uses
Variants;
type
TElem = Variant;
procedure Get(var x: array of TElem; var n: integer; var f: TextFile);
var
t: char;
vt: integer;
s: string;
i: integer;
begin
repeat
writeln('Задайте тип - i для integer, s для string');
readln(t);
until (t = 'i') or (t = 's');
if t = 'i' then
vt := varInteger
else if t = 's' then
vt := varString;
readln(f, n);
SetLength(x, n);
for i := 0 to n - 1 do
begin
readln(f, s);
x[i] := VarAsType(s, vt);
end;
end;
При сортировке необходимо измерить время, затрачиваемое на сортировку каждым алгоритмом. В Embarcadero RAD Studio для хранения времени используется тип TDateTime. Функция Time позволяет определить текущее время. Для определения разницы во времени между двумя моментами можно просто вычесть значение одной переменной типа TDateTime из другой переменной того же типа. Для преобразования времени в строку используется функция FormatDateTime.
var
start, finish: TDateTime;
begin
start := Time();
... // Некоторые действия
finish := Time();
writeln(FormatDateTime('h.nn.ss:zzz', finish - start));
end;
В PascalABC для хранения времени используется переменная типа System.DateTime. Функция Now позволяет определить текущее время. Для определения разницы во времения также нужно вычесть одну переменную из другой, результатом будет значение типа System.TimeSpan. Затем можно использовать функции Minutes, Seconds и Milliseconds для получения времени.
var
start, finish: System.DateTime;
ts: System.TimeSpan;
begin
start := System.DateTime.Now;
... // Некоторые действия
finish := System.DateTime.Now;
ts := finish - start;
writeln(Format('{0:d2}:{1:d2}.{2:d3}', ts.Minutes, ts.Seconds, ts.Milliseconds));
end;