МИНИСТЕРСТВО  ОБРАЗОВАНИЯ

РОССИЙСКОЙ  ФЕДЕРАЦИИ

«МАТИ»  – РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ

ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К. Э. ЦИОЛКОВСКОГО

___________________________________________________________________ 
 
 
 
 
 

Кафедра «Моделирование систем и информационные технологии» 
 
 

ОТЧЕТ   ПО   КУРСОВОЙ   РАБОТЕ

"ИССЛЕДОВАНИЕ  АЛГОРИТМОВ СОРТИРОВКИ В СРЕДЕ  OC LINUX" 
 
 
 
 
 
 
 
 

                      Преподаватель:  Лидовский В.В.

                      Студент:             

                       Группа:                АСУ-2ДС-025

                      Вариант:                        11 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2010г.

1.   Цель лабораторной  работы :

 

      Изучить временные характеристики алгоритмов сортировки данных различного объема, приобрести навыки работы в среде  OC Linux.

2. Краткая характеристика исследуемых алгоритмов

 

     2.1.Метод Шелла.

      Этот  метод является модификацией метода пузырька. Основная его идея заключается  в том, чтобы вначале устранить  массовый беспорядок в сортируемой  последовательности, сравнивая далеко отстоящие друг от друга элементы. Интервал между сравниваемыми элементами постепенно уменьшают до единицы, т.е. на первом проходе гарантируется, что все элементы, расстояние между которыми L₁ < N – 1, упорядочиваются друг относительно друга, на втором то же гарантируется для элементов, расстояние между которыми L₂ < L₁ и т.д. до последнего k-го прохода, когда должно выполняться L_k = 1. Обычно расстояния L для сортировки Шелла берутся из приблизительного соотношения L_k ≤ 2L_k-1 и L₁ ≤ N/2, но лучше для расстояний L брать простые числа, ближайшие к L_k, выбираемым по описанной выше схеме.

 

      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, необходимая для хранения размера массива.

t1,t2 – двумерные массивы из 28 элементов типа longint, необходимые для хранения значений времени сортировки для сортировки методом пузырька и сортировки выбором деревом соответственно.

 
 

Массивы:

basearray - массив из 16000 элементов типа LongInt.