Answer to Question #237047 in Java | JSP | JSF for anto

Question

Write a program which takes as input a huge array of numbers. This array is

split into n sub-arrays and n threads apply a bubble sort on each of the n sub-

arrays. Lastly, another thread merges the n sorted sub-arrays into one with

the same size as the original array. Of course, the resulting array should be

sorted.

Answer 1

import java.lang.System;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;


class Sort{
	
	private static final int max = 4;
	
	private static class SortThreads extends Thread{
		SortThreads(Integer[] arr, int start, int stop){
			super(()->{
				Sort.sort(arr, start, stop);
			});
			this.start();
		}
	}
	
	public static void threadedSort(Integer[] arr){
		long time = System.currentTimeMillis();
		final int length = arr.length;
		boolean exact = length%max == 0;
		int maxlim = exact? length/max: length/(max-1);
		maxlim = maxlim < max? max : maxlim;
		final ArrayList<SortThreads> threads = new ArrayList<>();
		for(int i=0; i < length; i+=maxlim){
			int beg = i;
			int remain = (length)-i;
			int stop = remain < maxlim? i+(remain-1): i+(maxlim-1);
			final SortThreads t = new SortThreads(arr, beg, stop);
			threads.add(t);
		}
		for(Thread t: threads){
			try{
				t.join();
			} catch(InterruptedException ignored){}
		}
		
		for(int i=0; i < length; i+=maxlim){
			int mid = i == 0? 0 : i-1;
			int remain = (length)-i;
			int stop = remain < maxlim? i+(remain-1): i+(maxlim-1);
			merge(arr, 0, mid, stop);
		}
		time = System.currentTimeMillis() - time;
		System.out.println("Time spent : "+ time+ "ms");
	}


	
	public static void sort(Integer[] arr, int start, int stop){
		if (start<stop){
			int mid = (start+stop)/2;
			sort(arr, start, mid);
			sort(arr, mid+1, stop);
			merge(arr, start, mid, stop);
		}
	}


	public static void merge(Integer[] arr, int start, int mid, int stop){
		Integer[] temp = new Integer[(stop-start)+1];
		
		int i = start, j = mid+1;
		int k = 0;


		while(i<=mid && j<=stop){
			if (arr[i] <= arr[j]){
				temp[k] = arr[i];
				i+=1;
			}else{
				temp[k] = arr[j];
				j+=1;
			}
			k+=1;
		}


		while(i<=mid){
			temp[k] = arr[i];
			i+=1; k+=1;
		}
		while(j<=stop){
			temp[k] = arr[j];
			j+=1; k+=1;
		}


		for(i=start, k=0; i<=stop; i++,k++){
			arr[i] = temp[k];
		}
	}
}


public class Main{
	private static Random rand = new Random();
	private static final int size = rand.nextInt(100);
	private static final Integer list[] = new Integer[size];
	static {
	for(int i=0; i<size; i++){
		list[i] = rand.nextInt(size+(size-1))-(size-1);
	}
	}
	
	public static void main(String[] args){
	System.out.print("Input = [");
	for (Integer each: list)
		System.out.print(each+", ");
	System.out.print("] \n" +"Input.length = " + list.length + '\n');


	Integer[] arr1 = Arrays.copyOf(list, list.length);
	long t = System.currentTimeMillis();
	Arrays.sort(arr1, (a,b)->a>b? 1: a==b? 0: -1);
	t = System.currentTimeMillis() - t;
	System.out.println("Time spent: " + t + "ms");


	Integer[] arr2 = Arrays.copyOf(list, list.length);
	t = System.currentTimeMillis();
	Sort.sort(arr2, 0, arr2.length-1);
	t = System.currentTimeMillis() - t;
	System.out.println("Time spent: " + t + "ms");


	Integer[] arr = Arrays.copyOf(list, list.length);
	Sort.threadedSort(arr);
	System.out.print("Output = [");
	for (Integer each: arr)
		System.out.print(each+", ");
	System.out.print("]\n");
	}
}