VPF::Алгоритм Шелла - Форум программистов

Sancho

Дата 15.9.2006, 21:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 15.9.2006

Репутация: нет
Всего: нет

Здраствуйте, помогите пожалуйста с графическим предтавлением работы алгоритма Шелла.
Вот алгоритм Шелла:
begin
g:=trunc((n+1)/2);
repeat
i:=i-g;
c:=True;
repeat
if a[j]<=a[j+g]
then
  begin
  c:=False;
  end
  else
  begin
  t:=a[j];
  a[j]:=a[j+g];
  a[j+g]:=t;
  end;
  j:=j-1
until not((j>=0)and©);
i:=i+1
until not (i<=n);
g:=trunc(g/2);
until not(g>0);
end;
Как модернизировать его чтобы выводился график с 33 опытами сортировки.Где ось Y:время, X:количество элементов. И вывод сред. арифм. времени. Буду очень признателен, т.к. pascal изучаю недавно, но вот с графиками и временем выполнения алгоритма ещё не сталкивался.

volvo877

Дата 16.9.2006, 13:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Sancho, ну, вот так например:

Код

uses dos, graph;

function GetTime: LongInt;
Var h, m, s, ms: Word;
begin
  Dos.GetTime(h, m, s, ms);
  GetTime := longint(ms) + 100 * (s + 60 * (m + 60 * h));
end;

procedure ShellSort(var Arr : array of Real; N : Integer);
var
  C:   Boolean;
  Tmp: Real;

  E, G: Integer;
  I, J: Integer;
begin
  N:=N-1;
  g:=((n+1) div 2);
  repeat

    i:=g;
    repeat

      j:=i-g;
      c:=True;
      repeat

        if Arr[j]<=Arr[j+g] then c:=False
        else begin
          Tmp:=Arr[j];
          Arr[j]:=Arr[j+g];
          Arr[j+g]:=Tmp;
        end;
        dec(j)

      until not((j>=0)and(C));
      inc(i)

    until not(i<=n);
    g:=g div 2;

  until not(g>0);
end;

procedure PrintArray(var Arr: array of real; const n: integer);
var i: integer;
begin
  for i := 0 to pred(n) do
    write(arr[i]:7:2);
  writeln;
end;


const
  size = 10 * 640;
  nEvents = 33;
  kvant = size div nEvents;

var
  sizeEvent, Times: array[1 .. nEvents] of word;

  buf: array[0 .. size - 1] of real;
  i, Event: integer;
  Average: LongInt;
  tm, tm1: longint;

var
  grDriver: Integer;
  grMode: Integer;
  ErrCode: Integer;
  X, Y: integer;
  s: string;
const
  DY = 40;

begin
  randomize;
  for i := 1 to nEvents do
    sizeEvent[i] := i * kvant;

  Average := 0;
  for Event := 1 to nEvents do begin

    for i := 0 to pred(sizeEvent[Event]) do
      buf[i] := (random(10000) + 100) / 100;
      { PrintArray(buf, sizeEvent[Event]); }

      tm1 := GetTime;
      ShellSort(buf, sizeEvent[Event]);
      tm := GetTime;
      Times[Event] := (tm - tm1);
      Average := Average + Times[Event];
      writeln('Event = ', Event, '; time = ', Times[Event],
              ' size = ', sizeEvent[Event]);

      { PrintArray(buf, sizeEvent[Event]); }

  end;
  writeln('average time = ', average div nEvents);
  writeln('press Enter to view the diagram...'); readln;

  grDriver := Detect;
  InitGraph(grDriver, grMode, '');
  ErrCode := GraphResult;
  if ErrCode = grOk then begin
    rectangle(0, 0, getmaxx, getmaxy - DY);
    moveto(0, getmaxy - DY); setcolor(red);
    settextjustify(centertext, centertext);
    settextstyle(defaultfont, vertdir, 0);
    for event := 1 to nEvents do begin
      lineto(sizeevent[event] div 10, (getmaxy - DY) - 5 * times[event]);
      X := getx; Y := gety;
      str(sizeevent[event], s);
      outtextxy(sizeevent[event] div 10, getmaxy - (DY div 2), s);
      moveto(X, Y);
    end;

    Readln;
    CloseGraph;
  end
  else
    Writeln('Graphics error:', GraphErrorMsg(ErrCode));

end.

(правда, по оси OY я не стал выводить шкалу. Нужно - добавь сам, по аналогии с тем, как я сделал)...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »