Реферат Исследование алгоритмов сортировки в среде OC LINUX
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
МИНИСТЕРСТВО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ
«МАТИ» – РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ
ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К. Э. ЦИОЛКОВСКОГО
___________________________________________________________________
Кафедра «Моделирование систем и информационные технологии»
ОТЧЕТ ПО КУРСОВОЙ РАБОТЕ
"ИССЛЕДОВАНИЕ АЛГОРИТМОВ СОРТИРОВКИ В СРЕДЕ OC LINUX"
Преподаватель: Лидовский В.В.
Студент:
Группа: АСУ-2ДС-025
Вариант: 11
2010г.
1. Цель лабораторной работы :
Изучить временные характеристики алгоритмов сортировки данных различного объема, приобрести навыки работы в среде OC Linux.
2. Краткая характеристика исследуемых алгоритмов
2.1.Метод Шелла.
Этот метод является модификацией метода пузырька. Основная его идея заключается в том, чтобы вначале устранить массовый беспорядок в сортируемой последовательности, сравнивая далеко отстоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшают до единицы, т.е. на первом проходе гарантируется, что все элементы, расстояние между которыми L1 < N – 1, упорядочиваются друг относительно друга, на втором то же гарантируется для элементов, расстояние между которыми L2 < L1 и т.д. до последнего k-го прохода, когда должно выполняться Lk = 1. Обычно расстояния L для сортировки Шелла берутся из приблизительного соотношения Lk ≤ 2Lk-1 и L1 ≤ N/2, но лучше для расстояний L брать простые числа, ближайшие к Lk, выбираемым по описанной выше схеме.
2.2.Сортировка массивом (хэширование).
Сортировка массивом – это самый быстрый метод сортировки, не лишенный, однако, множества существенных недостатков. Суть метода заключается в заполнении вспомогательного массива, содержащего элементов несколько больше, чем исходная последовательность. Заполнение этого вспомогательного массива происходит так: вычисляются значения некоторой монотонной функции, называемой хэш-функция, на элементах сортируемой последовательности и эти значения считаются индексами этих элементов в заполняемом массиве. Если же окажется, что подлежащий заполнению элемент вспомогательного массива уже занят, то происходит сдвиг соответствующих элементов этого массива так, чтобы образовалось «окно» для вносимого элемента и сохранялась упорядоченность между элементами. Функция должна выбираться так, чтобы её значения лежали внутри диапазона индексов вспомогательного массива. Например, если известно, что сортируемая последовательность состоит из натуральных чисел от 1 до N, то в качестве искомой функции можно взять
где A – это исходная последовательность (массив), Max(A) и Min(A) – максимальный и минимальный элементы А, B – это вспомогательный массив, а Size(B) – это его размер. Эта монотонная (почти линейная) функция гарантирует, что её значения на элементах сортируемого массива будут лежать в диапазоне от 1 до Size(B). Она определена только при Max(A) ≠ Min(A). Если же Max(A) = Min(A), то это означает, что массив состоит из одинаковых элементов, т.е. он отсортирован.
3. Листинг исследовательской программы
type
mass=array[1..16000] of longint;
const
maxnumber=70000;
var
i,m,k:byte;
d,s:longint;
t1,t2:array[1..4,1..7]of longint;
basearray,basearraycopy:mass;
procedure exchange(a:longint;b:longint;var basearray:mass);
var k:longint;
begin
k:=basearray[b];
basearray[b]:=basearray[a];
basearray[a]:=k;
end;
procedure fillarray(size:longint;t:byte;var base:mass);
var i:word;
begin
randomize;
case t of
1:begin
base[1]:=maxnumber;
for i:=2 to size do
base[i]:=base[i-1]-random(maxnumber div size)-1
end;
2:begin
base[1]:=1;
for i:=2 to size do
base[i]:=base[i-1]+random(maxnumber div size)+1
end;
3:for i:=1 to size do
base[i]:=random(12)+1;
4:for i:=1 to size do
base[i]:=random(maxnumber)+1;
end;
end;
procedure shellsort(size:longint;var basearray:mass);
var
i,j,gap:longint;
begin
gap:=size div 2;
while gap>0 do begin
for i:=gap to size-1 do begin
j:=i-gap+1;
while basearray[j]<basearray[j+gap] do begin
exchange(j,j+gap,basearray);
if j>gap then j:=j-gap else break;
end;
end;
gap:=gap div 2;
end;
end;
procedure arraysort(size:longint;var basearray:mass);
const
factor:real=1.4;
var
i,j,l,p,minelem,maxelem,ubound:longint;
k,m:longint;
auxarray:array[1..22400] of longint;
begin
minelem:=basearray[1];
maxelem:=basearray[1];
for i:=2 to size do begin
if maxelem<basearray[i] then
maxelem:=basearray[i];
if minelem>basearray[i] then
minelem:=basearray[i];
end;
if maxelem=minelem then exit;
ubound:=round(size*factor);
for i:=1 to ubound do
auxarray[i]:=0;
for i:=1 to size do begin
j:=(basearray[i]-minelem)*(ubound-1) div (maxelem-minelem)+1;
if auxarray[j]=0 then
auxarray[j]:=basearray[i]
else begin
if auxarray[j]>basearray[i] then begin
while j>1 do
if auxarray[j-1]>basearray[i] then
dec(j)
else
break;
m:=-1;
end else begin
while j<ubound do
if (auxarray[j+1]<basearray[i])
and (auxarray[j+1]<>0) then
inc(j)
else
break;
m:=1;
end;
k:=0;
repeat
if (k+j>0) and (k+j<=ubound) then
if auxarray[k+j]=0 then
break;
if k>0 then k:=-k else k:=1-k;
until false;
l:=j+k;
if k>0 then k:=1 else k:=-1;
j:=j+(m+k) div 2;
while l<>j do begin
auxarray[l]:=auxarray[l-k];
l:=l-k;
end;
auxarray[j]:=basearray[i];
end;
end;
j:=1;
for i:=ubound downto 1 do
if auxarray[i]<>0 then begin
basearray[j]:=auxarray[i];
inc(j);
end;
end;
procedure check_error(size:longint;basearray:mass);
var
i:longint;
begin
for i:=1 to size do
if basearray[i]<basearray[i+1] then begin
writeln('Error!');
halt;
end;
end;
{$L timer.o}
procedure init_timer; cdecl; external;
function get_timer:longint; cdecl; external;
{$LinkLib c}
begin
s:=250;
writeln('Shellsort/Arraysort');
for i:=1 to 7 do begin
write(s:5,’: |’);
for k:=1 to 4 do begin
fillarray(s,k,basearray);
basearraycopy:=basearray;
init_timer;
shellsort(s,basearray);
t1[k,i]:=get_timer;
check_error(s,basearray);
basearray:=basearraycopy;
init_timer;
arraysort(s,basearray);
t2[k,i]:=get_timer;
check_error(s,basearray);
write(t1[k,i]:5,'/',t2[k,i]:6,' |');
end;
s:=s*2;
writeln;
end;
end.
4. Описание исследовательской программы
Процедуры и функции:
exchange
(
a
:
longint
;
b
:
longint
;
var
basearray
:
mass
) – процедура меняющая местами элементы с индексами a и b, в массиве basearray.
fillarray
(
size
:
longint
;
t
:
byte
;
var
base
:
mass
)
- подготовка исходных данных : заполнение первых size элементов массива base одним из четырех способов, в зависимости от значения t: “Упорядоченные” - элемент массива с меньшим индексом строго больше элемента с большим индексом(t=1); “Обратного порядка” - элемент массива с меньшим индексом строго меньше элемента с большим индексом(t=2); “Вырожденные” - массив заполняется случайным образом числами из диапазона от 1 до 12(t=3); “Случайные” - массив заполняется случайным образом числами из диапазона от 1 до 70000(t=4).size – параметр типа longint, задает количество заполняемых первых элементов массива (250, 500, 1000, 2000, 4000, 8000 или 16000 элементов);
shellsort
(
size
:
longint
;
var
basearray
:
mass
)
– процедура, сортирует первых size элементов массива basearray по убыванию методом Шелла.
arraysort(size:longint;var basearray:mass) – процедура, обеспечивает сортировку массивом первых size элементов массива basearray по убыванию.
check
_
error
(
size
:
longint
;
basearray
:
mass
)
- процедура для проверки правильности сортировки первых size элементов массива basearray, если он отсортирован правильно, то продолжается выполнение программы, если нет, то выдается сообщение об ошибке и выполнение программы прекращается.
init
_
timer – процедура, инициализирует (обнуляет) таймер (счетчик времени).
get
_
timer – функция, возвращает количество микросекунд, прошедших с момента последнего обнуления таймера.
Директивы:
cdecl – директива, применяется для обращения к статическим библиотекам, использующим соглашения языка C.
external – директива, указывает на неявный вызов подпрограммы.
{$
L
timer
.
o
} – директива, подключает подпрограммы из модуля timer.o.
{$
LinkLib
c
} – директива, подключает стандарты языка C.
Глобальные переменные:
i ,
k
–временные переменная типа byte.
s – вспомогательная переменная типа longint, необходимая для хранения размера массива.
t
1,
t
2 – двумерные массивы из 28 элементов типа longint, необходимые для хранения значений времени сортировки для сортировки методом пузырька и сортировки выбором деревом соответственно.
Массивы:
b
asearray - массив из 16000 элементов типа LongInt.
b
ase
a
rray
copy
– копия сортируемого массива.
Auxarray
– вспомогательный массив, состоящий из 16000*factor элементов типа LongInt, factor = 1.4
Константы:
maxnumber
– вспомогательная константа, равная 70000
factor
– константа, равная 1.4 = размер(auxarray)/размер(basearray)
Таблица и график результатов исследования
Таблица
Результатов исследования зависимости времени (в мс) сортировки массива от его размеров и способа заполнения.
Алгоритм | Сортировка методом Шелла / Сортировка массивом | |||
типРазмер | Упорядоченные | Обратный порядок | Вырожденные | Случайные |
| 250 | 0.016/0.042 | 0.040/0.035 | 0.043/0.074 | 0.064/0.039 |
| 500 | 0.033/0.067 | 0.109/0.067 | 0.086/0.202 | 0.148/0.074 |
| 1000 | 0.074/0.139 | 0.323/0.132 | 0.305/0.620 | 0.393/0.146 |
| 2000 | 0.165/0.262 | 0.552/0.262 | 0.448/2.132 | 0.895/0.309 |
| 4000 | 0.364/0.526 | 1.224/0.513 | 0.975/8.135 | 2.079/0.598 |
| 8000 | 0.802/1.015 | 2.716/1.010 | 2.244/29.419 | 4.607/1.207 |
| 16000 | 1.759/1.914 | 4.327/2.005 | 5.111/119.213 | 10.991/2.416 |
| N | ~N / N | ~N / N | ~N / N2 | ~N / N |
График
Зависимости времени сортировки от размера сортируемой последовательности, заполненной случайным образом.
Задание размера массива и типа
его заполнения
Заполнение массива
Сохранение копии массива
Обнуление таймера
Сортировка методом Шелла
Получение времени сортировки
Проверка,
массив?
Восстановление исходного
массива из копии
Обнуление таймера
Сортировка массивом
Получение времени сортировки
Проверка, Нет
Да есть ли неисследованные
типа его заполнения?
6. Анализ результатов эксперимента
В результате исследования я установил, что метод Шелла является более эффективным по сравнению с сортировкой массивом при сортировке упорядоченных и вырожденных данных, причем преимущество в скорости в случае с вырожденными данными возрастает с увеличением количества сортируемых элементов, что объясняется многочисленными перестановками при сортировке часто повторяющихся данных в алгоритме сортировки массивом. Метод Шелла приблизительно одинаково эффективен при упорядочивании данных любого типа и время сортировки пропорционально количеству элементов в массиве. А вот со случайными данными и данными обратного порядка очень быстро справляется сортировка массивом, опережая сортировку методом Шелла.
7. Выводы
Проанализировав результаты эксперимента, я сделал вывод, что метод Шелла является более простым и хорошо справляется с упорядоченными и вырожденными данными, причем в случае с вырожденными данными, чем больше количество сортируемых элементов, тем эффективнее этот метод по сравнению с сортировкой массивом. Результаты сортировки вырожденных данных отчетливо показывают крайнюю неэффективность алгоритма сортировки массивом. С набором повторяющихся данных он справляется значительно медленнее, чем метод Шелла. Но зато сортировка массивом замечательно справляется с упорядочиванием случайных данных, а ведь в основном числа, с которыми приходится иметь дело в реальной жизни расположены случайным образом, поэтому на практике чаще используется именно этот метод. Но наряду с этим метод сортировки массивом является более сложным методом относительно сортировки методом Шелла, требует больше памяти и не всегда будет наилучшим выбором.
