Cで書かれたクイックソートでのレース条件とOpenMPとの並列化

このクイックソルトの実装では、私が走っているプログラムが、私が理解できないレーシングコンディションになると思います。だから私はSOコミュニティに導いて指導します。Cで書かれたクイックソートでのレース条件とOpenMPとの並列化

quicksort（）のfor-loopの前に "#pragma omp parallel for private（i）"を削除すると正しくソートされます。

以下は、ソートのサンプルとコードです。

Unsorted 
3 6 7 5 3 5 6 2 9 1 

Sorted 
0 1 2 3 3 5 6 7 9 5 



    size_t average (size_t a, size_t b) 
    { 
      return (a + b)/2; 
    } 

    void swap (int *array, size_t x, size_t y) 
    { 
      int tmp; 
      tmp = array[x]; 
      array[x] = array[y]; 
      array[y] = tmp; 
    } 

    void quicksort (int *array, int left, int right) 
    { 
      int i, last; 

      if (left >= right) 
      { 
        return; 
      } 

      swap (array, left, average(left, right)); 
      last = left; 

      #pragma omp parallel for private(i) 
      for (i = left + 1; i <= right; i++) 
      { 
        if (array[i] < array[left]) 
        { 
          #pragma omp critical 
          { 
            last++; 
          } 
          swap(array, last, i); 
        } 
      } 

      swap (array, left, last); 

      #pragma omp parallel sections 
      { 
        #pragma omp section 
        { 
          quicksort(array,left,last-1); 
        } 

        #pragma omp section 
        { 
          quicksort (array, last+1, right); 
        } 
      } 
    }

出典

2012-02-15 Igor Eklund