Показать сообщение отдельно
Старый 28.02.2007, 17:38   #62
 
Аватар для Overlord
 
Статус: Старейшина
Регистрация: 27.03.2005
Адрес: Великая и могучая
Сообщений: 732
СПАСИБО: 49
сказали Спасибо 293 раз(а) в 169 сообщении
Получено наград:
По умолчанию Re: Решебник (turbo pascal, Delphi)

Цитата:
Сообщение от Kain Посмотреть сообщение
ООО а вот и трудные задачи!! помогеш оверлорд??

Разработать процедуры сортировки массива целых чисел методом прямого выбора, методом пузырьковой сортировки и методом шейкерной сортировки (язык программирования Паскаль или Си).


Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве.


Во время сортировки предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.


Составить таблицу следующего вида (данные получить экспериментально) для н= 100, 200, 300, 400, 500. (н – количество элементов в массиве)
Код:
-------------------------------------------------------------------
метод  |  М для             | Ц для            | М для        | Ц для         |
          |  упорядочного  |  упорядочного| случайного| случайного  |
          | массива           | массива        | массива     | массива     |
--------------------------------------------------------------------
прямой |                       |                     |                 |                 |
выбор   |                       |                     |                 |                 |
--------------------------------------------------------------------
Пузырьковая|                  |                    |                  |                |
--------------------------------------------------------------------
Шейкерная|                    |                    |                  |               |
--------------------------------------------------------------------
Проанализировать полученные результаты. (Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности?)

Добавлено через 1 минуту
вот блин сайт неподерживает пробелы таблица корявая получилась ну в принципе по знаку | можно понять

вот для затравки начало напишу. чуть чуть доделать остается

все делать будем через процедуры и функции. и еще нам потребуется свой тип данных (чтобы правильно функцию оформить). Общий смыл такой заполняем произвольно массив потом дважды вызываем метод сортировки. При этом сначала сортируется безпорядочный массив, а вторым проходом соответсвенно упорядочный. Повторям для каждого метода сортировки. Пока сделал для двух методов сортировки.
Код:
program OverLord;
uses crt;

const
  X = 10;
  Y = 10;

type TMC = record
  M:integer;
  C:integer;
end;

var
  A:array [1..X] of integer;
  i,j,k:integer;
  Count:TMC;

procedure FillRandom;
begin
  randomize;
  for i:=1 to X do
    A[i]:=random(1000) - 500;
end;

procedure PrintArray;
begin
  for i:=1 to X do
  begin
    write(A[i]);
    if i<>X then write(', ') else write('.');
  end;
  writeln;
end;

Function SortLineSelect:TMC;
var
i, j, min, t : integer;
begin
  SortLineSelect.M:=0;
  SortLineSelect.C:=0;
  for i:=1 to X-1 do
    begin
      min := i;
      for j:=i+1 to X do
        begin
          if A[j]<A[min] then min := j;
          inc(SortLineSelect.M);
        end;
      {вот этого условия в теории не было
      и алгоритм переставлял местами элемент сам с собой
      перестановок насчитывалось столько же сколько и при сортировке
      упорядоченного массива.
      Я точно не знаю является ли такая добавка усовершенствованием
      массива или нет, так что если что просто убери это условие}
      if min<>i then
        begin
        { раз перестановка}
        t := A[min];
        inc(SortLineSelect.C);
        {два перестановка}
        A[min] :=A[i];
        inc(SortLineSelect.C);
        {три перестановка}
        A[i] := t;
        inc(SortLineSelect.C);
      end;
    end;
end;

function SortBubble:TMC;
var i, j, t : integer;
begin
  SortBubble.M:=0;
  SortBubble.C:=0;
  for i:=2 to X do
  for j:=X downto i do
    begin
    inc(SortBubble.M);
    if A[i-1]>A[j] then
       begin
         t:=A[j-1];
         inc(SortBubble.C);
         A[j-1]:=A[j];
         inc(SortBubble.C);
         A[j]:=t;
         inc(SortBubble.C);
       end;
    end;
end;


BEGIN
  clrscr;
  for k:= 1 to 2 do
  begin
    {произвольно заполняем массив}
    FillRandom;
    {печатаем массив на экране}
    write('Первыоначальный массив: ');
    PrintArray;
    {сортируем и считаем сравнения с перестановками}
    case k of
      1:Count:=SortLineSelect;
      2:Count:=SortBubble;
    end;
    write('при сортировке не упорядоченного массива имеем: ');
    writeln(Count.M,', сравнений и ', Count.C, ' перестановок');
    {сортируем только что отсортированный массив}
    case k of
      1:Count:=SortLineSelect;
      2:Count:=SortBubble;
    end;
    write('при сортировке упорядоченного массива имеем: ');
    writeln(Count.M,', сравнений и ', Count.C, ' перестановок');
    write('А так после сортировки: ');
    PrintArray;
    writeln('****************************');
  end;


  write('Нажмите Enter для выхода ...');
  readln;
END.


[Ссылки могут видеть только зарегистрированные пользователи. ]
Overlord вне форума   ЦИТИРОВАТЬ
Этот пользователь сказал Спасибо Overlord за это полезное сообщение: