Merge Sort

Merge Sort. Using extra space to copy partially sorted array.

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

public class Main { public static void main(String[] args) { if (args.length == 0) { System.out .println("Proper Usage is: java main number1 number2 number3 ..."); System.exit(0); } Main main = new Main(); main.print(args); main.merge_sort(args, 0, args.length - 1); main.print(args); } public void print(String[] array) { print(array, 0, array.length - 1); } public void print(String[] array, int start, int end) { if (start > end || start < 0 || end > array.length - 1) return; for (int i = start; i <= end; i++) { System.out.print(array[i] + " "); } System.out.println(); } public void merge_sort(String[] array, int start, int end) { print(array, start, end); if (end == start) return; int mid = (start + end) / 2; merge_sort(array, start, mid); merge_sort(array, mid + 1, end); if (array[mid].compareTo(array[mid + 1]) <= 0) return; int i = start; int j = mid + 1; String[] arraycopy = new String[end - start + 1]; System.arraycopy(array, start, arraycopy, 0, end - start + 1); int index = start; while (i <= mid && j <= end) { if (arraycopy[i - start].compareTo(arraycopy[j - start]) > 0) { array[index++] = arraycopy[j++ - start]; } else { array[index++] = arraycopy[i++ - start]; } } while (i <= mid) array[index++] = arraycopy[i++ - start]; while (j <= end) array[index++] = arraycopy[j++ - start]; } }

Square Root from Binary Search to Newton's Method

Task: Calculate the Square Root of Double value in Java

The ideal way to calculate the value of square root is using Newton's Method, but from my experience, I can barely remember that formula, especially when you are in a tidy timed online contest, there will be no time to google much on this topic. So it comes to an end with a reasonable solution: Binary Search, or someone call it bisection.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

import java.lang.Exception; public class Main{ public static void main(String[] args){ Main main = new Main(); System.out.println(main.square_root(Double.parseDouble(args[0]))); } public double square_root(double number) { if (number < 0.0) { throw new ArithmeticException(); } double left = 0.0; double right = Math.max(1.0, number); while(right - left > 10e-9) { double mid = (left + right) / 2.0; if (mid*mid > number) right = mid; else left = mid; } return left; } }

When I have this code into test, the result we have is:

3.0 - > 1.7320508044213057
4.0 - > 2.0
9.0 - > 2.9999999972060323
16.0 - > 4.0
25.0 - > 4.999999998835847

We can see the result is pretty good and close.

However, the result is still far from our expectation.

Modification:

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

import java.lang.Exception; public class Main{ public static void main(String[] args){ Main main = new Main(); System.out.println(main.square_root(Double.parseDouble(args[0]))); } public double square_root(double number) { if (number < 0.0) { throw new ArithmeticException(); } double left = 0.0; double right = Math.max(1.0, number); double prev = 0.0; double mid = (left + right) / 2.0; while(Math.abs(prev - mid) > 10e-9) { if (mid*mid > number) { right = mid; } else { left = mid; } prev = mid; mid = (left + right) / 2.0; } return mid; } }

The result:

3.0 - > 1.7320508044213057
4.0 - > 2.0000000074505806
9.0 - > 2.9999999972060323
16.0 - > 4.000000007450581
25.0 - > 4.999999998835847

Observation:

One of the observation is if we divide N by a number greater than it's square root, we get a number that is less than it's square root. Conversely, if we divide N by a number less than it's square root we get a number greater than it's square root. And of course, dividing N by it's square root gives us it's square root. This means:

Square_Root(81.0) = 9.0
81 / 3 = 27
81 / 5 = 16.2
81 / 10 = 8.1

So after checking on the if mid^2 value is greater than N, or not, we always have our real square root between divider and quotation. So we can update the code slightly as below:

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

import java.lang.Exception; public class Main{ public static void main(String[] args){ Main main = new Main(); System.out.println(main.square_root(Double.parseDouble(args[0]))); } public double square_root(double number) { if (number < 0.0) { throw new ArithmeticException(); } double left = 0.0; double right = Math.max(1.0, number); double prev = 0.0; double mid = (left + right) / 2.0; while(Math.abs(prev - mid) > 10e-9) { if (mid*mid > number) { right = mid; left = number / mid; // added this line. } else { left = mid; right = number / mid; // added this line. } prev = mid; mid = (left + right) / 2.0; } return mid; } }

Result:

3.0 - > 1.7320508075688772
4.0 - > 2.0
9.0 - > 3.0
16.0 - > 4.0
25.0 - > 5.0

As you can see, this result is perfect for our current precision (10e-9); We can leave precision here so far. But we can't just stop here, let's see if we can make our code more precisely.

Observation:

From above code, when we calculate the mid of left and right, we always use mid = (left + right) / 2.0, so for each case, we have:

• mid * mid > number, mid = (left + right) / 2.0 = (number / mid + mid) / 2.0;
• mid * mid <= number, mid = (left + right) / 2.0 = (mid + number / mid ) / 2.0;

So, mid is always equal to (mid + number / mid) / 2.0;

Then we could have our code modified as:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

import java.lang.Exception; public class Main{ public static void main(String[] args){ Main main = new Main(); System.out.println(main.square_root(Double.parseDouble(args[0]))); } public double square_root(double number) { if (number < 0.0) { throw new ArithmeticException(); } double mid = number; double prev = 0.0; while(Math.abs(prev - mid) > 10e-9) { prev = mid; mid = (mid + number / mid) / 2.0; } return mid; } }

The precision stays the same, but the code is much more precisely, and THIS IS Newton's Method.
We could easily derive from our binary search.