Реализовать многопоточную сортировку динамического массива целых чисел

@igdev · Регистрация: 22.04.2016

Студворк — интернет-сервис помощи студентам

Есть задание:
Написать программу, которая выполняет сортировку динамического массива целых чисел, количество элементов которого задает пользователь после соответствующего запроса. Реализовать однопоточную и многопоточную сортировку массива. Отсортированный массив записать в файл.

Все, что нужно реализовать для однопоточности - я сделал. Для однопоточной сортировки я реализовал быструю сортировку. А вот с многопоточной сортировкой беда (в данном случаи, я выбрал сортировку Шелла с применением последовательности Седжвика). Никак не получается.

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

Свой код прилагаю:
Файл ArraySorting.h

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
#include "stdafx.h"
#include <iostream>
#include <Windows.h>
#include <fstream>
#include <cstdlib>
#include <time.h>
#include <stdio.h>
#include <thread>
 
#define MAXSTACK 2048 // максимальный размер стека
 
using namespace std;
 
template <class T>
class ArraySorting
{
public:
    ArraySorting();
    ~ArraySorting();
    void setArraySize(T); // Задание размера массива
    void arrayInitialization(); // Инициализация массива
    void printArray(); // Вывод массива на екран
    void printArrayCopy(); // Вывод копии массива на екран
    void writeToFile(); // Запись массива в файл
    T increment(long inc[], long size); // Инкремент для сортировки Шелла с 
                                    // применением последовательности Седжвика                                 
    void shellSorting(); // Сортировка массива
    void qSortI(); // Сортировка Хоара
    void readFromFile(); // Чтение с файла
    void arrayCopys();
    void sorting(int s, long i, long j, long seq[40], long inc);
 
private:
    T *array; // Начальный массив
    T *arrayCopy; // Копия массива
    INT64 arraySize; // Размер массива
 
};
 
 
template <class T>
ArraySorting<T>::ArraySorting()
{
    array = new T[0];
    arrayCopy = new T[0];
}
 
template <class T>
ArraySorting<T>::~ArraySorting()
{
    delete[] array;
    //delete[] arrayCopy;
}
 
 
 
// Задание размера массива
template <class T>
void ArraySorting<T>::setArraySize(T size)
{
    arraySize = size;
}
 
// Инициализация массива
template <class T>
void ArraySorting<T>::arrayInitialization()
{
    srand(time(0));
 
    array = new T[arraySize];
 
    // Заполняем массив случайными цыфрами от 1 до 9
    for (int counter = 0; counter < arraySize; counter++)
    {
        array[counter] = 1 + rand() % 9;
    }
}
 
 
// Вывод массива на екран
template <class T>
void ArraySorting<T>::printArray()
{
    for (int counter = 0; counter < arraySize; counter++)
    {
        cout << array[counter] << " ";
    }
}
 
// Вывод копии массива на екран
template <class T>
void ArraySorting<T>::printArrayCopy()
{
    for (int counter = 0; counter < arraySize; counter++)
    {
        cout << arrayCopy[counter] << " ";
    }
}
 
// Запись массива в файл
template <class T>
void ArraySorting<T>::writeToFile()
{
    ofstream file;
    file.open("array.bin", ios::out | ios::binary);
    for (int counter = 0; counter < arraySize; counter++)
    {
        file.write((char *)&array[counter], sizeof(T));
    }
    file.close();
}
 
 
// Чтение из файла
template <class T>
void ArraySorting<T>::readFromFile()
{
    ifstream instrm("array.bin", ios::binary);
    int a = 0;
    // читаем числа по одному из файла и выводим 
    while (instrm.read((char *)&a, sizeof(T)))
        cout << a << ' ';
    cout << '\n';
 
}
 
 
template <class T>
void ArraySorting<T>::arrayCopys()
{
    arrayCopy = new T[arraySize];
    for (int counter = 0; counter < arraySize; counter++)
    {
        arrayCopy[counter] = array[counter];
    }
}
 
