AlgorithmsAndDataStructures/PranavMerge.java at master · biprade/AlgorithmsAndDataStructures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
public class PranavMerge {
	int[] input1;
	int[] input2;
	int[] input3;

	PranavMerge(int[] input1, int[] input2, int[] input3) {
		this.input1 = input1;
		this.input2 = input2;
		this.input3 = input3;
		sort(input1);
		sort(input2);
		sort(input3);
	}
	void sort(int[] input)
	{
		InsertionSort is=new InsertionSort(input);
		is.sort();
	}
	int[] mergeSortedArrays()
	{
		// the output array
		int[] output =new int[input1.length+input2.length+input3.length];
		int i=0;
		int j=0;
		int k=0;
		int o=0;
		//Assuming all arrays have some elements and are not empty

		while(i<input1.length && j<input2.length && k<input3.length)
		{
			if(input1[i]<=input2[j] && input1[i]<=input3[k])
			{
				output[o++]=input1[i++];
			}
			else if(input2[j]<=input3[k])
			{
				output[o++]=input2[j++];
			}
			else
				output[o++]=input3[k++];
		}
		if(i==input1.length)
			mergeRest(input2,j,input3,k,output,o);
		else if(j==input2.length)
			mergeRest(input1,i,input3,k,output,o);
		else
			mergeRest(input1,i,input2,j,output,o);

//		while(i<=input1.length-1)
//		{
//			output[o++]=input1[i++];
//		}
//		while(j<=input2.length-1)
//		{
//			output[o++]=input2[j++];
//		}
//		while(k<=input3.length-1)
//		{
//			output[o++]=input3[k++];
//		}
		return output;
	}

	void mergeRest(int[] input1,int i,int[] input2,int j,int[] out,int o)
	{

		while(i<input1.length && j<input2.length)
		{
			if(input1[i]<=input2[j])
			{
				out[o++]=input1[i++];
			}
			else
				out[o++]=input2[j++];
		}
		while(i<input1.length)
		{
			out[o++]=input1[i++];
		}
		while(j<input2.length)
		{
			out[o++]=input2[j++];
		}
	}
	public static void main(String[] args)
	{
		int[] a={11,78,23,18};
		int[] b={5,7};
		int[] c={5,7};
		PranavMerge p= new PranavMerge(a,b,c);
		int[] out=p.mergeSortedArrays();
		for(int i=0;i<out.length;i++)
			System.out.println(out[i]);

	}

}