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

#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); // пока есть запросы в стеке
}

#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;
}

thread second(&ArraySorting<T>::shellSorting, this, array3, arraySize2);

std::is_array<std::vector<int>>::value//false =(

myArray.initializationTwoArrays();

template <class T>
void ArraySorting<T>::initializationTwoArrays()
{
    array2 = new T[arraySize2];
    array3 = new T[arraySize2];
 
    for (int counter = 0; counter < arraySize2; counter++)
    {
        array2[counter] = arrayCopy[counter];
    }
 
    for (int counter = 0, i = arraySize2; i < arraySize;    )
    {
        array3[counter++] = arrayCopy[i++];
    }
}

#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 initializationTwoArrays(); // Инициализация двух массивов, 
                                    // которые являются половинами массива arrayCopy 
    void printArray(); // Вывод массива на екран
    void printArrayCopy(); // Вывод копии массива на екран
    void writeToFile(); // Запись массива в файл
    void qSortI(); // Сортировка Хоара
    void readFromFile(); // Чтение с файла
    void arrayCopys(); // Создаем копии массива array
    void sorting(); // Многопоточная сортировка
    void margeArrays(); // Слияние двух массивов array2 и array3 в массив result
    void quickSortR(T* a, long N); // Рекурсивная сортировка Хоара для многопоточности
 
private:
    T *array; // Начальный массив
    T *arrayCopy; // Копия массива
    T *array2; // Первая половина массива arrayCopy
    T *array3; // Вторая половина массива arrayCopy
    T *result; // Массив, в который будет записано 
                //результат слияния двух массивов array2 и array3 
    INT64 arraySize; // Размер массива
    INT64 arraySize2; // Размер массивов array2 и array3 
 
};
 
 
template <class T>
ArraySorting<T>::ArraySorting()
{
    array = new T[0];
    arrayCopy = new T[0];
    array2 = new T[0];
    array3 = new T[0];
}
 
template <class T>
ArraySorting<T>::~ArraySorting()
{
    delete[] array;
    //delete[] arrayCopy;
}
 
 
 
// Задание размера массива
template <class T>
void ArraySorting<T>::setArraySize(T size)
{
    arraySize = size;
    arraySize2 = arraySize / 2;
}
 
// Инициализация массива
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;
    }
}
 
// Разделение массива arrayCopy на два подмассива array2 и array3
template <class T>
void ArraySorting<T>::initializationTwoArrays()
{
    array2 = new T[arraySize2];
    array3 = new T[arraySize2];
 
    for (int counter = 0; counter < arraySize2; counter++)
    {
        array2[counter] = arrayCopy[counter];
    }
 
    for (int counter = 0, i = arraySize2; i < arraySize; counter++)
    {
        array3[counter++] = arrayCopy[i++];
    }
}
 
 
// Вывод массива на екран
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 << result[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';
 
}
 
// Создаем массив arrayCopy, который будет 
// использоваться в многопоточной сортировке
template <class T>
void ArraySorting<T>::arrayCopys()
{
    arrayCopy = new T[arraySize];
    for (int counter = 0; counter < arraySize; counter++)
    {
        arrayCopy[counter] = array[counter];
    }
}
 
 
// Слияние двух массивов array2 и array3 в
// сортированный массив result
template <class T>
void ArraySorting<T>::margeArrays()
{
    result = new T[arraySize2 + arraySize2];
 
    int i = 0; // Индексы, которые указывают на первый 
    int j = 0; // необработанный элемент первого и второго массива
 
    int index = 0; // Индекс массива-результата, который указывает на 
                    // на позицию, которая будет заполнена нп текущем шаге
 
    // Повторяем сравнение элементов массивов array2 и array3 до тех пор
    // пока в каждом из них есть хотя бы один необработанный элемент
    while (i < arraySize2 && j < arraySize)
    {
        // В соответствии с тем, текущий элемент какого массива меньше,
        // записываем элемент в массив-результат и обновляем нужный индекс
        if (array2[i] < array3[j])
        {
            result[index] = array2[i];
            i++;
        }
        else
        {
            result[index] = array3[j];
            j++;
        }
        index++;
    }
 
    // Дописываем оставшиеся элементы одного из массива в массив результат
    while (i < arraySize2)
    {
        result[index] = array2[i];
        index++;
        i++;
    }
 
    while (j < arraySize2)
    {
        result[index] = array3[j];
        index++;
        j++;
    }
}
 
// Многопоточная сортировка
template <class T>
void ArraySorting<T>::sorting()
{
    
    //initializationTwoArrays();    
 
    thread first(&ArraySorting<T>::quickSortR, this, array2, arraySize2);
    thread second(&ArraySorting<T>::quickSortR, this, array3, arraySize2);
 
    first.join();
    second.join();
 
    margeArrays();
}
 
 
 
 
// Сортировка Хоара
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); // пока есть запросы в стеке
}
 
// Рекурсивня сортировка Хоара для многопоточности
template<class T>
void ArraySorting<T>::quickSortR(T* a, long N) {
    // На входе - массив a[], a[N] - его последний элемент. 
 
    long i = 0, j = N;   // поставить указатели на исходные  места
        T temp, p;
 
    p = a[N >> 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 > i) quickSortR(a + i, N - i);
}

#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();
    myArray.initializationTwoArrays();
    myArray.printArray();
 
    //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.sorting();
    long t6 = clock();
 
    cout << "\ntime paralel sorting: " << t6 - t5 << endl;
    
    myArray.printArrayCopy();
 
    system("PAUSE");
 
    return 0;
}