algorithm - 想要: working Bose-Hibbard Sort implementation preferably in C-like language

请为我指出有效的Bose-Hibbard Sort实现的代码，最好使用类似C的语言。

我正在尝试在C#中实现该算法，但没有该算法的副本。我仅有的一个示例是一个Fortran实现，它是希伯德原始Algol版本的“免费翻译”(摘自ACM期刊第10卷(1963年)第142-50页的“一种简单的排序算法”，我也没有) 。 Fortran版本似乎有问题(它只进行1个比较，如果已经排序，最终退出)，所以我的主要重点是研究一个可用的版本。

最佳答案

从original article(从ACM数字图书馆下载)的扫描PDF中，在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”功能设置为“log2”。换行符与原来一样。这早于“结构化编程”革命之前-现在您可以了解为什么结构化编程是一个好主意。它还早于仔细，清晰的代码布局。看到“两个词”标签和过程名称很有趣。 (在Revised Report for Algol-60(PDF或HTML)中，它表示:打印功能(例如空白或换行)在引用语言中没有意义。但是，可以自由使用它们来促进阅读。这意味着在现代计算机语言中似乎是“两个单词”，在Algol-60中只是一个单词；在Google上搜索表明，这些关键字与变量等有所区别，是用下划线或粗体显示或用某种引号引起来。使用了许多通常在键盘上找不到的符号；此程序中的三个示例是“×”，“↑”和“≤”。)

使用嵌套过程，您需要大量的“免费翻译”才能在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