Программа,исходник реализующий параллельную сортировку Бетчера на Си(C++)

Алгоритм :

Жестокая сортировачная сеть!!! Долго понимал алгоритм. Опишем теперь собственно алгоритм Бетчера, основанный на простом представлении входных данных длиной только 2 k (k N). К реальным данным можно всегда добавить несколько элементов ? , чтобы сделать длину входа равной степени двойки. Длина входа при этом не более чем удвоится, число же сравнений возрастет (предложение 2.4) лишь в постоянное число раз.

Алгоритм Бетчера (чет-нечет-слияние):

•  Задан вход (х 1, …, х„) R n , n=2 k , k N 0 .

•  Последовательности длины 1 отсортированы.

•  Сортируем с помощью этого алгоритма укороченные последовательности x 1 , …, и , …, х n , получая в результате у 1 <= … <= и , …, у n .

3) Смешиваем упорядоченные последовательности у 1 <= … <= и , …, у n , получая z 1 <= … <=z n .

(i) Две последовательности длины 1 соединяются таким образом в результате одного сравнения.

(ii) Смешиваем сначала более короткие последовательности y 1 <=y 3 <= … <= и <= <= … <=y n-1, получая ? 1 ?… , а затем смешиваем у 2 <= y 4 <=…<= и <= <= … <= y n и получаем w l <= … <= .

( iii ) Полагаем z 1 :=u 1 и z n := . Сравниваем u i+1 и w i и полагаем z 2 i := min ( u i + l , u i ·), z 2i+1 :=max(u i+1 , u i ),

Текст программы :

Код на C++
int log2(int arg) {
        int i, tmp;
        i = -1;
        tmp = arg;
        while(arg!=0) {
                arg=arg>>1;
                i++;
        }
        arg=1;
        arg=arg<<i;
        return(i);
}
 
int smes(int *y1,int *y2,int n,int *z){
 if (n==1){
                if (y1[0]<y2[0]){
                  z[0]=y1[0];z[1]=y2[0];
                }else{
                  z[0]=y2[0];z[1]=y1[0];
                }
                return (1);
          }
 int i,n_2=n/2;
 int *a=new int[n];
 int *b=new int[n];
 for (i=0;i<n_2;i++){
      a[i]=y1[i*2];
      b[i]=y2[i*2];
      a[i+n_2]=y1[i*2+1];
      b[i+n_2]=y2[i*2+1];
 }
 int *v=new int[n];
 smes(&a[0],&b[0],n_2,v);
 int *w=new int[n];
 smes(&a[n_2],&b[n_2],n_2,w);
 delete a;
 delete b;
 
 z[0]=v[0];
 z[n*2-1]=w[n-1];
 int k=1;
 for(i=1;i<n;i++){
     if (v[i]<w[i-1])
                {
                z[k]=v[i];
                z[k+1]=w[i-1];
                } else {
                z[k+1]=v[i];
                z[k]=w[i-1];
                }
     k+=2;
 }
   delete w;
   delete v;
}
 
int bet(int *x,int n){
   int i;
   if (n==1) return(1);
   int n_2=n/2;
   int *l=new int[n_2];
   int *r=new int[n_2];
   memcpy(&l[0],&x[0],n_2*sizeof(x[0]));
   memcpy(&r[0],&x[n_2],n_2*sizeof(x[0]));
   bet(&l[0],n_2);
   bet(&r[0],n_2);
   int *z;
   z=new int[n];
   smes(&l[0],&r[0],n_2,z);
   //for (i=0;i<n;i++)x[i]=z[i];
   memcpy(&x[0],&z[0],n*sizeof(x[0]));
   delete z;
   delete l;
   delete r;
}
 
void betcher_sort(int *x,int n){
int i;
              int n1=pow(2,log2(n))*2;
              int *x1;
              if (n!=n1){
                x1=new int[n1];
                memcpy(&x1[0],&x[0],n*sizeof(x[0]));
                for (i=n;i<n1;i++) x1[i]=-maxint;
              }else x1=x;
              bet(&x1[0],n1);
              int k=n1-n;
              if (n!=n1) {
                        memcpy(&x[0],&x1[k],n*sizeof(x[0]));
                        delete x1;
                        }
}
При использовании обязательна ссылка на http://DMTSoft.ru

Результаты работы программы: