Вопрос 2. Разработать многопоточную программу для сортировки массива чисел с плавающей точкой методом Хоара


Добавил:DMT
Дата создания:30 декабря 2007, 18:18
Дата обновления:30 декабря 2007, 18:18
Просмотров:8938 последний сегодня, 8:55
Комментариев: 2

Вопрос 2. Разработать многопоточную программу для сортировки массива чисел с плавающей точкой методом Хоара

up

Комментарии для "Вопрос 2. Разработать многопоточную программу для сортировки массива чисел с плавающей точкой методом Хоара"


Пользователь: ruslan
Сообщений: 23
Статус: Незримый
Зарегистрирован:
5 января 2008, 2:42
Был:29 января 2008, 21:23
ruslan
smsup
Дата: 11 января 2008, 1:30 Сообщение № 1
Код на C++
  1. //---------------------------------------------------------------------------
  2. #pragma hdrstop
  3. //---------------------------------------------------------------------------
  4. #pragma argsused
  5. #include <windows.h>
  6. #include <stdlib.h>
  7. #include <stdio.h>
  8. #include <conio.h>
  9. #define N 10
  10. struct data
  11. {
  12. int l;
  13. int u;
  14. float *x;
  15. };
  16. void swap (float *a, float *b)
  17. {
  18. float temp=*a; *a=*b; *b=temp;
  19. }
  20. DWORD WINAPI q_sort (void *params)
  21. {
  22. int i, j, m, l, u;
  23. float *x, t;
  24. l = ((data*)params)->l;
  25. u = ((data*)params)->u;
  26. x = ((data*)params)->x;
  27. data *d1 = new data();
  28. data *d2 = new data();
  29. if (l<u)
  30. {
  31. swap (&x[l], &x[l+random(u-l+1)]);
  32. t=x[l]; m=l;
  33. for (i=l+1; i<=u; i++)
  34. if (x[i]<t)
  35. {
  36. m++; swap (&x[m],&x[i]);
  37. }
  38. swap (&x[l], &x[m]);
  39. d1->l = l; d1->u = m-1; d1->x = x;
  40. d2->l = m+1; d2->u = u; d2->x = x;
  41. HANDLE thr[2];
  42. thr[0] = CreateThread(0,0,(LPTHREAD_START_ROUTINE)q_sort,(void *)d1,0,0);
  43. thr[1] = CreateThread(0,0,(LPTHREAD_START_ROUTINE)q_sort,(void *)d2,0,0);
  44. WaitForMultipleObjects(2,thr,true,INFINITE);
  45. delete d1;
  46. delete d2;
  47. }
  48. }
  49. int main(int argc, char* argv[])
  50. {
  51. int i; float *a=new float[N];
  52. data d;
  53. randomize();
  54. for (i=0; i<N; i++) a[i]=(float)(1 + rand()%100)/10;
  55. printf("\nСортировка методом Хоара\nДо сортировки\n");
  56. for (i=0; i<N; i++) printf (" %.2f ", a[i]);
  57. d.l = 0;
  58. d.u = N-1;
  59. d.x = a;
  60. q_sort ((void*)&d);
  61. printf("\nПосле сортировки\n");
  62. for (i=0; i<N; i++) printf (" %.2f ", a[i]);
  63. getch();
  64. return 0;
  65. }
  66. //---------------------------------------------------------------------------
  67.  
При использовании обязательна ссылка на http://DMTSoft.ru
Пользователь: ruslan
Сообщений: 23
Статус: Незримый
Зарегистрирован:
5 января 2008, 2:42
Был:29 января 2008, 21:23
ruslan
smsup
Дата: 14 января 2008, 0:26 Сообщение № 2
Несколько слов про метод Хоара...

Быстрая сортировка Хоара. Массив разбивается на две части таким образом, чтобы каждый элемент левой части был не больше любого элемента правой части. Затем для каждой из этих двух частей подпрограмма вызывается рекурсивно. Иными словами, схема подпрограммы будет выглядеть так:

void qsort(int l, int u, int *x)
{
if(l>=u) return;
Разбиение массива на две части;
qsort(l,p-1,x); // p – середина массива
qsort(p+1,u,x);
}

Под серединой массива p понимается индекс такого элемента, что для любых i<p<j имеют место неравенства x[i]<=x[p]<=x[j]. Данная подпрограмма будет сортировать элементы x[l],x[l+1],...,x[u]. Для сортировки всего массива она вызывается как [B]qsort(0,n-1,x)[I].

Опишем алгоритм разбиения массива, индексы элементов которого имеют значения l,l+1,...,u. Будем разбивать этот массив на два из следующих соображений. Установим t=x[l]. Будем перебирать элементы массива, начиная с x[l]. Схема массива представлена на рис. 2.1.


image1


Здесь m – индекс последнего элемента, меньшего, чем t, i – номер элемента, начиная с которого массив еще не разбит, т.е. i – индекс рассматриваемого элемента.

Если x[i]>=t, то, увеличивая i на 1, мы расширяем область, для элементов которой известно, относятся они к левой или правой области разбиения. Если же x[i]<t, то, меняя местами x[i] и x[m+1] и увеличивая m и i на 1, мы вновь расширяем область, разбиение которой известно.

Получаем следующие операции:

t=x[l];
m=l;
for(i=l+1; i<=u; i++)
if (x[i]<t)
{
m++; swap (m,i);
}
swap (l,m);


последняя из которых меняет местами x[l] и x[m].

Пример. Применим быструю сортировку Хоара для следующих входных данных:
55, 41, 59, 26, 53, 58, 97, 93

• При i=1 будет x[1]<55, m=1, и x[1] поменяется местами сам с собой.
• При i=2 будет x[2]>=55.
• При i=3 будет x[3]<55, m=2, и x[3] поменяется местами c x[2]; получим массив:
55, 41, 26, 59, 53, 58, 97, 93.
• При i=4 будет x[4]<55, m=3, и x[4] поменяются местами с x[3]:
55, 41, 26, 53, 59, 58, 97, 93.
• При i>4 элементы x[i]>=55, поэтому массив остается прежним.
После цикла x[l] и x[m] меняются местами. Получим массив, равный искомому разбиению:

53, 41, 26, 55, 59, 58, 97, 93.


Для дальнейшей сортировки нужно вызвать подпрограммы qsort(0,2,x) и qsort(4,7,x).