Hi,
I am currently following a Java training.
We learnt the basics and one of the assignements was to combine 2 sorted arrays. The thing is we have no right to use anything that sorts the array (otherwise it is a few lines of code).
Thought Java is close to C# I did struggle with it.
Until I started over with C# and did it in 5mn.
The following code works, but Java has specifics I don’t know yet and I would like to know if as a more experienced Java developer, you could refactor this better?
Subsidiary question : Is there an equivalent to C# string interpolation in Java? Console.WriteLine($"Value of A: {a}. Value of B {b}.");
Closest Java I know System.out.printf("Value of A: %d. Value of B %d.", a, b);
Is there something closer?
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] numbers1 = { 1, 5, 51, 84, 92, 800, 850, 855, 1000 };
int[] numbers2 = { -1, 9, 741, 900, 901, 999 };
int[] finalTable = new int[numbers1.length + numbers2.length];
int i = 0, j = 0, k = 0;
boolean numbers1HasNext = i < numbers1.length;
boolean numbers2HasNext = j < numbers2.length;
// Sort them as long both tables have values left
while (numbers1HasNext && numbers2HasNext)
{
if (numbers1[i] < numbers2[j])
{
finalTable[k++] = numbers1[i++];
}
else
{
finalTable[k++] = numbers2[j++];
}
numbers1HasNext = i < numbers1.length;
numbers2HasNext = j < numbers2.length;
}
// Check if numbers1 has any value left. If so complete the process
if (numbers1HasNext)
{
while (numbers1HasNext)
{
finalTable[k++] = numbers1[i++];
numbers1HasNext = i < numbers1.length;
}
}
// Check if numbers2 has any value left. If so complete the process
if (numbers2HasNext)
{
while (numbers2HasNext)
{
finalTable[k++] = numbers2[j++];
numbers2HasNext = j < numbers2.length;
}
}
System.out.println("\n" + Arrays.toString(finalTable));
}
}
OK, so this is a subset of the MergeSort algorithm (the merge step).
You have the basic idea, but there are some simplifications we could do. For example, this is easier to reason about if you use a class to contain the state of the algorithm while processing (perhaps called “MergeProcessor” or simply “Merger”) where you can add helper methods.
class Merger {
private final int[] first;
private final int[] second;
private final int[] result;
private int firstIndex = 0;
private int secondIndex = 0;
Merger(int[] first, int[] second) {
this.first = first;
this.second = second;
this.result = new int[first.length + second.length];
}
int[] merge() {
while (!isComplete()) {
mergeNext();
}
return result;
}
private boolean isComplete() {
return resultIndex() == result.length;
}
private int resultIndex() {
return firstIndex + secondIndex;
}
private void mergeNext() {
if (!firstHasNext()) {
result[resultIndex()] = nextSecond();
secondIndex++;
return;
}
if (!secondHasNext() || nextFirst() <= nextSecond()) {
result[resultIndex()] = nextFirst();
firstIndex++;
return;
}
// If we get here, the next second was less than the next first
result[resultIndex()] = nextSecond();
secondIndex++;
}
private boolean firstHasNext() {
return firstIndex < first.length;
}
private int nextFirst() {
return first[firstIndex];
}
private boolean secondHasNext() {
return secondIndex < second.length;
}
private int nextSecond() {
return second[secondIndex];
}
}
That is how I would “refactor” the code. It is best to put things into methods that have names as often as you can. You can probably even do better than I just did with a little more effort.
The String.printf and I/O stream printf methods are the closest we have currently. I know it is not as nice as other languages, but that is the state of Java today.
I did not run it yet but went through it statically.
I was asked to do it in the form of a function but this is terrific how your code makes complete sense (except for a part I find a bit more difficult to digest but that’s just me too young dev).
I also did observe that the index in the result table is the addition of the indexes to source tables but I preferred to play safe.
This function has me a bit dizzy.
private void mergeNext() {
if (!firstHasNext()) {
result[resultIndex()] = nextSecond();
secondIndex++;
return;
}
if (!secondHasNext() || nextFirst() <= nextSecond()) {
result[resultIndex()] = nextFirst();
firstIndex++;
return;
}
// If we get here, the next second was less than the next first
result[resultIndex()] = nextSecond();
secondIndex++;
}
If you don’t have more values in first then you merge from second. Can’t we get in a situation where there is no more values in second? Actually if we get into that method, it means there is at least one more value to merge because of this:
while (!isComplete()) {
mergeNext();
}
Then you can get to the next if only if there are values in second so you avoid the problem I had on my previous approach of having null exceptions.
If there is nothing left in second or if the value in first is smaller, we push the value from the 1st table.
I have that strange feeling that I overall understand it yet I don’t… xD.
I’ll need to run it against a debugger and observe it several times but this is very ingenious.
I have further questions.
Why did you set the tables final ? What is its benefit ?
private void mergeNext() {
if (!firstHasNext()) {
mergeSecond();
return;
}
if (!secondHasNext() || nextFirst() <= nextSecond()) {
mergeFirst();
return;
}
// If we get here, the next second was less than the next first
mergeSecond();
}
private void mergeFirst() {
result[resultIndex()] = nextFirst();
firstIndex++;
}
private void mergeSecond() {
result[resultIndex()] = nextSecond();
secondIndex++;
}
The point is we can keep adding helpful named methods that allow us to do what we want. And you can still use a class and have a static method which uses that class to achieve the result. For example:
public static int[] merge(int[] first, int[] second) {
return new Merger(first, second).merge();
}
Basically, I generally follow the Google Java Style Guide (you can search for it if you want to) and declare any fields that can be final as final since it means they cannot be reassigned. I only leave them non-final if there is some need to reassign them (for example, the index variables need to be incremented). The benefit is that it is clear to someone reading the class that the field is never reassigned after the constructor.
