Метод Шелла с шагом Хиббарда, для матрицы Опции

[Renbo]

вот собственно программа которая сортирует строки матрицы методом шелла с шагом N/2:

TYPE mas = array [1..100,1..100] of integer;
VAR
  I,N, M, J : Integer;
  a:mas;

  Procedure Sort( var a : mas; N, M:Integer);
Var
  d, i, t : integer;
  k : boolean;
begin
  d:=N div 2;
  while d>0 do
    begin
      k:=true;
      while k do
        begin
          k:=false;
          for I:=1 to M do
          for J:=1 to N-d do
            begin
              if a[I,J] > a[I,J+d] then
                begin
                  t:=a[I,J]; a[I,J]:=a[I,J+d]; a[I,J+d]:=t;
                  k:=true;
                end;
            end;
        end;
      d:=d div 2;
    end;
end;

Begin
  write ('введите количество строк ');
  read (M);
  write ('введите количество столбцов ');
  read (N);
  For I:=1 to M do
    For J:=1 to N do
      begin
        write ('введите a[',I,',',J,']= ');
        read (a[I,J]);
      end;
  Sort(a,N,M);
  For I:=1 to M do
    For J:=1 to N do
  writeln (a[I,J]);
END.

Кстати по идее если почитать литературу, то тут сортировка тоже не совсем корректная в плане шага. Так как мне изменить шаг, чтобы он был как у Хиббарда?

Сообщение отредактировано: Renbo - 17.12.2006 20:25

[volvo]

Я правильно помню, что "шаг Хиббарда" - это 1, 3, ... (2^k) - 1 ?

Тогда:

Procedure Sort( var a : mas; N, M:Integer);
Var
  d, i, t : integer;
  k : boolean;
  the_n: integer;
begin
  while ($1 shl the_n) < N do inc(the_n);
  dec(the_n); 
  d := pred($1 shl the_n); { <--- Находим максимальное значение шага Хиббарда }

  while d>0 do begin
    k:=true;
    while k do begin
      k:=false;
      for I:=1 to M do
        for J:=1 to N-d do begin
          if a[I,J] > a[I,J+d] then begin
            t:=a[I,J]; a[I,J]:=a[I,J+d]; a[I,J+d]:=t;
            k:=true;
          end;
        end;
    end;
    dec(the_n);
    d := pred($1 shl the_n); { <--- И уменьшаем его }
  end;
end;

[Renbo]

Правильно )
для вектора из 11 элементов шаги равны 7, 3, 1 - у Хиббарда,
8,4,2,1 - у Шелла.

а вот что означает $1 или $l и dec?
и чем отличается shl от div?


Сообщение отредактировано: Renbo - 17.12.2006 22:18

[volvo]

$1 - это 16-ричная запись числа, т.е. та же самая единица, просто как только дело касается битовых операций (shl/shr) я автоматически перехожу на 16-ричную запись - чтоб не ошибиться...

shl - это сдвиг на 1 бит влево, т.е. не деление, а наоборот, умножение на 2 (делается оно до тех пор, пока 2^the_n не будет больше N, потом the_n уменьшается на 1 и высчитывается шаг)

dec - уменьшение на 1

[Renbo]

спасиб огромное