Hi There,
Please find the source code for implementing Quick Sort using the Threads in Java. The below program will create a new thread for sort each partition.
import java.util.Scanner;
import java.util.Random;
class QuickSort {
int beg, end;
int[] numbers = null;
public QuickSort(int beg, int end, int[] numbers) {
this.beg = beg;
this.end = end;
this.numbers = numbers;
}
void sortNumbers() {
if(beg < end) {
int p = partiton(beg, end);
Thread t1 = new Thread(new MyThread(beg, p-1, numbers));
Thread t2 = new Thread(new MyThread(p+1, end, numbers));
t1.start();
t2.start();
try {
t1.join();
t2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
int partiton(int beg, int end) {
int piv = numbers[end];
int i = beg - 1;
for(int j=beg;j<=end-1;j++) {
if(numbers[j] < piv) {
i++;
int t = numbers[i];
numbers[i] = numbers[j];
numbers[j] = t;
}
}
int t = numbers[i+1];
numbers[i+1] = numbers[end];
numbers[end] = t;
return i+1;
}
}
class MyThread implements Runnable {
int beg, end;
int[] numbers;
public MyThread(int beg, int end, int[] numbers) {
this.beg = beg;
this.end = end;
this.numbers = numbers;
}
@Override
public void run() {
QuickSort q = new QuickSort(beg, end, numbers);
q.sortNumbers();
}
}
class NormalQuickSort{
int[] numbers = null;
public NormalQuickSort(int[] numbers) {
this.numbers = numbers;
}
void sortNumbers(int beg, int end) {
if(beg < end) {
int p = partiton(beg, end);
sortNumbers(beg, p-1);
sortNumbers(p+1, end);
}
}
int partiton(int beg, int end) {
int piv = numbers[end];
int i = beg - 1;
for(int j=beg;j<=end-1;j++) {
if(numbers[j] < piv) {
i++;
int t = numbers[i];
numbers[i] = numbers[j];
numbers[j] = t;
}
}
int t = numbers[i+1];
numbers[i+1] = numbers[end];
numbers[end] = t;
return i+1;
}
}
public class QuickSortThread {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Number of items: ");
int n = sc.nextInt();
int[] numbers = new int[n];
int[] nums = new int[n];
System.out.println("Generating "+n+" numbers: ");
for(int i=0;i<n;i++) {
// numbers[i] = sc.nextInt();
// nums[i] = numbers[i];
numbers[i] = new Random().nextInt(100000);
nums[i] = numbers[i];
}
long start = System.nanoTime();
Thread tt = new Thread(new MyThread(0, n-1, numbers));
tt.start();
try {
tt.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
long end = System.nanoTime();
System.out.println("Thread took: "+(end-start)+" nano seconds");
for(int i=0;i<n;i++) {
System.out.print(numbers[i] + " ");
}
System.out.println();
NormalQuickSort nq = new NormalQuickSort(nums);
start = System.nanoTime();
nq.sortNumbers(0, n-1);
end = System.nanoTime();
System.out.println("Normal took: "+(end-start)+" nano seconds");
for(int i=0;i<n;i++) {
System.out.print(nums[i] + " ");
}
System.out.println();
}
}