Our Feeds

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