Сортировка массива в openmp

Question

У меня есть массив из 100 элементов, который нужно отсортировать с помощью сортировки вставкой с использованием OpenMP.Когда я распараллеливаю свой род, он не дает правильных значений.Может ли кто-нибудь помочь мне

void insertionSort(int a[])
{
    int i, j, k;
    #pragma omp parallel for private(i)
    for(i = 0; i < 100; i++)
    {
            k = a[i];
            for (j = i; j > 0 && a[j-1] > k; j--)
                    #pragma omp critical
                    a[j] = a[j-1];
                    a[j] = k;
    }
}

Answer 1

Если это не домашнее задание, сортировка всего по 100 параллельных элементов не имеет смысла: накладные расходы, вызванные параллелизмом, значительно перевесят любое преимущество в производительности.

И, алгоритм сортировки вставок по своей сути последовательный. Когда обрабатывается [i], предполагается, что все предыдущие элементы в массиве уже отсортированы. Но если два элемента обрабатываются параллельно, такой гарантии, очевидно, нет.

Более подробное объяснение того, почему сортировка вставкой не может быть распараллелена предложенным способом дано @dreamcrash в своем ответе на подобный вопрос .

Answer 2

Переменные "j" и "k" должны быть приватными в параллельной области.В противном случае у вас есть условие гонки данных.