0

ネットでいくつかのマージソートアルゴリズムを見つけて、これを貼り付けました。要素が以前あった場所の情報を保持するために、インデックスを保持します。しかし、各要素に同じ値を持つ配列をフィードすると、インデックスがシャッフルされることがわかりました。別のマージ方法を使用する必要がありますか?

procedure TMSortNode.MergeSort(values, indices: TMValueArrayPtr; L, R: Integer);
var
  i, j, k, m : Integer;

begin
If (l < r) Then
begin
m:= (r+l) div 2;

MergeSort(values, indices, l, m );
MergeSort(values, indices, m+1, r );

For i:= l To m Do
begin
  FValueBuffer[i]:= values^[i];
  FIndexBuffer[i]:= indices^[i];
end;
i:= l;

For j:= m+1 To r Do
begin
  FValueBuffer[r+m+1-j]:= values^[j];
  FIndexBuffer[r+m+1-j]:= indices^[j];
end;
j:= r;

For k:= l To r Do
begin
  If (FValueBuffer[i] <= FValueBuffer[j]) Then
  begin
    values^[k]:= FValueBuffer[i];
    indices^[k]:= FIndexBuffer[i];
    inc(i);
  end
  else
  begin
    values^[k]:= FValueBuffer[j];
    indices^[k]:= FIndexBuffer[j];
    dec(j);
     end;
    end;
  end;
end;

編集：

これは正しい安定したマージ部分です:

length := r-l+1;
For i:= 0 To length-1 Do
begin
  FValueBuffer[i]:= values^[l+i];
  FIndexBuffer[i]:= indices^[l+i];
end;

j := 0;
k := m-l+1;

for i := 0 to length-1 do
if k < length then
  begin
  if j <= m-l then
  begin
    if FValueBuffer[j] > FValueBuffer[k] then begin
      values^[l+i] := FValueBuffer[k];
      indices^[l+i] := FIndexBuffer[k];
      inc(k)
    end else begin
      values^[l+i] := FValueBuffer[j];
      indices^[l+i] := FIndexBuffer[j];
      inc(j);
    end;
  end
  else
  begin //only upper Entrys left
    values^[i+l] := FValueBuffer[k];
    indices^[i+l] := FIndexBuffer[k];
    inc(k);
  end;
end else begin //only superior Entrys left
  values^[i+l] := FValueBuffer[j];
  indices^[i+l] := FIndexBuffer[j];
  inc(j);
end;
4

1 に答える 1

1

試す

If (FValueBuffer[i] <= FValueBuffer[j]) その後 ...

(安定性を保つため、同等のアイテムを交換する必要はありません)

編集：

別の問題: 標準のマージは次のようになります。

  1. 左と右の両方の部分に未処理のアイテムが含まれている間、最小のアイテムを新しい場所に移動します
  2. 残りの未処理部分を移動します (存在する場合)

例：

procedure Merge(var c, d: array of Integer; l, m, r: Integer);
 var
   i, j, k: Integer;
 begin
   i := l;
   j := m;
   k := l;
   while (i < m) and (j <= r) do
     if c[i] <= c[j] then begin
       d[k] := c[i];
       Inc(k);
       Inc(i);
     end
     else begin
       d[k] := c[j];
       Inc(k);
       Inc(j);
     end;
   while i < m do begin
     d[k] := c[i];
     Inc(k);
     Inc(i);
   end;
   while k <= r do begin
     d[k] := c[j];
     Inc(k);
     Inc(j);
   end;
  end;

しかし、最初のバリアントは左右のパーツの境界を超えています (これを避けるために、余分な価値のあるセンチネル アイテムを使用できます。追加の労力と場所が必要です)。

この問題は、2番目のバージョンで考慮されているようです

于 2012-09-13T17:14:23.783 に答える