CODEWITHSUNDEEP
c#algorithmsortingparallel-processing
user1799092
user1799092

Reputation: 163

parallel bidirectional selection sort

I wrote code to implement a bidirectional selection sort in parallel. I used c#, and the the parallel.invoke function. 2 loops were invoked in parallel, one to find the minimum, and one to find the max. Yet, it doesn't sort. I was wondering is the problem because this type of sort can't handle being done in parallel, since each loop relies on data existing in the other loop?...or is there simply something wrong with my code?

Parallel.Invoke(
            () => 
                {                        
                    for (int i=0; i < array.Length / 2; i++)
                    {
                        int m;
                        int min = i;
                        for (m = i + 1; m < array.Length - 1; m++)
                            if (array[m] < array[min])
                                min = m;
                        //swap
                        int temp = array[min];
                        array[min] = array[m];
                        array[m] = temp;
                    }
                },
                () => 
                    {
                        for (int m = 0; m < array.Length / 2; m++)
                        {
                            int length = array.Length - 1;
                            int max = length - m;
                            int k;
                            for (k = length--; k > 0; k--)
                                if (array[k] > array[max])
                                    max = k;
                            //swap
                            int temp = array[max];
                            array[max] = array[k];
                            array[k] = temp;
                        }
                });

Upvotes: 1

Views: 1868

Answers (1)

ultddave
ultddave

Reputation: 198

I think it's easier if you search the minimum and maximum within the same loop in 1 thread: (java-code, but I assume you'll understand the principle)

    int minimum, maximum;
    int k = size();
    for(int i = 0; i < size(); ++i)
    {
        --k;
        minimum = i;
        maximum = k;
        if(k - i <= 0)
            break;
        for(int j = i; j <= k; ++j)
        {
            if(greaterThan(minimum, j))
                minimum = j;
            if(lessThan(maximum, j))
                maximum = j;
        }

        if(minimum != i)
        {
            swap(minimum, i);
            if(maximum == i)
                maximum = minimum;
        }
        if(maximum != k)
            swap(maximum, k);
    }

The problem with your code is this:

Say this is the array:

[5, 4, 3, 2, 1]

Iteration 0: The first thread will find the smallest element to put on index 0
The first thread finds the minimum element at index 4
Iteration 0: The second thread will find the largest element to put on index 4
The second thread finds the maximum element at index 0

You will already see that this will not end well, as both threads will perform a swap between index 0 and 4 resulting in the same situation as it is now.

Another problem is if your first thread is looping from m -> array.length - 1. If at the same time thread 2 moves the minimum element (which it doesn't need, because it's searching the maximum) from index k to "max" via a swap. With index "max" being < "m". That means the first thread will never find the next minimum value because it was moved before its position.

EDIT: After consideration, I don't think it's possible to implement a straightforward parallel version of selection sort. The version I first recommended was indeed not going to work due to the algorithm finding the same minimum every time because it didn't change the input-array.

What is possible is to only perform selection sort with thread 1 on the first half of the array (and only allow it to find the minimum in that half) and the second half of the array is for the second thread. And then in the end you can merge both halfs with a mergesort-algorithm.

This way you can always use more than 2 threads; say "p" amount of threads for example. Each responsible for N/p part of the input array with "N" being the inputsize. And in the end you just merge every part with a mergesort-algorithm. I never implemented it myself, so I can't say if it would be efficient, but I assume there will be better algorithms to parallelize out there (like mergesort itself).

PS: About the code posted above. I assume everything seems rather straightforward except this part:

            if(maximum == i)
                maximum = minimum;

That's to deal with a situation like this:
. . . i . . . k
[1, 4, 3, 1, 5]

so with i = 1 and k = 3 (the indices).

The algorithm will find:
maximum = index 1
minimum = index 3

After swapping the minimum value with the one on index i, the situation changes like this:
. . . i . . . k
[1, 1, 3, 4, 5]

Meaning the maximum value (integer 4) actually moved from index "i" to index "minimum". If we would perform a swap(maximum, k), it would have a bad result. That's why we need to update the index of the maximum element if it was positioned at index i.

Upvotes: 2

Related Questions