6

動作する Bose-Hibbard Sort 実装のコードを、できれば C に似た言語で示してください。

C# でアルゴリズムを実装しようとしていますが、アルゴリズムのコピーがありません。私が持っている唯一のサンプルは、Hibbard の元の Algol バージョンの「無料翻訳」である Fortran 実装です (「A simple sorting algorithm」 Journal of the ACM vol 10 (1963) p142-50 から - これも持っていません)。 . Fortran のバージョンにはバグがあるようです (正確に 1 つの比較を行い、既にソートされている場合は終了します)。そのため、私の主な焦点は、動作するバージョンを取得して研究することです。

4

1 に答える 1

10

元の記事のスキャンされた PDF (ACM デジタル ライブラリからダウンロード) から、Mac でコピー アンド ペーストして OCR を実行し、手動でクリーンアップしました (かなりの量):

procedure ternary sort (a, n); array a; integer n; begin integer j, L;
integer array x, y[0: log2(n-1)] ; integer procedure sum(w); array w;
begin integer j, s; s := 0; for j:= 0 step 1 until L do s := s+w[j]×2↑j; sum := s
end; procedure compare; begin real w;
if a[sum(x)] > a[sum(y)] then begin w := a[sum(x)]; a[sum(x)] := a[sum(y)];
a[sum(y)] := w end end;
L := entier log2(n-1); for j := 0 step 1 until L do begin x[j] := 0;
y[j] := if j = 0 then 1 else 0 end;
A: compare; j := 0;
C: go to if x[j] = y[j] = 0 then zero else if x[j] = y[j] = 1 then one else
if x[j] = 0 then first two else two;
zero: x[j] := y[j] := 1; if sum(y) ≤ n-1 then go to A;
one: y[j] := 0; go to A;
two: x[j] := 0; j := j+1; go to C;
first two: x[j] := y[j] := 0; if j = L then go to exit; j := j+1;
if y[j] = 1 then go to D; x[j] := y[j] := 1; if sum(y) > n-1 then
go to first two; if sum(y) < n-1 then j := 0;
D: x[j] := 0; y[j] := 1; go to A;
exit: end

オリジナルでは、「log2」関数は「log 2」として設定されています。改行は原作通り。これは「構造化プログラミング」革命よりも前のことです。構造化プログラミングが優れたアイデアである理由がわかります。また、慎重で明確なコード レイアウトよりも前のことです。「2 語」のラベルとプロシージャー名を見るのは興味深いことです。( Algol-60 の改訂レポート(PDF またはHTML ) では、次のように述べられています。空白スペースや新しい行への変更などのタイポグラフィの特徴は、参照言語では重要ではありません。ただし、読みやすくするために自由に使用できます。 . これは、現代のコンピューター言語で「2 つの単語」に見えるものは、Algol-60 では 1 つの単語にすぎないことを意味します。Google で検索すると、下線が引かれているか、太字で印刷されているか、何らかの引用符で囲まれていることで、キーワードが変数などと区別されていることがわかります。この言語はまた、キーボードでは通常見られない多くの記号を使用していました。このプログラムの 3 つの例は、「×」、「↑」、および「≤」です。)

ネストされたプロシージャを使用すると、これを Fortran でコーディングするには、かなり多くの「自由な変換」が必要になります。

ここでは、再フォーマットされています。おそらく、コードが何であるかを確認するのが少し簡単です。「go to」ステートメントが多すぎると、理解しやすくなりません。これで、ダイクストラが「GOTO は有害であると見なす」と書いた理由がわかります。

procedure ternary sort (a, n); array a; integer n; 
begin
    integer j, L;
    integer array x, y[0: log2(n-1)]; 
    integer procedure sum(w); array w;
    begin
        integer j, s; 
        s := 0; 
        for j:= 0 step 1 until L do s := s+w[j]×2↑j; 
        sum := s
    end;
    procedure compare;
    begin
        real w;
        if a[sum(x)] > a[sum(y)] then
        begin
            w := a[sum(x)]; 
            a[sum(x)] := a[sum(y)];
            a[sum(y)] := w 
        end 
    end;
    L := entier log2(n-1);
    for j := 0 step 1 until L do
    begin
        x[j] := 0;
        y[j] := if j = 0 then 1 else 0
    end;
A:  compare; j := 0;
C:  go to if x[j] = y[j] = 0 then zero
          else if x[j] = y[j] = 1 then one
          else if x[j] = 0 then first two 
          else two;
zero:
    x[j] := y[j] := 1;
    if sum(y) ≤ n-1 then go to A;
one:
    y[j] := 0; 
    go to A;
two:
    x[j] := 0; 
    j := j+1; 
    go to C;
first two:
    x[j] := y[j] := 0;
    if j = L then go to exit; 
    j := j+1;
    if y[j] = 1 then go to D; 
    x[j] := y[j] := 1; 
    if sum(y) > n-1 then go to first two; 
    if sum(y) < n-1 then j := 0;
D:  x[j] := 0;
    y[j] := 1; 
    go to A;
exit:
end
于 2010-12-19T18:16:56.933 に答える