// Инкремент для сортировки Шелла с 
// применением последовательности Седжвика
template <class T>
T  ArraySorting<T>::increment(long inc[], long size)
{
    int p1, p2, p3, s;
    p1 = p2 = p3 = 1;
    s = -1;
    do {
        if (++s % 2) {
            inc[s] = 8 * p1 - 6 * p2 + 1;
        }
        else {
            inc[s] = 9 * p1 - 9 * p3 + 1;
            p2 *= 3;
            p3 *= 3;
        }
        p1 *= 2;
    } while (3 * inc[s] < size);
    return s > 0 ? --s : 0;
}
 
template <class T>
void ArraySorting<T>::sorting(int s, long i, long j, long seq[40], long inc)
{
    while (s >= 0)
    {
        // сортировка вставками с инкрементами inc[]
        inc = seq[s--];
        for (i = inc; i < arraySize; i++) {
            T temp = arrayCopy[i];
            for (j = i - inc; (j >= 0) && (arrayCopy[j] > temp); j -= inc)
                arrayCopy[j + inc] = arrayCopy[j];
            arrayCopy[j + inc] = temp;
        }
    }
}
 
// Сортировка массива
template <class T>
void ArraySorting<T>::shellSorting()
{
    long inc = 0;
    long i = 0;
    long j = 0;
    long seq[40];
    int s;
    // вычисление последовательности приращений
    s = increment(seq, arraySize);
        
        // Моя попытка сделать многопоточную сортировку
    thread first (sorting(s, i, j, seq, inc)); // Компилятор ругается на эту строчку
    first.join();
}
 
 
// Сортировка Хоара
template<class T>
void ArraySorting<T>::qSortI() {
    long i, j; // указатели, участвующие в разделении
 
    long lb, ub; // границы сортируемого в цикле фрагмента
    long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов
    // каждый запрос задается парой значений,
    // а именно: левой(lbstack) и правой(ubstack)
    // границами промежутка
    long stackpos = 1; // текущая позиция стека
    long ppos; // середина массива
    T pivot; // опорный элемент
    T temp;
    lbstack[1] = 0;
    ubstack[1] = arraySize - 1;
    do {
        // Взять границы lb и ub текущего массива из стека.
        lb = lbstack[stackpos];
        ub = ubstack[stackpos];
        stackpos--;
        do {
            // Шаг 1. Разделение по элементу pivot
            ppos = (lb + ub) >> 1;
            i = lb; j = ub; pivot = array[ppos];
            do {
                while (array[i] < pivot) i++;
                while (pivot < array[j]) j--;
                if (i <= j) {
                    temp = array[i]; array[i] = array[j]; array[j] = temp;
                    i++; j--;
                }
            } while (i <= j);
            // Шаги 2, 3. Отправляем большую часть в стек и двигаем lb, ub
            if (i < ppos) { // правая часть больше
                if (i < ub) { // если в ней больше 1 элемента - нужно
                    stackpos++; // сортировать, запрос в стек
                    lbstack[stackpos] = i;
                    ubstack[stackpos] = ub;
                }
                ub = j; // следующая итерация разделения
                // будет работать с левой частью
            }
            else { // левая часть больше
                if (j > lb) {
                    stackpos++;
                    lbstack[stackpos] = lb;
                    ubstack[stackpos] = j;
                }
                lb = i;
            }
        } while (lb < ub);// пока в меньшей части более 1 элемента
    } while (stackpos != 0); // пока есть запросы в стеке
}

