Модераторы: bsa
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Сортировка Шелла 
:(
    Опции темы
Кли
Дата 15.6.2018, 18:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 35
Регистрация: 20.11.2016

Репутация: нет
Всего: нет



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

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

PM MAIL   Вверх
Romikgy
Дата 15.6.2018, 19:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Любитель-программер
****


Профиль
Группа: Участник Клуба
Сообщений: 7325
Регистрация: 11.5.2005
Где: Porto Franco Odes sa

Репутация: 1
Всего: 146



вы знаете как создавать потоки? (если таким способом распараллеливание подразумевалось)
грубо каждый поток будет со свои шагом 
Код

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

одно как организовать блокировку что бы потоки друг с другом не ссорились...


--------------------
Владение русской орфографией это как владение кунг-фу — истинные мастера не применяют его без надобности. 
smile

PM   Вверх
Кли
Дата 17.6.2018, 13:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 35
Регистрация: 20.11.2016

Репутация: нет
Всего: нет



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

// 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;


PM MAIL   Вверх
Кли
Дата 16.10.2018, 13:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 35
Регистрация: 20.11.2016

Репутация: нет
Всего: нет



Посоветуйте пожалуйста , как быть? У меня как-то не так оно параллелится, что не так в этой проге?
Код

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


Это сообщение отредактировал(а) Кли - 16.10.2018, 13:22
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

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


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »


 




[ Время генерации скрипта: 0.1311 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.