Как исправить этот нерекурсивный алгоритм сортировки нечетных четных-слияний?

Я искал нерекурсивный алгоритм сортировки нечетных и четных слияний и нашел 2 источника:

книга от Седжвика Р.
этот такой вопрос

Оба алгоритма идентичны, но неверны. Результирующая сеть сортировки не является сеткой сортировки с нечетным четным слиянием.

Вот изображение результирующей сети с 32 входами. Вертикальная линия между двумя горизонтальными линиями означает сравнение значения a [x] с a [y], если оно больше, то поменять местами значения в массиве.

_{(источник: flylib.com)}
(Интерактивный)

Я скопировал код с Java на C и заменил функцию exch на printf для печати кандидатов на обмен.

Когда вы рисуете диаграмму пар, можно увидеть, что генерируется слишком много пар.

Кто-нибудь знает, как исправить этот алгоритм?

Зачем мне нужна нерекурсивная версия?
Я хочу превратить эту сортировочную сеть в аппаратное обеспечение. Легко вставить этапы конвейера в нерекурсивные алгоритмы.

Я также исследовал рекурсивную версию, но она слишком сложна для преобразования алгоритма в конвейерное оборудование.

Мой код C:

#include <stdlib.h>
#include <stdio.h>

void sort(int l, int r)
{ int n = r-l+1;

  for (int p=1; p<n; p+=p)
    for (int k=p; k>0; k/=2)
      for (int j=k%p; j+k<n; j+=(k+k))
        for (int i=0; i<n-j-k; i++)
          if ((j+i)/(p+p) == (j+i+k)/(p+p))
              printf("%2i cmp %2i\n", l+j+i, l+j+i+k);
}
int main(char* argv, int args)
{ const int COUNT = 8;
  sort(0, COUNT);
}

Результат:

0 -o--------o-------------------------o---------------o-------------------------
   |        |                         |               |
1 -o--------|-o------o----------------|-o-------------o-o-----------------------
            | |      |                | |               |
2 -o-o------o-|------o-o--------------|-|-o----o--------o-o---------------------
   | |        |        |              | | |    |          |
3 -o-o--------o--------o--------------|-|-|-o--|-o--------o-o-------o-----------
                                      | | | |  | |          |       |
4 -o-o-o----o---o----o-----o----------o-|-|-|--o-|-o--------o-o-----o-o---------
   | | |    |   |    |     |            | | |    | |          |       |
5 -o-o-o----|-o-|-o--o-o---o-o---o------o-|-|----o-|-o--------o-o-----o-o---o---
            | | | |    |     |   |        | |      | |          |       |   |
6 -o-o-o-o--o-|-o-|----o-o---o-o-o-o------o-|------o-|----------o-o-----o-o-o-o-
   | | | |    |   |      |     |   |        |        |            |       |   |
7 -o-o-o-o----o---o------o-----o---o--------o--------o------------o-------o---o-

Когда я узнаю правильные пары обмена и алгоритм будет соответствовать изображению, я переведу его в VHDL для тестов на моей аппаратной платформе.

Другие реализации аппаратной сортировки с открытым исходным кодом:

Приложение:
Нечетно-четная сортировка слиянием (a.k.a сортировка дозатора) похожа на битоническую сортировку (не путать с битронной сортировкой дозирования). Но в аппаратном обеспечении этот алгоритм имеет большую сложность по размеру, чем битовая сортировка, а задержка такая же.

Эти алгоритмы могут быть реализованы с хорошим использованием ресурсов по сравнению с быстрыми программными алгоритмами, такими как быстрая сортировка.

Википедия: нечетно-четное слияние

Примечание:
Поскольку сети сортировки являются статическими и не зависят от входных значений, для генерации сети не нужно сравнивать и менять местами. Это одна из причин, почему он может быть преобразован в аппаратное обеспечение. Мой код генерирует индексы для операций сравнения. В аппаратном обеспечении эти вертикальные соединения будут заменены схемами сравнения и обмена. Таким образом, несортированные данные будут проходить через сеть и на выходной стороне будут отсортированы.

Ответ 1

Думаю, я нашел решение. Я проверил его на length = 2, 4, 8, 16.

Вот мой код:

void sort(int length)
{ int G = log2ceil(length);                      // number of groups
  for (int g = 0; g < G; g++)                    // iterate groups
  { int B = 1 << (G - g - 1);                    // number of blocks
    for (int b = 0; b < B; b++)                  // iterate blocks in a group
    { for (int s = 0; s <= g; s++)               // iterate stages in a block
      { int d = 1 << (g - s);                    // compare distance
        int J = (s == 0) ? 0 : d;                // starting point
        for (int j = J; j+d < (2<<g); j += 2*d)  // iterate startpoints
        { for (int i = 0; i < d; i++)            // shift startpoints
          { int x = (b * (length / B)) + j + i;  // index 1
            int y = x + d;                       // index 2
            printf("%2i cmp %2i\n", x, y);
          }
        }
      }
   }
}

Это решение вводит пятый цикл for-loop для обработки субблоков в группе. В j-цикле есть измененное значение начала и прерывания для обработки нечетных счетчиков шагов после слияния без создания удвоенных шагов сравнения.

Ответ 2

Следующий код работает для массивов любого размера и не является рекурсивным. Это прямой порт из реализации соответствующей функции в модуле Perl Algorithm::Networksort. Реализация соответствует алгоритму, описанному Кнутом в "Искусстве компьютерного программирования", том 3 (алгоритм 5.2.2M). Это не помогает исправить ваш алгоритм, но он по крайней мере дает вам рабочую нерекурсивную реализацию нечетно-четного объединения Batcher с тремя вложенными циклами:)

#include <math.h>
#include <stdio.h>

void oddeven_merge_sort(int length)
{
    int t = ceil(log2(length));
    int p = pow(2, t - 1);

    while (p > 0) {
        int q = pow(2, t - 1);
        int r = 0;
        int d = p;

        while (d > 0) {
            for (int i = 0 ; i < length - d ; ++i) {
                if ((i & p) == r) {
                    printf("%2i cmp %2i\n", i, i + d);
                }
            }

            d = q - p;
            q /= 2;
            r = p;
        }
        p /= 2;
    }
}

Если вы можете получить копию "Искусства компьютерного программирования", том 3, у вас будет хорошее объяснение того, как и почему работает алгоритм, а также несколько дополнительных деталей.

Ответ 3

Это фиксированная нерекурсивная подпрограмма.

void sort(int n)
{
  for (int p = 1; p < n; p += p)
    for (int k = p; k > 0; k /= 2)
      for (int j = k % p; j + k < n; j += k + k)
        //for (int i = 0; i < n - (j + k); i++) // wrong
        for (int i = 0; i < k; i++) // correct
          if ((i + j)/(p + p) == (i + j + k)/(p + p))
            printf("%2i cmp %2i\n", i + j, i + j + k);
}

или

void sort(int n)
{
  for (int p = 1; p < n; p += p)
    for (int k = p; k > 0; k /= 2)
      for (int j = 0; j < k; j++)
        for (int i = k % p; i + k < n; i += k + k)
          if ((i + j)/(p + p) == (i + j + k)/(p + p))
            printf("%2i cmp %2i\n", i + j, i + j + k);
}