Параллелизм на внутреннем выбранном цикле сортировки пропускает несколько чисел

Question

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

    int* selectionSort(int arr[], int size, int numberOfThreads)
{
    int i, j;
    int me, n, min_idx;
    bool canSwap = false;

#pragma omp parallel num_threads(numberOfThreads) private(i,j,me,n)
    {
        me = omp_get_thread_num();
        n = omp_get_num_threads();

        printf("Hello from %d/%d\n", me, n);


        for (i = 0; i < size - 1; i++) {
            min_idx = i;
            canSwap = true;
#pragma omp barrier

#pragma omp for
            for (j = i + 1; j < size; j++) {
                if (arr[j] < arr[min_idx])
                    min_idx = j;
                //printf("I am %d processing %d,%d\n", me, i, j);

            }

            printf("Min value %d ---- %d \n", arr[min_idx], min_idx);

#pragma omp critical(swap)
            if(canSwap)
            {
                swap(&arr[min_idx], &arr[i]);
                canSwap = false;
            }

#pragma omp barrier

        }
    }

    return arr;
}

Answer 1

Я обнаружил, что проблема в том, что вы не можете по-настоящему распараллелить этот алгоритм (по крайней мере, так, как я это делаю), поскольку я сравниваю arr[j] с arr[min_idx], min_idxзначение может иногда изменяться в такое конкретное время, когда другой поток завершит строку if (arr[j] < arr[min_idx]), и сразу после этого другой поток изменит значение min_idx, что иногда делает просто выполненный оператор if уже не true.