Question

Implement Quicksort in Java by sorting in parallel after partitioning; for this, the parent thread can continue sorting one segment and a child thread is created for sorting the other segment. However, create a new thread only if both segments contain more than S elements, otherwise sort sequentially both segments.

%%writefile Quicksort.java
import java.util.Random;

YOUR CODE HERE

public class Quicksort {

    static int N;   // number of elements to be sorted
    static int S;   // threshold for creating a sub-thread
    static int a[]; // array to be sorted

    static int partition(int p, int r) {
        int x = a[r];
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (a[j] <= x) {
                i++; 
                int t = a[i]; a[i] = a[j]; a[j] = t;
            }
        }
        int t = a[i + 1]; a[i + 1] = a[r]; a[r] = t;
        return i + 1;
    }

    static void sequentialsort(int p, int r) {
        if (p < r) {
            int q = partition(p, r);
            sequentialsort(p, q - 1);
            sequentialsort(q + 1, r);
        }
    }

YOUR CODE HERE

    public static void main(String args[]) {
        N = Integer.parseInt(args[0]);
        S = Integer.parseInt(args[1]);
        a = new int[N + 1];
        Random random = new Random();
        for (int i = 0; i < N; i++) a[i] = random.nextInt(10000);
        final long start = System.currentTimeMillis();

        parallelsort(0, N - 1);

        final long end = System.currentTimeMillis();
        for (int i = 1; i < N; i++) assert a[i - 1] <= a[i];
        System.out.println((end - start) + " ms");
    }
}

Above code only defines sequential sorting. Copy it and add parallel sorting; your solution must be derived from above template by adding code at the two marked locations.

Use the commands below to test your implementation.

!javac Quicksort.java
!java -enableassertions Quicksort 100000 10

Answer 1

import java.io.*;

import java.util.Random;

import java.util.concurrent.ForkJoinPool;

import java.util.concurrent.RecursiveTask;

public class QuickSortMutliThreading

    extends RecursiveTask<Integer> {

    int start, end;

    int[] arr;

    /**

     * Finding random pivoted and partition

     * array on a pivot.

     * There are many different

     * partitioning algorithms.

     * @param start

     * @param end

     * @param arr

     * @return

     */

    private int partion(int start, int end,

                        int[] arr)

    {

        int i = start, j = end;

        // Decide random pivot

        int pivote = new Random()

                         .nextInt(j - i)

                     + i;

        // Swap the pivote with end

        // element of array;

        int t = arr[j];

        arr[j] = arr[pivote];

        arr[pivote] = t;

        j--;

        // Start partioning

        while (i <= j) {

            if (arr[i] <= arr[end]) {

                i++;

                continue;

            }

            if (arr[j] >= arr[end]) {

                j--;

                continue;

            }

            t = arr[j];

            arr[j] = arr[i];

            arr[i] = t;

            j--;

            i++;

        }

        // Swap pivote to its

        // correct position

        t = arr[j + 1];

        arr[j + 1] = arr[end];

        arr[end] = t;

        return j + 1;

    }

    // Function to implement

    // QuickSort method

    public QuickSortMutliThreading(int start,

                                   int end,

                                   int[] arr)

    {

        this.arr = arr;

        this.start = start;

        this.end = end;

    }

    @Override

    protected Integer compute()

    {

        // Base case

        if (start >= end)

            return null;

        // Find partion

        int p = partion(start, end, arr);

        // Divide array

        QuickSortMutliThreading left

            = new QuickSortMutliThreading(start,

                                          p - 1,

                                          arr);

        QuickSortMutliThreading right

            = new QuickSortMutliThreading(p + 1,

                                          end,

                                          arr);

        // Left subproblem as separate thread

        left.fork();

        right.compute();

        // Wait untill left thread complete

        left.join();

        // We don't want anything as return

        return null;

    }

    // Driver Code

    public static void main(String args[])

    {

        int n = 7;

        int[] arr = { 54, 64, 95, 82, 12, 32, 63 };

        // Forkjoin ThreadPool to keep

        // thread creation as per resources

        ForkJoinPool pool

            = ForkJoinPool.commonPool();

        // Start the first thread in fork

        // join pool for range 0, n-1

        pool.invoke(

            new QuickSortMutliThreading(

                0, n - 1, arr));

        // Print shorted elements

        for (int i = 0; i < n; i++)

            System.out.print(arr[i] + " ");

    }

}