algorithmsortingalgol# Wanted: working Bose-Hibbard Sort implementation preferably in C-like language

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

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.

Solution

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
```

In the original, the 'log2' functions are set as 'log_{2}'. 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 '≤'.)

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

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
```

- How can building a heap be O(n) time complexity?
- What is the reason why std::rotate() is implemented this way?
- String to string compression algorithm?
- Computing index from timestamp
- Forward chaining and Backward chaining in java
- Brent's cycle detection algorithm
- The simplest algorithm for poker hand evaluation
- Partition a string into substrings that all have majority characters
- How do I check if a number is a palindrome?
- Algorithm / pseudo-code to create paging links?
- Algorithm to draw waveform from audio
- Find the maximum number of pieces a rod can be cut
- Cycling LED Modes using ControllerMate
- How to show a sudoku solution is unique?
- Randomly Splitting a Graph according to Conditions
- How to chunk array into nice grid of rows and columns, where columns always line up (all rows are even, or all are odd)?
- Fastest sort of fixed length 6 int array
- Can hash tables really be O(1)?
- Number of ways to tile a W x H Grid with 2 x 1 and 1 x 2 dominos?
- Is it possible to reduce number of comparisons from O(N^2) to O(N) in brute-force sorting by using multiplication?
- Mathematical explanation of Leetcode question: Container With Most Water
- manhattan skyline cover failing some test cases
- How to Correctly Group Rows by Column Values Using Union-Find in Java?
- Algorithm for Determining Tic Tac Toe Game Over
- Counting the number of positive integers that are lexicographically smaller than a specific number
- How to analyze time complexity of an algorithm with different running time
- What is the most efficient way of finding all the factors of a number in Python?
- A good way to find a vector perpendicular to another vector?
- Find the max average subarray with length at least k
- Flip bits in binary string and avoid 10 pattern