Файл main.cpp

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
#include "stdafx.h"
#include <iostream>
#include <Windows.h>
#include <stdio.h>
#include <cstdlib>
#include <time.h>
#include <fstream>
#include <thread>
#include "ArraySorting.h"
 
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(0, "");
 
    INT64 size;
    
    cout << "Введите размер массива: " << endl;
    cin >> size;
 
    ArraySorting<int> myArray;
    
 
    myArray.setArraySize(size);
    myArray.arrayInitialization();
    //myArray.printArray();
    
    myArray.arrayCopys();
    
    
 
    long t1 = clock();
    //myArray.shellSorting();
    thread first([&myArray](){myArray.qSortI(); });
    long t2 = clock();
    cout << "\ntime sorting: " << t2 - t1 << endl;
 
    first.join();
 
    //myArray.printArray();
    long t3 = clock();
    thread second([&myArray](){myArray.writeToFile(); });
    long t4 = clock();
 
    cout << "\ntime writing to file: " << t4 - t3 << endl;
    second.join();
    //myArray.readFromFile();
 
    long t5 = clock();
    
    
    myArray.shellSorting();
    long t6 = clock();
 
    cout << "\ntime paralel sorting: " << t6 - t5 << endl;
    
    //myArray.printArrayCopy();
 
    system("PAUSE");
 
    return 0;
}

nd2 · 04.11.2016, 23:03

Сообщение от igdev

Как же его можно убрать?

Сделать правильную сортировку.

@igdev · 04.11.2016, 23:03 **[ТС]**

Сообщение от nd2

Я разве так показывал (в initializationTwoArrays())?

Сообщение от nd2

Что исправил? Сортировку?

Инициализацию.

@igdev · 04.11.2016, 23:23 **[ТС]**

nd2, передаю размер массива в функцию вот так:

C++
1
2
thread first(&ArraySorting<T>::quickSortR, this, array2, arraySize2 - 1);
thread second(&ArraySorting<T>::quickSortR, this, array3, arraySize2 - 1);

Но после этого, сортировка работает не постоянно. Раз нормально отсортирует, другой уже с отрицательным значением.

@igdev · 05.11.2016, 18:34 **[ТС]**

Или я не так передаю этот размер? Может, нужно было делать так?

C++
1
2
3
.............................................
thread first(&ArraySorting<T>::quickSortR, this, array2, arraySize2);
thread second(&ArraySorting<T>::quickSortR, this, array3, arraySize2);

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
// Рекурсивня сортировка Хоара для многопоточности
template<class T>
void ArraySorting<T>::quickSortR(T* a, long N) {
    // На входе - массив a[], a[N] - его последний элемент. 
 
    long i = 0, j = N - 1;   // поставить указатели на исходные  места
        T temp, p;
 
    p = a[N - 1 >> 1];    // центральный элемент 
 
    // процедура разделения 
    do {
        while (a[i] < p) i++;
        while (a[j] > p) j--;
 
        if (i <= j) {
            temp = a[i]; a[i] = a[j]; a[j] = temp;
            i++; j--;
        }
    } while (i <= j);
 
 
    // рекурсивные вызовы, если есть, что сортировать  
    if (j > 0) quickSortR(a, j);
    if (N - 1 > i) quickSortR(a + i, N - 1 - i);
}

Хотя, это, вроде, одно и то же.

Добавлено через 19 часов 10 минут
Проблема остаётся актуальной. Отладчиком у меня не получилось выловить ошибку. Получается, что я где-то выхожу за границу выделения памяти. Но вот где, не могу найти. Где может быть ошибка? В самой сортировке или же в методе слияния двух массивов?

nd2 · 05.11.2016, 21:12

Сообщение от igdev

Где может быть ошибка? В самой сортировке или же в методе слияния двух массивов?

Писал уже (по поводу того кода, который был):

Сообщение от nd2

В сортировке. После неё, в нулевых элементах - мусор.

Поставь точку останова перед слиянием и посмотри, что в массивах после сортировки получилось. Но это не значит, что со слиянием всё в порядке. Сначала нужно сортировку исправить, потом дальше смотреть.

@igdev · 05.11.2016, 22:38 **[ТС]**

nd2, с массивами, вроде, все нормально, мусора нет. Что-то со слиянием не то.

nd2 · 06.11.2016, 00:59

Сообщение от igdev

с массивами, вроде, все нормально, мусора нет.

Что-то исправлял?

@igdev · 06.11.2016, 02:00 **[ТС]**

nd2, Нет, ничего не исправлял, тестил. Как вы говорили, что А[N -1] последний элемент массива, так я и передавал.

