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


Добавил:DMT
Дата создания:28 апреля 2008, 14:32
Дата обновления:28 апреля 2008, 14:38
Просмотров:9390 последний сегодня, 20:01
Комментариев: 4
Программа,исходник реализующий параллельную сортировку Бетчера на Си(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++
  1. int log2(int arg) {
  2. int i, tmp;
  3. i = -1;
  4. tmp = arg;
  5. while(arg!=0) {
  6. arg=arg>>1;
  7. i++;
  8. }
  9. arg=1;
  10. arg=arg<<i;
  11. return(i);
  12. }
  13.  
  14. int smes(int *y1,int *y2,int n,int *z){
  15. if (n==1){
  16. if (y1[0]<y2[0]){
  17. z[0]=y1[0];z[1]=y2[0];
  18. }else{
  19. z[0]=y2[0];z[1]=y1[0];
  20. }
  21. return (1);
  22. }
  23. int i,n_2=n/2;
  24. int *a=new int[n];
  25. int *b=new int[n];
  26. for (i=0;i<n_2;i++){
  27. a[i]=y1[i*2];
  28. b[i]=y2[i*2];
  29. a[i+n_2]=y1[i*2+1];
  30. b[i+n_2]=y2[i*2+1];
  31. }
  32. int *v=new int[n];
  33. smes(&a[0],&b[0],n_2,v);
  34. int *w=new int[n];
  35. smes(&a[n_2],&b[n_2],n_2,w);
  36. delete a;
  37. delete b;
  38.  
  39. z[0]=v[0];
  40. z[n*2-1]=w[n-1];
  41. int k=1;
  42. for(i=1;i<n;i++){
  43. if (v[i]<w[i-1])
  44. {
  45. z[k]=v[i];
  46. z[k+1]=w[i-1];
  47. } else {
  48. z[k+1]=v[i];
  49. z[k]=w[i-1];
  50. }
  51. k+=2;
  52. }
  53. delete w;
  54. delete v;
  55. }
  56.  
  57. int bet(int *x,int n){
  58. int i;
  59. if (n==1) return(1);
  60. int n_2=n/2;
  61. int *l=new int[n_2];
  62. int *r=new int[n_2];
  63. memcpy(&l[0],&x[0],n_2*sizeof(x[0]));
  64. memcpy(&r[0],&x[n_2],n_2*sizeof(x[0]));
  65. bet(&l[0],n_2);
  66. bet(&r[0],n_2);
  67. int *z;
  68. z=new int[n];
  69. smes(&l[0],&r[0],n_2,z);
  70. //for (i=0;i<n;i++)x[i]=z[i];
  71. memcpy(&x[0],&z[0],n*sizeof(x[0]));
  72. delete z;
  73. delete l;
  74. delete r;
  75. }
  76.  
  77. void betcher_sort(int *x,int n){
  78. int i;
  79. int n1=pow(2,log2(n))*2;
  80. int *x1;
  81. if (n!=n1){
  82. x1=new int[n1];
  83. memcpy(&x1[0],&x[0],n*sizeof(x[0]));
  84. for (i=n;i<n1;i++) x1[i]=-maxint;
  85. }else x1=x;
  86. bet(&x1[0],n1);
  87. int k=n1-n;
  88. if (n!=n1) {
  89. memcpy(&x[0],&x1[k],n*sizeof(x[0]));
  90. delete x1;
  91. }
  92. }
При использовании обязательна ссылка на http://DMTSoft.ru

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

up

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


Пользователь: glover02
Сообщений: 2
Статус: Незримый
Зарегистрирован:
19 июня 2008, 20:17
Был:19 июня 2008, 20:38
glover02
smsup
Дата: 19 июня 2008, 20:32 Сообщение № 1

Код на C++
  1. Как получить полный код программы?
  2.  
При использовании обязательна ссылка на http://DMTSoft.ru

Пользователь: glover02
Сообщений: 2
Статус: Незримый
Зарегистрирован:
19 июня 2008, 20:17
Был:19 июня 2008, 20:38
glover02
smsup
Дата: 19 июня 2008, 20:38 Сообщение № 2
sm
Пользователь: DMT
Сообщений: 123
Статус: Программист
Зарегистрирован:
18 октября 2007, 2:35
Был:31 мая, 23:33
DMT
smsup
Дата: 19 июня 2008, 21:23 Сообщение № 3
Если просто пришлите свой личный, полезный исходный код sm
У меня на распараллеливание сортировки Бетчера ушло 3 дня.
Можете сами написать sm
Пользователь: tigr240172
Сообщений: 1
Статус: Незримый
Зарегистрирован:
23 февраля 2010, 3:53
Был:24 февраля 2010, 15:24
tigr240172
smsup
Дата: 23 февраля 2010, 3:59 Сообщение № 4
Трудно дохдимый метод для меня sm
А можно увидеть полный код программы или полностью всю программу с открытым исходным кодом??