Sunday, June 26, 2011

Multi-threaded Quicksort using Java




NOTE: There was a bug in the initial code. The insertion sort portion had for(int i = left; i < right; i++), but right is already an index, not a size, so we need to change < to <=.

 I'm in the process of learning parallel programming. The first thing I wanted to do to learn it is to actually use threading in Java. So I created a multi-threaded version of quicksort. I compared it to single-threaded quicksort. Running it with 10 million elements i got 1300 ms for multi-threaded, and 1991 ms for single-threaded running on a quad-core processor.

Notice that insertion sort is done if the size of the array is less than 20. Two reasons:
1. Insertion sort is better on small amounts of data compared to quick sort
2. This reduces the number of threads spawned.

Here's the code...


//Use it by creating the QuickSorter object and calling start().
    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i = 10000000; i > 0; i--)
            arr.add(i);
        ThreadGroup group = new ThreadGroup("QuickSorter");
        Thread t = new QuickSorter(arr, 0, arr.size() - 1, group);
        t.start();
        while(t.isAlive())
        {
        }
 }

public class QuickSorter extends Thread{
    private ArrayList<Integer> arr;
    int left;
    int right;
    public QuickSorter(ArrayList<Integer> arr, int left, int right, ThreadGroup g)
    {
        super(g, "QuickSorter");
        this.arr = arr;
        this.left = left;
        this.right = right;
       
    }
    public void run()
    {
        if(left >= right || left < 0 || right >= arr.size())
        {
            return;
        }
        if(right - left < 20)
        {
            for(int i = left; i <= right; i++)
            {
                int tmp = arr.get(i);
                int j = i;
                for(; j > 0 && tmp < arr.get(j - 1); j--)
                    arr.set(j, arr.get(j - 1));

                arr.set(j, tmp);//[j] = tmp;
            }
            return;
        }
        int pivotIdx = (right + left) / 2;
        int pivot = arr.get(pivotIdx);
        int i = left;
        int j = right;
       
        while(i < j)
        {
           while(arr.get(i) < pivot)
               i++;
          
           while(arr.get(j) > pivot)
               j--;
           if(i >= j)
               break;
           int tmp = arr.get(i);
           arr.set(i, arr.get(j));
           arr.set(j, tmp);
        }
        QuickSorter leftQS = new QuickSorter(arr, left, i - 1, this.getThreadGroup());
        leftQS.start();
        QuickSorter rightQS = new QuickSorter(arr, i + 1, right, this.getThreadGroup());
        rightQS.start();
       
    }

No comments:

Post a Comment

There was an error in this gadget