Parallizing quicksort using multithreading in Java

Question

I was experimenting a bit with multi-threading in Java.I tried using multi-threading in quick-sort.I am trying to parallelize the two arrays made after partitioning around the pivot. But when i run the code,nothing happens.It just runs for infinite period.Can someone help?(I am a beginner in **multi-threading(().

import java.util.Arrays;
import java.util.Random;


public class QuickSort {


public synchronized static int pivot(int[] a, int lo, int hi){
    int mid = (lo+hi)/2;
    int pivot = a[lo] + a[hi] + a[mid] - Math.min(Math.min(a[lo], a[hi]), a[mid]) - Math.max(Math.max(a[lo], a[hi]), a[mid]);

    if(pivot == a[lo])
        return lo;
    else if(pivot == a[hi])
        return hi;
    return mid;
}

public synchronized static int partition(int[] a, int lo, int hi){

    int k = pivot(a, lo, hi);
    //System.out.println(k);
    swap(a, lo, k);
    //System.out.println(a);
    int j = hi + 1;
    int i = lo;
    while(true){

        while(a[lo] < a[--j])
            if(j==lo)   break;

        while(a[++i] < a[lo])
            if(i==hi) break;

        if(i >= j)  break;
        swap(a, i, j);
    }
    swap(a, lo, j);
    return j;
}

public synchronized static void sort(int[] a, int lo, int hi){
    if(hi<=lo)  return;
    int p = partition(a, lo, hi);
    Thread t1=new Thread(new Runnable(){

        @Override
        public void run() {

            sort(a, lo, p-1);
        }

    });
    Thread t2=new Thread(new Runnable(){
        public void run()
        {
            sort(a, p+1, hi);
        }
    });
    t1.start();
    t2.start();
    try {
        t1.join();
        t2.join();
    } catch (InterruptedException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }

}

public synchronized static  void swap(int[] a, int b, int c){
    int swap = a[b];
    a[b] = a[c];
    a[c] = swap;
}

public synchronized static void sort(int[] a){
    sort(a, 0, a.length - 1);
    System.out.print(Arrays.toString(a));
}

public static void main(String[] args) {
    int arr[] = new int[1001];
    Random rand=new Random();
    for(int i=0;i<1000;i++)
    {
        arr[i]=rand.nextInt(350);

    }
    float start=System.currentTimeMillis();
    sort(arr);
    float end=System.currentTimeMillis();
    System.out.println("Time take to sort");
    System.out.println(end-start);
 }
}

STaefi · Accepted Answer · 2016-01-25 13:38:36Z

1

I think the problem is:

When you mark a method as synchronized, you put a hidden lock on the whole method block.

So when you call the sort method recursively, it waits for the lock (which has been created for the first call of the sort method) of previous call to be released.

But that lock won't be released until the execution of the first call is ended. On the other hand, the execution of the first call of sort is depend on the second and third and ... calls of sort method.

So you are in a deadlock situation. That is the reason of your infinite situation.

Hope this would be helpful.

answered Jan 25, 2016 at 13:38

STaefi

4,4071 gold badge31 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Parallizing quicksort using multithreading in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related