CODEWITHSUNDEEP
javamultithreadingquicksort
Rpant
Rpant

Reputation: 1054

multithreaded quick sort does not give answer as expected

I modified quick sort to make it multithread. I expected it to work , coz the original algorithm was working. After partitioning, for the recursive calls to left and right of pivot .. I am creating a new thread. 

public class QuickSort extends Thread{
    private int[] arr;
    private int left;
    private int right;
public QuickSort(int[] arr){

    this.arr= arr;
    this.left=0;
    this.right=arr.length -1;
    this.start();
}

public QuickSort(int[] arr, int left , int right){

    this.arr= arr;
    this.left=left;
    this.right=right;
    this.start();

}

    int partition( int left, int right)
    {
          int i = left, j = right;
          int tmp;
          int pivot = arr[(left + right) / 2];

          while (i <= j) {
                while (arr[i] < pivot)
                      i++;
                while (arr[j] > pivot)
                      j--;
                if (i <= j) {
                      tmp = arr[i];
                      arr[i] = arr[j];
                      arr[j] = tmp;
                      i++;
                      j--;
                }
          };

          return i;
    }

    void quickSort(int left, int right) {
          int index = partition(left, right);
          if (left < index - 1)
                new QuickSort(arr, left , index -1);
          if (index < right)
              new QuickSort(arr ,index, right);
    }

    public void run(){
        quickSort(left , right);
    }

    public static void main(String arg[])
    {
        int[] s = {100,99,98,97,96,95,94,93,92,91};
        new QuickSort(s);
        for(int i: s)
            System.out.println(i);
    }
}

Upvotes: 0

Views: 148

Answers (2)

user207421
user207421

Reputation: 311052

Your first problem is that you aren't waiting for any thread to exit, so you are printing the data while the threads are still running. You need some Thread.join() calls.

I'm not saying there aren't other problems ... Your sort fails if there are already sorted elements, e.g. if you add 89,90 to your test array.

Upvotes: 1

Michael Burr
Michael Burr

Reputation: 340516

For one thing, you're never waiting for any of the threads to finish. So by the time you go to print out the array who knows how much work has been done.

You'll need to somehow join() the threads you've spun up (or come up with some other mechanism to figure out they're done).

Upvotes: 1

Related Questions