Требуются: рабочая реализация сортировки Бозе-Хиббарда, предпочтительно на C-подобном языке

Question

Пожалуйста, укажите мне код для работающей реализации сортировки Бозе-Хиббарда, предпочтительно на языке, подобном Си.

Я пытаюсь реализовать алгоритм в C#, но у меня нет копии алгоритма. Единственный пример, который у меня есть, - это реализация на Фортране, которая представляет собой "свободный перевод" оригинальной версии Алгола Хиббарда (из "Простого алгоритма сортировки", журнал ACM, том 10 (1963), стр. 142-50 - которого у меня тоже нет), Версия на Фортране, кажется, содержит ошибки (она делает ровно 1 сравнение и завершает работу, если они уже отсортированы), поэтому моя основная задача - получить рабочую версию для изучения.

Answer 1

Из отсканированного PDF оригинальной статьи (загруженной из цифровой библиотеки ACM) OCR копировал copy'n'paste на Mac, а затем очищал вручную (довольно много):

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) говорится: " Типографские функции, такие как пробел или переход на новую строку, не имеют значения в справочном языке. Однако они могут свободно использоваться для облегчения чтения"). Это означает, что то, что кажется "двумя словами" в современных компьютерных языках, - это всего лишь одно слово в Алголе-60, поиск в Google показывает, что ключевые слова были отделены от переменных и т. Д., Подчеркнуты или напечатаны жирным шрифтом или заключены в кавычки некоторых sort. Язык также использовал несколько символов, которые обычно не встречаются на клавиатурах; три примера в этой программе: "×", "↑" и "≤".)

С вложенными процедурами вам понадобится довольно много "бесплатных переводов", чтобы кодировать это на Фортране.

Здесь он переформатирован - возможно, немного легче увидеть, что это за код; Изобилие утверждений "перейти к" не облегчает понимание. Теперь вы можете понять, почему Дейкстра написал "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