Tuesday, 21 December 2021

Ajith KP

Quick Sort in Java Threads

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