请为我指出有效的Bose-Hibbard Sort实现的代码,最好使用类似C的语言。
我正在尝试在C#中实现该算法,但是没有该算法的副本。我仅有的一个样本是Fortran实现,它是希伯德原始Algol版本的“免费翻译”(摘自ACM期刊第10卷(1963年)第142-50页的“一种简单的排序算法”,我也没有) 。Fortran版本似乎有错误(它只进行1个比较,如果已经排序,最终退出),所以我的主要重点是研究一个工作版本。
从原始文章的扫描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 ”。换行符与原来一样。这早于“结构化编程”革命之前- 现在您可以了解为什么结构化编程是一个好主意。它还早于仔细,清晰的代码布局。看到“两个单词”标签和过程名称很有趣。(在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