Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Метод Шелла с шагом Хиббарда

Автор: Renbo 18.12.2006 0:20

вот собственно программа которая сортирует строки матрицы методом шелла с шагом 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.






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

Автор: volvo 18.12.2006 0:56

Я правильно помню, что "шаг Хиббарда" - это 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 18.12.2006 1:47

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

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

Автор: volvo 18.12.2006 2:06

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

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

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

Автор: Renbo 18.12.2006 3:34

спасиб огромное good.gif