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

Question

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

• книга из Sedgewick R.
• это SO question

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

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

odd-even-merge sort for 32 inputs http://flylib.com/books/3/55/1/html/2/images/11fig07.gif (кликабельны)

Я скопировал код из 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 для испытаний на моей аппаратной платформе.

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

• PoC.sort.sortnet.oddevensort
• PoC.sort.sortnet.bitonicsort

---

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

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

Википедия: odd-even mergesort

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

Answer 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); 
      } 
     } 
     } 
    } 
} 

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

Answer 2

Следующий код работает для массивов любого размера и не является рекурсивным. Это прямой порт от реализации the corresponding function в модуле Algorithm::Networksort от Perl. Реализация соответствует алгоритму, описанному Кнутом в «Искусство программирования», том 3 (алгоритм 5.2.2M). Это не поможет реально исправить алгоритм, но он по крайней мере, дает рабочую нерекурсивную реализацию Бэтчер нечетным даже слияние с только три вложенными циклами :)

#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, у вас будет хорошее объяснение того, как и почему работает алгоритм, а также несколько дополнительных деталей.

Answer 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); 
}