CODEWITHSUNDEEP
javamultithreadingquicksort
Prashant Pandey
Prashant Pandey

Reputation: 139

Parallizing quicksort using multithreading in Java

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);
 }
}

Upvotes: 0

Views: 169

Answers (1)

STaefi
STaefi

Reputation: 4377

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.

Upvotes: 1

Related Questions