Page 1 of 1

issues with OpenMP Quicksort please help

Posted: Thu Jul 16, 2015 7:46 am
by seyli1234
hello,
i'm not an expert and i'm facing a problem that i could'nt resolve so plesae if any one know how to solve my problem help me please because it's urgent .
i need to "parallelize" all the code below because my Professor says that i should change this part

Code: Select all

int q = Partition(p, r, items);
to work in parallel. and i could't figure it out . [/b]
This is my code :

Code: Select all

template< typename T >
void ParallelQuickSort(int p, int r, T items, int low_limit) {
    if (p < r) {
        if ((r - p) < low_limit) {
            SeqQuickSort(p, r, items);
        } else {

            int q = Partition(p, r, items);
           
#pragma omp task firstprivate(items, low_limit, r, q)
{
          
         tasks_counter++;
            ParallelQuickSort(p, q - 1, items, low_limit);
}
#pragma omp task firstprivate(items, low_limit, r, q)
{
         tasks_counter++;
            ParallelQuickSort(q + 1, r, items, low_limit);
}
       
    }}
}
 
and here is the function Partition because maybe this function must be in parallel and not the call for it (sorry for the bad English and thank you :) ):

Code: Select all

template< typename T >
int Partition(int first, int last, T items) {

    //int pivot_index = (rand() % (last - first)) + first;
    //int pivot_index = (first + last) / 2;

    byte pivot_tweet[SIZEMETADATA];
    memcpy(pivot_tweet, getTweetMetaByIndex(items, first), SIZEMETADATA);

    int k = first;
    int l = last + 1;

    //while (1) {
    //items[k] <= pivot

    do {
        k++;
    } while (CompareTweetsQStandard(pivot_tweet, getTweetMetaByIndex(items, k)) == 1 && (k < last));

    //items[l] > x
    do {
        l--;
    } while (CompareTweetsQStandard(getTweetMetaByIndex(items, l), pivot_tweet) == 1);

    while (k < l) {
        swapTweets(items, k, l);

        //items[k] <= x
        do {
            k++;
        } while (CompareTweetsQStandard(pivot_tweet, getTweetMetaByIndex(items, k)) == 1);

        //items[l] > x
        do {
            l--;
        } while (CompareTweetsQStandard(getTweetMetaByIndex(items, l), pivot_tweet) == 1);
    }

    swapTweets(items, first, l);

    return l;
    
}