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

@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)
    {

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

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

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

Решение