Параллельная сортировка Шелла

@никмейн · Регистрация: 24.10.2016

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

Здравствуйте!!! Помогите с заданием: Нужно распараллелить сортировку Шелла, но у меня что-то не выходит(((

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
#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <Windows.h>
#include <iostream>
 
//сортировка методом Шелла
void ShellSort(int n, int mass[])
{
    int i, j, step;
    int tmp;
    for (step = n / 2; step > 0; step /= 2)
        for (i = step; i < n; i++)
        {
            tmp = mass[i];
            for (j = i; j >= step; j -= step)
            {
                if (tmp < mass[j - step])
                    mass[j] = mass[j - step];
                else
                    break;
            }
            mass[j] = tmp;
        }
}
 
int main()
{
    //ввод N
    int N;
    printf("Input N: ");
    scanf_s("%d", &N);
    //выделение памяти под массив
    int* mass;
    mass = (int *)malloc(N * sizeof(int));
    //ввод элементов массива
    printf("Input the array elements:\n");
    for (int i = 0; i < N; i++)
        scanf_s("%d", &mass[i]);
    //сортировка методом Шелла
    ShellSort(N, mass);
    //вывод отсортированного массива на экран
    printf("Sorted array:\n");
    for (int i = 0; i < N; i++)
        printf("%d ", mass[i]);
    printf("\n");
    //освобождение памяти
    free(mass);
    _getch();
    return 0;
}

@никмейн · 17.06.2018, 13:55 **[ТС]**

Как объединить эти два кода

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
// Function for parallel Shell sorting
void ParallelShellSort(double* pData, int Size) {
 InitializeParallelSections();
 int* Index = new int [2*ThreadNum];
 int* BlockSize = new int [2*ThreadNum];
 int * BlockPairs = new int [2*ThreadNum];
 for (int i=0; i<2*ThreadNum; i++) {
 Index[i] = int((i*Size)/double(2*ThreadNum));
 if (i<2*ThreadNum-1)
 BlockSize[i] = int (((i+1)*Size)/double(2*ThreadNum)) - Index[i];
 else
 BlockSize[i] = Size-Index[i];
 }
 // Local sorting of data blocks (reverse cycle scheme)
#pragma omp parallel
 {
 int BlockID = ReverseGrayCode(ThreadNum+ThreadID, DimSize);
 QuickSorter(pData, Index[BlockID], Index[BlockID]+BlockSize[BlockID]-1);
 BlockID = ReverseGrayCode(ThreadID, DimSize);
 QuickSorter(pData, Index[BlockID], Index[BlockID]+BlockSize[BlockID]-1);
 }
 // Iterations of the Shell method
 for (int Iter=0; (Iter<DimSize) && (!IsSorted(pData, Size)); Iter++) {
 // Block pairs determination
 SetBlockPairs(BlockPairs, Iter);
 // ”Compare-split” operation for data blocks
#pragma omp parallel
 {
 int MyPairNum = FindMyPair(BlockPairs, ThreadID, Iter);
 int FirstBlock = ReverseGrayCode(BlockPairs[2*MyPairNum], DimSize);
 int SecondBlock = ReverseGrayCode(BlockPairs[2*MyPairNum+1], DimSize); 
CompareSplitBlocks(pData, Index[FirstBlock], BlockSize[FirstBlock],
 Index[SecondBlock], BlockSize[SecondBlock]);
 } // pragma omp parallel
 } // for
 // Odd-even blocks’ transposition
 int Iter = 1;
 while (!IsSorted(pData, Size)) {
#pragma omp parallel
 {
 if (Iter%2 == 0) // Even iteration
 MergeBlocks(pData, Index[2*ThreadID], BlockSize[2*ThreadID],
 Index[2*ThreadID+1], BlockSize[2*ThreadID+1]);
 else // Odd iteration
 if (ThreadID<ThreadNum-1)
 MergeBlocks(pData, Index[2*ThreadID+1], BlockSize[2*ThreadID+1],
 Index[2*ThreadID+2], BlockSize[2*ThreadID+2]);
 } // pragma omp parallel
 Iter++; 
22
 } // while
 delete [] Index;
 delete [] BlockSize;
 delete [] BlockPairs;
}

@никмейн · 11.07.2018, 17:47 **[ТС]**

Как это сделать?

@lArtl · 11.07.2018, 19:06

......

@lArtl · 11.07.2018, 19:12

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
#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <Windows.h>
#include <iostream>
 
void ParallelShellSort(double* pData, int Size) {
 InitializeParallelSections();
 int* Index = new int [2*ThreadNum];
 int* BlockSize = new int [2*ThreadNum];
 int * BlockPairs = new int [2*ThreadNum];
 for (int i=0; i<2*ThreadNum; i++) {
 Index[i] = int((i*Size)/double(2*ThreadNum));
 if (i<2*ThreadNum-1)
 BlockSize[i] = int (((i+1)*Size)/double(2*ThreadNum)) - Index[i];
 else
 BlockSize[i] = Size-Index[i];
 }
 // Local sorting of data blocks (reverse cycle scheme)
#pragma omp parallel
 {
 int BlockID = ReverseGrayCode(ThreadNum+ThreadID, DimSize);
 QuickSorter(pData, Index[BlockID], Index[BlockID]+BlockSize[BlockID]-1);
 BlockID = ReverseGrayCode(ThreadID, DimSize);
 QuickSorter(pData, Index[BlockID], Index[BlockID]+BlockSize[BlockID]-1);
 }
 // Iterations of the Shell method
 for (int Iter=0; (Iter<DimSize) && (!IsSorted(pData, Size)); Iter++) {
 // Block pairs determination
 SetBlockPairs(BlockPairs, Iter);
 // ”Compare-split” operation for data blocks
#pragma omp parallel
 {
 int MyPairNum = FindMyPair(BlockPairs, ThreadID, Iter);
 int FirstBlock = ReverseGrayCode(BlockPairs[2*MyPairNum], DimSize);
 int SecondBlock = ReverseGrayCode(BlockPairs[2*MyPairNum+1], DimSize); 
CompareSplitBlocks(pData, Index[FirstBlock], BlockSize[FirstBlock],
 Index[SecondBlock], BlockSize[SecondBlock]);
 } // pragma omp parallel
 } // for
 // Odd-even blocks’ transposition
 int Iter = 1;
 while (!IsSorted(pData, Size)) {
#pragma omp parallel
 {
 if (Iter%2 == 0) // Even iteration
 MergeBlocks(pData, Index[2*ThreadID], BlockSize[2*ThreadID],
 Index[2*ThreadID+1], BlockSize[2*ThreadID+1]);
 else // Odd iteration
 if (ThreadID<ThreadNum-1)
 MergeBlocks(pData, Index[2*ThreadID+1], BlockSize[2*ThreadID+1],
 Index[2*ThreadID+2], BlockSize[2*ThreadID+2]);
 } // pragma omp parallel
 Iter++; 
22
 } // while
 delete [] Index;
 delete [] BlockSize;
 delete [] BlockPairs;
}
 
int main()
{
    //ввод N
    int N;
    printf("Input N: ");
    scanf_s("%d", &N);
    //выделение памяти под массив
    double* mass;
    mass = (double*)malloc(N * sizeof(double));
    //ввод элементов массива
    printf("Input the array elements:\n");
    for (int i = 0; i < N; i++)
        scanf_s("%lf", &mass[i]);
    //сортировка методом Шелла
    ParallelShellSort(mass, N);
    //вывод отсортированного массива на экран
    printf("Sorted array:\n");
    for (int i = 0; i < N; i++)
        printf("%lf ", mass[i]);
    printf("\n");
    //освобождение памяти
    free(mass);
    _getch();
    return 0;
}

Но это не точно...
PS: если у вас VS, то в свойствах проекта в разделе С/C++ ->Язык включить поддержку OpenMP

@никмейн · 26.09.2018, 23:56 **[ТС]**

Извините, что много времени прошло с момента последней переписки, но сделал сортировку Шелла, но препод мне сказал, что он у меня работает коряво, неправильно введет сортировку, еще сказал синхронизацию critical надо

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
#include "stdafx.h" 
#include <iostream> 
#include <Windows.h> 
#include <conio.h> 
#include <omp.h> 
#include <time.h> 
#include <ctime>
using namespace std;
int main()
{
    setlocale(LC_ALL, "rus");
    int m, y = 0;
    const int n = 5;
    int a[n];
    srand(time(NULL));
    cout << "\nИсходный массив: ";
    for (int i = 0; i < n; i++)
    {
        a[i] = rand()%n;
    }
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << "\n";
    cout << endl;
    cout << "Этапы сортировки массива: \n";
    cout << "\n";
    //алгоритм сортировки Шелла
#pragma omp parallel firstprivate(n)
    {
        m = omp_get_thread_num();
        int step = n / 2;//инициализируем шаг. 
        while (step > 0)//пока шаг не 0 
        {
#pragma omp for 
            for (int i = 0; i < (n - step); i++)
            {
                int j = i;
                //будем идти начиная с i-го элемента 
                while (j >= 0 && a[j] > a[j + step])
                    //пока не пришли к началу массива 
                    //и пока рассматриваемый элемент больше 
                    //чем элемент находящийся на расстоянии шага 
                {
                    //меняем их местами 
                    int temp = a[j];
                    a[j] = a[j + step];
                    a[j + step] = temp;
                    cout << "Поток " << m << " меняет местами элементы с номерами " << j << " и " << j + step << "\n";
                    j--;
                }
            }
            step = step / 2;//уменьшаем шаг 
        }
    }
    cout << "\nОтсортированный массив: ";
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << "\n";
    system("pause");
    return 0;
}

можете сказать, что не так?

@никмейн · 07.10.2018, 23:00 **[ТС]**

помогите пожалуйста

@никмейн · 17.10.2018, 20:54 **[ТС]**

есть спецы в технологии open mp?

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@никмейн 65 / 46 / 20 Регистрация: 24.10.2016 Сообщений: 1,053
	11.07.2018, 17:47 [ТС]
	Как это сделать? 0

@lArtl 322 / 174 / 78 Регистрация: 09.10.2014 Сообщений: 809
	11.07.2018, 19:06
	...... Миниатюры 0

@никмейн 65 / 46 / 20 Регистрация: 24.10.2016 Сообщений: 1,053
	07.10.2018, 23:00 [ТС]
	помогите пожалуйста 0

@никмейн 65 / 46 / 20 Регистрация: 24.10.2016 Сообщений: 1,053
	17.10.2018, 20:54 [ТС]
	есть спецы в технологии open mp? 0