program Sort;
{$APPTYPE CONSOLE}
uses
SysUtils;
Type
PList=^List;
List=Record
inf:Integer;
next:PList;
End;
Var
a,b,c:PList;
//Add element to list
Procedure pAddToList(Var elem:PList; i:Integer);
Var
q,p:PList;
Begin
New(q);
q^.inf:=i;
q^.next:=nil;
IF elem=nil Then elem:=q
Else
Begin
p:=elem;
While p^.next<>nil Do p:=p^.next;
p^.next:=q;
End;
End;
//Split lists
Procedure pSplitting(Var a,b,c:PList);
Var
p,bfin,cfin:PList;
flag:Boolean;
Begin
bfin:=b;
cfin:=c;
flag:=True;
//Flag is use for detect the number of list
While a<>nil Do
Begin
p:=a;
While (p^.next<>nil)and(p^.next^.inf>=p^.inf) Do p:=p^.next;
IF flag Then
Begin
IF bfin=nil Then b:=a
Else bfin^.next:=a;
bfin:=p;
a:=p^.next;
flag:=false;
End
Else
Begin
IF cfin=nil Then c:=a
Else cfin^.next:=a;
cfin:=p;
a:=p^.next;
flag:=True;
End;
End;
IF cfin<>nil then cfin^.next:=nil;
bfin^.next:=nil;
End;
//Mix lists
Procedure pMix(Var a,b,c:PList);
Var
p1,p2,afin:PList;
Begin
afin:=a;
While (b<>nil)and(c<>nil) Do
Begin
p1:=b;
While (p1^.next<>nil)and(p1^.next^.inf>=p1^.inf) Do p1:=p1^.next;
p2:=c;
While (p2^.next<>nil)and(p2^.next^.inf>=p2^.inf) Do p2:=p2^.next;
While (b<>p1^.next)and(c<>p2^.next) Do
Begin
IF b^.inf<c^.inf Then
Begin
IF afin=nil Then a:=b
Else afin^.next:=b;
afin:=b;
b:=b^.next;
End
Else
Begin
IF afin=nil Then a:=c
Else afin^.next:=c;
afin:=c;
c:=c^.next;
End;
End;
IF (b=p1^.next)and(c<>p2^.next) Then
Begin
afin^.next:=c;
afin:=p2;
c:=p2^.next;
End
Else
IF (b<>p1^.next)and(c=p2^.next) Then
Begin
afin^.next:=b;
afin:=p1;
b:=p1^.next;
End;
End;
IF (b=nil)and(c<>nil) Then
Begin
IF afin=nil Then a:=c
Else afin^.next:=c;
c:=nil;
End;
IF (c=nil)and(b<>nil) Then
Begin
IF afin=nil Then a:=b
Else afin^.next:=b;
b:=nil;
End;
End;
Var
i,n,tmp:integer;
p:PList;
Begin
Randomize;
Write('Input data{'+#10#13+'Enter number of elements: ');
ReadLn(n);
Write('Input list:');
For i:=1 To n Do
Begin
tmp:=Random(8)+1;
Write(' ',tmp);
pAddToList(a,tmp);
End;
pSplitting(a,b,c);
While c<>nil Do
Begin
pMix(a,b,c);
pSplitting(a,b,c);
End;
pMix(a,b,c);
p:=a;
i:=0;
Write(#10#13+'Output data{'+#10#13+'Sorted list:');
While p<>nil Do
Begin
Write(' ',p^.inf);
p:=p^.next;
Inc(i);
End;
WriteLn(#10#13+'}');
ReadLn;
End.
end.
Помогите!!!! Трехпутевое слияние
Товарищи!!! ПОМОГИТЕ, пожалуйста!!! очень нужна прога, реализующая алгоритм трехпутевого слияния на Delphi или хотя б ее алгоритм... Как?! Заранее благодарю...
Я Delphi не знаю, но писал такую прогу на С. Алгоритм смотри в 5-ой главе третего тома Кнута
Вот реализация алгоритмя трёхпутевого слияния (сортировка на 3х лентах) однонаправленных списков. Запара ещё та...
Спасибо огромное!!!! Жаль, что увидела твой ответ слишком поздно...(((