0 / 0 / 0
Регистрация: 10.10.2018
Сообщений: 5
1

Многопоточная быстрая сортировка (уменьшить время работы)

09.11.2018, 18:27. Показов 1143. Ответов 2
Метки нет (Все метки)

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include "pch.h"
#include <iostream>
#include<stdio.h>
#include<ctime>
#include<vector>
#include<thread>
#include<chrono>
#include<mutex>
using namespace std;
using namespace chrono;
mutex mut;
void ThreadRecuesQuickSort(int arr[], int left2, int right2) {
    int i2 = left2, j2 = right2;
    int tmp2;
    int pivot2 = arr[(left2 + right2) / 2];
    while (i2 <= j2) {
        while (arr[i2] < pivot2)
            i2++;
        while (arr[j2] > pivot2)
            j2--;
        if (i2 <= j2) {
            tmp2 = arr[i2];
            arr[i2] = arr[j2];
            arr[j2] = tmp2;
            i2++;
            j2--;
        }
    }
}
void ThreadQuickSort(int arr[], int left1, int right1) {
    mut.lock();
    int i1 = left1, j1 = right1;
    int tmp1;
    int pivot1 = arr[(left1 + right1) / 2];
    while (i1 <= j1) {
        while (arr[i1] < pivot1)
            i1++;
        while (arr[j1] > pivot1)
            j1--;
        if (i1 <= j1) {
            tmp1 = arr[i1];
            arr[i1] = arr[j1];
            arr[j1] = tmp1;
            i1++;
            j1--;
        }
    };
    mut.unlock();
    if (left1 < j1) {
        thread thr3(ThreadQuickSort, arr, left1, j1);
        thr3.join();
    }
    if (i1 < right1) {
        thread thr4(ThreadQuickSort, arr, i1, right1);
        thr4.join();
    }
}
 
void quickSort(int arr[], int left, int right) {
    int i = left, j = right;
    thread thr3(ThreadQuickSort, arr, left, j);
    thr3.join();
    if (left < j) {
        thread thr1(ThreadQuickSort, arr, left, j);
        thr1.join();
    }
    if (i < right) {
        thread thr2(ThreadQuickSort, arr, i, right);
        thr2.join();
    }
 
}
 
void print(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << endl;
    }
    cout << endl;
}
 
int main()
{
    setlocale(LC_ALL, "rus");
    srand(time(0));
    int n;
    cin >> n;
    int i;
    int* arr = new int[n];
    for (i = 0; i < n; i++) {
        arr[i] = rand();
    }
    quickSort(arr, 0, n - 1);
    mut.lock();
    cout << "sorted array :" << endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << endl;
    }
    mut.unlock();
    cout << "Время выполнения:" << clock() / 1000.0<<endl; // искомое время
    system("pause");
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.11.2018, 18:27
Ответы с готовыми решениями:

Многопоточная быстрая сортировка
Столкнулся с проблемой как сделать многопоточную быструю сортировку. Основную часть кода написал,...

Многопоточная быстрая сортировка
Здравствуйте!Для написания использовал код однопоточной сортировки...

Уменьшить время работы компилятора
var a, a2: string; i, k: integer; begin read(a); for i := 1 to length(a) do ...

Как уменьшить время работы программы?
#include&lt;iostream&gt; using namespace std; int main() { int a,m,n; double d,o,w; ...

2
С чаем беда...
Эксперт CЭксперт С++
9988 / 5341 / 1460
Регистрация: 18.10.2014
Сообщений: 12,835
09.11.2018, 18:32 2
Отформатируйте код программы. Невозможно читать.

Цитата Сообщение от decoder12 Посмотреть сообщение
C++
1
void ThreadRecuesQuickSort(int arr[], int left2, int right2) {
Зачем в программе определена эта функция?

Цитата Сообщение от decoder12 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
thread thr3(ThreadQuickSort, arr, left, j);
thr3.join();
if (left < j) {
thread thr1(ThreadQuickSort, arr, left, j);
thr1.join();
}
if (i < right) {
thread thr2(ThreadQuickSort, arr, i, right);
thr2.join();
}
}
Что это вообще? Почему одно и то же делается 3 раза?

И какой вообще может быть смысл в многопоточности, если за запуском каждого потока сразу же делается join для него?
1
0 / 0 / 0
Регистрация: 10.10.2018
Сообщений: 5
11.11.2018, 20:22  [ТС] 3
Спасибо на счет "3 раза одно и то же",но join если не после то когда?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.11.2018, 20:22
Помогаю со студенческими работами здесь

Как уменьшить время работы макроса?
Добрый вечер! Суть проблемы: Открыто две книги, в одной макрос, делаем активной ту в которой...

Как уменьшить время работы программы?
const nmax=10000; var a:array of integer; n,m,i,j,x:integer; f:boolean; begin...

Сортировки: быстрая, вставками. Сравнить время работы на последовательностях разной длины
Быстрая сортировка, сортировка вставками. Необходимо реализовать эти алгоритмы сортировки и...

кто-нибудь сможет уменьшить время работы задачи?
эта задача с сайта http://acm.timus.ru/problem.aspx?space=1&amp;num=1150, он ее не пропускает тк она...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru