В статье Stable Minimum Storage Merging by Symmetric Comparisons приведен псевдокод алгоритма, по которому я написал программу на С (код здесь).
Она не работает (результат слияния 2-х упорядоченных массивов не упорядочен).
Собственно, вопросы:
- Я ошибся в перекодировании алгоритма с псевдокода на C ?
- или я чего-то не понял в статье и приведенный алгоритм в принципе не работает ? (с чего бы это ?)
Алгоритм
Algorithm 1 Symmerge algorithm
Symmerge (A, first1, first2, last)
if first1 < first2 and first2 < last then
m <- (first1 + last)/2
n <- m + first2
if first2 > m then
start <- Bsearch (A, n - last, m, n - 1)
else
start <- Bsearch (A, first1, first2, n - 1)
end <- n - start
Rotate (A, start, first2, end)
Symmerge (A, first1, start, m)
Symmerge (A, m, end, last)
Bsearch (A, l, r, p)
while l < r
m <- (l + r ) / 2
if A[m] <= A[p - m]
then l m + 1 ;
else r m;
return l
Часть кода, соответствующая алгоритму
Symmerge (int A[], int first1, int first2, int last)
{
printf ("Symm %d %d %d\n",first1,first2,last);
int start, end, m, n;
if (first1 < first2 && first2 < last) {
m = (first1 + last)/2;
n = m + first2;
if (first2 > m) {
start = Bsearch (A, n - last, m, n - 1);
} else {
start = Bsearch (A, first1, first2, n - 1);
}
end = n - start;
Rotate (A, start, first2, end);
Symmerge (A, first1, start, m);
Symmerge (A, m, end, last);
}
}
int
Bsearch (int A[], int l, int r, int p)
{
int m;
while (l < r) {
m = (l + r ) / 2;
if (A[m] <= A[p - m])
l = m + 1 ;
else r = m;
}
return l;
}
Функцию Rotate() тестировал (да и в ее коде печать массива до и после есть), крутит нормально.
Вожусь давно, почему не работает (точнее почему этот алгоритм должен работать) не понимаю.
В тайне надеюсь, что я что-то не понял в псевдокоде и поэтому не работает.
UPDATE 1 (на комментарий @jmu)
Rotate
Взято отсюда
Псевдокод
/* Функция swap(a, b, m) меняем местами:
* x[a..a+m-1] и x[b..b+m-1]
*/
if rotdist == 0 || rotdist == n
exit
i = p = rotdist
j = n - p
while i != j
/* инвариант:
x[0..p-i] двигать не нужно
x[p-i..p-1] = a (нужно поменять с b)
x[p..p+j-1] = b (нужно поменять с a)
x[p+j..n-1] двигать не нужно */
if i > j
swap(p-i, p, j)
i -= j
else
swap(p-i, p+j-i, i)
j -= i
swap(p-i, p, i)
Реализация Rotate
void
swap (int a[], int f, int t, int l)
{
int tt;
for (l+=f; f < l; f++,t++) {
tt = a[f];
a[f] = a[t];
a[t] = tt;
}
}
void
rotate (int a[], int n, int dist)
{
if (dist == 0 || dist == n)
return;
int i, j, p;
i = p = dist;
j = n - p;
while (i != j) {
if (i > j) {
swap (a, p-i,p,j);
i -= j;
} else {
swap (a, p-i,p+j-i,i);
j -= i;
}
}
swap (a, p-i,p,i);
}
Rotate (int *A, int left, int r, int end)
{
int *a = A+left, n = end-left+1, m = r-left;
printf ("l=%d r=%d e=%d\n",left,r,end);
pri("++ ");
rotate (a,n,m);
pri("-- ");
}