6

请指点我为一个工作的 Bose-Hibbard 排序实现的代码，最好是用类似 C 的语言。

我正在尝试在 C# 中实现该算法，但我没有该算法的副本。我拥有的唯一示例是一个 Fortran 实现，它是 Hibbard 原始 Algol 版本的“免费翻译”（来自 ACM vol 10 (1963) p142-50 的“简单排序算法”期刊——我也没有） . Fortran 版本似乎有问题（它只进行了 1 次比较，如果它们已经排序则最终退出）所以我的主要重点是获得一个工作版本来研究。

4

1 回答 1

10

从原始文章的扫描 PDF （从 ACM 数字图书馆下载），通过在 Mac 上复制'n'粘贴 OCR'd，然后手动清理（相当多）：

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 ”。换行符和原来的一样。这早于“结构化编程”革命 - 现在您可以看到为什么结构化编程是一个好主意。它还早于仔细、清晰的代码布局。看到“两个词”标签和过程名称很有趣。（在Algol-60 （PDF 或HTML ）的修订报告中，它说：空格或换行等印刷特征在参考语言中没有意义。但是，它们可以自由使用以方便阅读. 这意味着在现代计算机语言中看似“两个词”的东西在 Algol-60 中只是一个词；用谷歌搜索表明关键字与变量等不同，通过加下划线或以粗体打印或用某种引号括起来。该语言还使用了许多键盘上通常没有的符号；该程序中的三个示例是“×”、“↑”和“≤”。）

使用嵌套过程，您需要大量的“免费翻译”才能在 Fortran 中对其进行编码。

在这里它被重新格式化 - 可能更容易看到代码是什么；过多的“转到”语句并不能使其更容易理解。现在你可以明白为什么 Dijkstra 写了“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 回答