通缉:工作Bose-Hibbard排序实现最好用C语言

Question

请指出一个有效的Bose-Hibbard Sort实现的代码,最好是类似C语言的代码.

我正在尝试在C#中实现该算法,但我没有该算法的副本.我唯一的样本是Fortran实现,它是Hibbard原始Algol版本的"免费翻译"(来自'一个简单的排序算法'期刊的ACM第10卷(1963)p142-50 - 我也没有) .Fortran版本似乎是错误的(它只进行了1次比较,如果它们已经排序则最终退出)所以我主要关注的是获得一个可用的版本来学习.

Answer 1

从原始文章的扫描PDF (从ACM数字图书馆下载),在Mac上通过copy'n'paste进行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 ₂ '.换行符与原文相同.这种情况早于"结构化编程"革命 - 现在您可以看到为什么结构化编程是一个好主意.它也早于仔细,清晰的代码布局.看到"两个字"的标签和程序名称很有意思.(在Algol-60的修订报告(PDF或HTML)中,它说:空白空间或更改为新行等印刷特征在参考语言中没有意义.但是,它们可以自由使用以方便阅读. 这意味着,这似乎是在现代计算机语言"两个词"是的Algol-60只是一个字;与谷歌搜索显示,关键字从变量等通过被强调或用粗体字标识或封闭在一些报价分化这种语言还使用了键盘上通常找不到的许多符号;这个程序中的三个例子是'×','↑'和'≤'.)

使用嵌套过程,您需要进行大量的"免费翻译"才能在Fortran中对此进行编码.

这里重新格式化 - 可能更容易看到代码是什么; 过多的"转到"陈述并不容易理解.现在你可以看到为什么Dijkstra写了'GOTO Considered Harmful'.

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