求购：工作玻色 - 希巴德排序实现preferably的类C语言 [英] Wanted: working Bose-Hibbard Sort implementation preferably in C-like language

问题描述

请点我到$ C $下一个工作玻色 - 希巴德分类实施，preferably的类C语言。

Please point me to code for a working Bose-Hibbard Sort implementation, preferably in a C-like language.

我想实现的算法在C＃中，但我没有算法的副本。唯一的样品我是一个Fortran实现，它是一个意译的希巴德的原陵的版本（从'一个简单的排序算法期刊ACM第10（1963）p142-50 - 我什么都没得到） 。该FORTRAN版本似乎是越野车（它正是1比较，并结束了，如果他们已经排序退出），所以我的主要重点是获得一个工作版本来研究。

I'm trying to implement the algorithm in C#, but I don't have a copy of the algorithm. The only sample I have is a Fortran implementation that is a "free translation" of Hibbard's original Algol version (from 'A simple sorting algorithm' Journal of the ACM vol 10 (1963) p142-50 — which I don't have either). The Fortran version appears to be buggy (it does exactly 1 compare and ends up exiting if they are already sorted) so my primary focus is to get a working version to study.

推荐答案

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

From a scanned PDF of the original article (downloaded from ACM Digital Library), OCR'd by copy'n'paste on a Mac, and then manually cleaned up (quite a lot):

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功能设置为日志 ₂ 。换行作为在原。这predates的结构化编程革命 - 现在你可以看到为什么结构化编程是一个好主意。它还predates小心，明确code布局。有趣的是，眼看'两个字'标签和程序的名称。 （在<一个href="http://portal.acm.org/citation.cfm?id=366193.366201&coll=DL&dl=GUIDE&CFID=2778014&CFTOKEN=53440748">Revised为陵-60 （PDF，或 HTML ）报告，它说：排版功能如空格或更改为新的生产线已经在参考语言没有意义。他们可能，但是，可以自由地用于促进阅读。的这意味着，这似乎是在现代计算机语言'两个字'是在陵-60只是一个字;与谷歌搜索显示，关键字是从变量等通过被强调或以黑体或封闭在某种行情分化的语言还采用了一些不正常的键盘中的符号;三个这个方案中的实例是×，↑和≤。）

In the original, the 'log2' functions are set as 'log₂'. Line breaks as in the original. This predates the 'structured programming' revolution - now you can see why structured programming is a good idea. It also predates careful, clear code layout. It is interesting seeing 'two word' labels and procedure names. (In the Revised Report for Algol-60 (PDF, or HTML), it says: Typographical features such as blank space or change to a new line have no significance in the reference language. They may, however, be used freely for facilitating reading. This means that what appears to be 'two words' in modern computer languages is just one word in Algol-60; searching with Google shows that the keywords were differentiated from variables etc by being underlined or printed in bold or enclosed in quotes of some sort. The language also used a number of symbols not normally found on keyboards; three examples in this program are '×', '↑', and '≤'.)

通过嵌套的程序，你需要相当多的免费翻译，以$ C C本$ Fortran语言。

With the nested procedures, you'd need quite a lot of 'free translating' to code this in Fortran.

这是重新格式化 - 这也许是一个比较容易看到的code是什么;多如牛毛'去'陈述并不能使它更容易理解。现在，你可以看到为什么Dijkstra算法写了GOTO是有害的。

Here it is re-formatted - it is perhaps a little easier to see what the code is; the plethora of 'go to' statements does not make it easier to understand. Now you can see why Dijkstra wrote '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

这篇关于求购：工作玻色 - 希巴德排序实现preferably的类C语言的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！