Параллельная сортировка слиянием на C++ Отсортируйте данный массив, используя параллельную сортировку слиянием

Пчелка

64

Для решения данной задачи параллельной сортировки слиянием на C++, вам потребуется выполнить следующие шаги:

1. Создайте функцию merge, которая объединяет два отсортированных подмассива в один отсортированный массив. Входными параметрами функции будут указатели на начало каждого подмассива, размеры подмассивов и указатель на начало результирующего массива.

2. Внутри функции merge создайте временный массив, размер которого будет равен суммарному размеру двух подмассивов. Затем выполните следующие действия:
- Инициализируйте два индекса: один для первого подмассива, другой для второго.
- Сравните элементы на текущих позициях в обоих подмассивах.
- Скопируйте меньший элемент во временный массив.
- Увеличьте соответствующий индекс в подмассиве, из которого был взят элемент.

3. После цикла объединения элементов обоих подмассивов в один временный массив, скопируйте оставшиеся элементы из первого и второго подмассивов, если таковые остались.

4. Замените значения в результирующем массиве временного массива.

5. Реализуйте рекурсивную функцию mergeSort, которая будет разделять исходный массив на две половины, вызывать себя для каждой половины и затем вызывать функцию merge, чтобы объединить отсортированные подмассивы.

6. Внутри функции mergeSort проверьте базовый случай: если размер массива равен 1, верните.

7. Разделите исходный массив на две половины и вызовите функцию mergeSort для каждой половины.

8. Вызовите функцию merge, чтобы объединить отсортированные половины массива.

9. Создайте массив с размером N и заполните его входными значениями.

10. Вызовите функцию mergeSort, передав начальный и конечный индексы массива, чтобы выполнить сортировку.

11. Наконец, выведите отсортированный массив на экран.

Вот пример реализации данного алгоритма на C++:

cpp

#include 



void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {

    int i = 0, j = 0, k = 0;



    while (i < leftSize && j < rightSize) {

        if (left[i] <= right[j]) {

            arr[k] = left[i];

            i++;

        } else {

            arr[k] = right[j];

            j++;

        }

        k++;

    }



    while (i < leftSize) {

        arr[k] = left[i];

        i++;

        k++;

    }



    while (j < rightSize) {

        arr[k] = right[j];

        j++;

        k++;

    }

}



void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        int mid = (left + right) / 2;



        mergeSort(arr, left, mid);

        mergeSort(arr, mid + 1, right);



        int leftSize = mid - left + 1;

        int rightSize = right - mid;



        int leftArr[leftSize];

        int rightArr[rightSize];



        for (int i = 0; i < leftSize; i++) {

            leftArr[i] = arr[left + i];

        }



        for (int i = 0; i < rightSize; i++) {

            rightArr[i] = arr[mid + 1 + i];

        }



        merge(arr, leftArr, leftSize, rightArr, rightSize);

    }

}



int main() {

    int N;

    std::cin >> N;



    int arr[N];



    for (int i = 0; i < N; i++) {

        std::cin >> arr[i];

    }



    mergeSort(arr, 0, N - 1);



    for (int i = 0; i < N; i++) {

        std::cout << arr[i] << " ";

    }



    return 0;

}

При запуске программы пользователь будет предоставлен ввод для N (количество элементов в массиве) и сами элементы. Затем программа отсортирует эти числа и выведет их в порядке неубывания.

Надеюсь, что данное пошаговое объяснение поможет вам реализовать параллельную сортировку слиянием на C++ без создания новых векторов при каждом рекурсивном вызове.