C++
1
2
thread first(&ArraySorting<T>::quickSortR, this, array2, arraySize2 - 1);
thread second(&ArraySorting<T>::quickSortR, this, array3, arraySize2 - 1);

Как я выяснил, проблема в методе margeArrays(); который выполняет слияния двух массивов. После его выполнения и появляются артифакты в виде отрицательных чисел. Данная проблема не постоянная: один раз нормально все сольет в один массив, второй - в конце появляется отрицательное число, третий - уже два отрицательных числа.

nd2 · 06.11.2016, 03:08

Сообщение от igdev

проблема в методе margeArrays(); который выполняет слияния двух массивов. После его выполнения и появляются артифакты в виде отрицательных чисел. Данная проблема не постоянная: один раз нормально все сольет в один массив, второй - в конце появляется отрицательное число, третий - уже два отрицательных числа.

Сообщение от igdev

C++
1
2
3
4
// Повторяем сравнение элементов массивов array2 и array3 до тех пор 
// пока в каждом из них есть хотя бы один необработанный элемент 
while (i < arraySize2 && j < arraySize) 
{

C++
1
2
3
4
// Повторяем сравнение элементов массивов array2 и array3 до тех пор
// пока в каждом из них есть хотя бы один необработанный элемент
    while (i < arraySize2 && j < arraySize2)
    {

Новые блоги и статьи Все статьи Все блоги /
Рефакторинг программы уравнивания. Massaraksh7 26.05.2026 Пример по предыдущей записи в блоге. Но, надо заметить, что, во-первых, там оптимизация не только математики, но и работы с базой данных, и с графами, а во-вторых, это ещё не всё.	Использование TThread в Lazarus для математических вычислений. Massaraksh7 25.05.2026 Производя рефакторинг своих программ на предмет ускорения их работы, обратил внимание на такой аспект, как сокращение времени матвычислений. Дело в том, что приходится работать с большими матрицами. . .	Модель здравосохранения 18. Чем здоровее работник, тем быстрее выгорает anaschu 24.05.2026 Имитационная модель корпоративного здравоохранения: что показывает математика Сегодня в модели рабочего коллектива на AnyLogic появились три новые механики — выгорание через накопленную усталость,. . .	Модель здравосохранения 17. Планы на выгорание anaschu 23.05.2026 Вот конкретная схема реализации: В классе Работник добавить: накопленнаяУсталость — растёт каждый час работы, снижается в перерывы и болезни коэффициентПрезентеизма — снижает продуктивность. . .
Изменение цветов в палитре gif файла aka фавикона russiannick 23.05.2026 Изменение цветов в палитре gif файла, юзаемого как фавиконка в составе html-файла, помещенная в base64, средствами нативного Java Script, навеянное сном в майский день. Для работы необходим браузер,. . .	Модель здравосохранения 16. Слишком хорошие и здоровые сотрудники уходят, недовольные зарплатой anaschu 23.05.2026 Отладка увольнений и настройка производительности Сегодня во второй половине дня разобрались с механикой увольнений и настроили коэффициент сложности заданий. Вот что было сделано. . . .	Как я стал коммунистом))) Модель сохранения здоровья сотрудников, запись блога номер 15 anaschu 23.05.2026 Внезапно хорошее здоровье сотрудников не нужно капиталистам?))	Модель здравоСохранения 15. Как мы чинили AnyLogic модель рабочего коллектива: сочленение диаграммы состояний болезней и поломок в ресурспул anaschu 23.05.2026 Как мы чинили AnyLogic модель рабочего коллектива Сегодня разобрались с пятью багами, из-за которых модель либо падала с ошибкой, либо давала совершенно бессмысленные результаты. Каждый баг был. . .

@igdev 79 / 67 / 28 Регистрация: 22.04.2016 Сообщений: 384
	05.11.2016, 22:38 [ТС]
	nd2, с массивами, вроде, все нормально, мусора нет. Что-то со слиянием не то. Миниатюры 0

Реализовать многопоточную сортировку динамического массива целых чисел

Решение