0 / 0 / 0
Регистрация: 11.10.2017
Сообщений: 3
|
|
|
1
|
Многопоточная быстрая сортировка Dev C++
16.11.2017, 00:53. Показов 2164. Ответов 0
Очень нужна помощь! Написана программа быстрой сортировки массива (однопоточная и распараллелиная). Но нужно, что бы выводилось время счета разного объёма массива одним ядром и двумя ядрами (однопоточная программа). И время счета разного объёма массива 2 - мя потоками, 4 - мя потоками.
Однопоточная:
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
// Функция быстрой сортировки
void quickSort(int *numbers, int left, int right)
{
int pivot; // разрешающий элемент
int l_hold = left; //левая граница
int r_hold = right; // правая граница
pivot = numbers[left];
while (left < right) // пока границы не сомкнулись
{
while ((numbers[right] >= pivot) && (left < right))
right--; // передвигаем правую границу пока элемент [right] больше разрешающего элемента [pivot]
if (left != right) // если границы не сомкнулись
{
numbers[left] = numbers[right]; // передвигаем элемент [right] на место разрешающего
left++; // сдвигаем левую границу вправо
}
while ((numbers[left] <= pivot) && (left < right))
left++; // сдвигаем левую границу пока элемент [left] меньше разрешающего элемента [pivot]
if (left != right) // если границы не сомкнулись
{
numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
right--; // сдвигаем правую границу вправо
}
}
numbers[left] = pivot; // ставим разрешающий элемент на место
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot) // рекурсивно вызываем сортировку для левой и правой части массива
quickSort(numbers, left, pivot - 1);
if (right > pivot)
quickSort(numbers, pivot + 1, right);
}
int main()
{
int n;
int a[n];
// заполнение массива случайными числами
cin>>n;
for (int i = 0; i<n; i++)
a[i] = rand() % 20 - 10;
// вывод элементов массива до сортировки
for (int i = 0; i<n; i++)
printf("%d ", a[i]);
printf("\n");
quickSort(a, 0, 9); // вызов функции сортировки
// вывод элементов массива после сортировки
for (int i = 0; i<n; i++)
printf("%d ", a[i]);
printf("\n");
getchar();
return 0;
} |
|
Распараллелиная:
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#include <iostream>
using namespace std;
// Функция быстрой сортировки
void quickSort(int *numbers, int left, int right)
{
int pivot; // разрешающий элемент
int l_hold = left; //левая граница
int r_hold = right; // правая граница
pivot = numbers[left];
#pragma omp parallel num_threads(2)
{
while (left < right) // пока границы не сомкнулись
{
while ((numbers[right] >= pivot) && (left < right))
right--; // передвигаем правую границу пока элемент [right] больше разрешающего элемента [pivot]
if (left != right) // если границы не сомкнулись
{
numbers[left] = numbers[right]; // передвигаем элемент [right] на место разрешающего
left++; // сдвигаем левую границу вправо
}
while ((numbers[left] <= pivot) && (left < right))
left++; // сдвигаем левую границу пока элемент [left] меньше разрешающего элемента [pivot]
if (left != right) // если границы не сомкнулись
{
numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
right--; // сдвигаем правую границу вправо
}
}
numbers[left] = pivot; // ставим разрешающий элемент на место
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot) // рекурсивно вызываем сортировку для левой и правой части массива
quickSort(numbers, left, pivot - 1);
if (right > pivot)
quickSort(numbers, pivot + 1, right);
}
}
int main()
{
int n;
int a[n];
// заполнение массива случайными числами
cin>>n;
#pragma omp parallel for
for (int i = 0; i<n; i++)
a[i] = rand() % 20 - 10;
// вывод элементов массива до сортировки
#pragma omp parallel for
for (int i = 0; i<n; i++)
printf("%d ", a[i]);
printf("\n");
quickSort(a, 0, 9); // вызов функции сортировки
// вывод элементов массива после сортировки
#pragma omp parallel for
for (int i = 0; i<n; i++)
printf("%d ", a[i]);
printf("\n");
getchar();
return 0;
} |
|
0
|
(
