Как исправить этот нерекурсивный алгоритм сортировки нечетных и четных слияний?
Я искал нерекурсивный алгоритм сортировки нечетных и четных слияний и нашел 2 источника:
- книга от Седжвик Р.
- этот ТАК вопрос
Оба алгоритма идентичны, но неверны. Результирующая сеть сортировки не является сеткой сортировки с нечетным четным слиянием.
Вот изображение результирующей сети с 32 входами. Вертикальная линия между двумя горизонтальными линиями означает сравнение значения a[x] с a[y], если оно больше, то поменять местами значения в массиве.
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 для тестов на моей аппаратной платформе.
Другие реализации аппаратной сортировки с открытым исходным кодом:
Приложение:
Нечетно-четная сортировка (сорта Бэтчера) похожа на битоническую сортировку (не путать с битовой сортировкой Бэтчера). Но в аппаратном обеспечении этот алгоритм имеет большую сложность по размеру, чем битовая сортировка, тогда как задержка такая же.
Эти алгоритмы могут быть реализованы с хорошим использованием ресурсов по сравнению с быстрыми программными алгоритмами, такими как быстрая сортировка.
Википедия: нечетно-четное слияние
Замечания:
Поскольку сети сортировки являются статическими и не зависят от входных значений, для генерации сети не нужно сравнивать и менять местами. Это одна из причин, почему он может быть преобразован в аппаратное обеспечение. Мой код генерирует индексы для операций сравнения. В аппаратном обеспечении эти вертикальные соединения будут заменены схемами сравнения и обмена. Таким образом, несортированные данные будут проходить через сеть и на выходной стороне будут отсортированы.
3 ответа
Я думаю, что нашел решение. Я проверил это для 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 для обработки субблоков в группе. Цикл j имеет измененное значение start и abort для обработки нечетного количества шагов после слияния без генерации двойных шагов сравнения.
Следующий код работает для массивов любого размера и не является рекурсивным. Это прямой порт от реализации соответствующей функции в Perl Algorithm::Networksort модуль. Реализация соответствует алгоритму, описанному Кнутом в книге "Искусство компьютерного программирования", том 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, у вас будет хорошее объяснение того, как и почему работает алгоритм, а также несколько дополнительных деталей.
Это фиксированная нерекурсивная подпрограмма.
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);
}