JetBrains Academy: Merge sort in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki
Count the number of merge operations:
Given an array of integers. Output the number of merge operations to solve the array using the standard top-down merge sort.
The first line of the input contains N - a number of elements in the array. The second line contains array you need to sort.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = Integer.parseInt(scanner.nextLine());
int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
.mapToInt(Integer::parseInt)
.toArray();
int mergeCount = size - 1;
System.out.println(mergeCount);
}
}or
import java.util.*;
public class Main {
public static void main(String[] args) {
System.out.println(new Scanner(System.in).nextInt() - 1);
}
}Merge all sequences:
Write a program that reads several descending sorted sequences of ints and merges them into one sequence. The merged sequence should be also sorted in the same order. Note, a sequence can have identical elements.
Input data format:
The first line contains the integer number of sequences N.
The followed N lines have two parts: the number of elements Mk in a k-sequence and its elements.
Output data format:
All elements of the merged sequence. The elements should be separated by spaces.
Constraints:
1 ⤠N ⤠100
1 ⤠Mk ⤠50000
import java.util.*;
import java.util.stream.Collectors;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
StringBuilder builder = new StringBuilder();
String numbers;
int arraysCount = Integer.parseInt(scanner.nextLine());
int size = 0;
for (int i = 0; i < arraysCount; i++) {
size += Integer.parseInt(scanner.next());
builder.append(scanner.nextLine().trim() + " ");
}
numbers = builder.toString();
int[] array = Arrays.stream(numbers.split("\\s+"))
.mapToInt(Integer::parseInt)
.toArray();
mergeSort(array, 0, size);
String sorted = Arrays.stream(array)
.mapToObj(Integer::toString)
.collect(Collectors.joining(" "));
System.out.println(sorted);
}
public static void mergeSort(int[] array, int leftIncl, int rightExcl) {
// the base case: if subarray contains <= 1 items, stop dividing because it's sorted
if (rightExcl <= leftIncl + 1) {
return;
}
/* divide: calculate the index of the middle element */
int middle = leftIncl + (rightExcl - leftIncl) / 2;
mergeSort(array, leftIncl, middle); // conquer: sort the left subarray
mergeSort(array, middle, rightExcl); // conquer: sort the right subarray
/* combine: merge both sorted subarrays into sorted one */
merge(array, leftIncl, middle, rightExcl);
}
private static void merge(int[] array, int left, int middle, int right) {
int i = left; // index for the left subarray
int j = middle; // index for the right subarray
int k = 0; // index for the temp subarray
int[] temp = new int[right - left]; // temporary array for merging
/* get the next lesser element from one of two subarrays
and then insert it in the array until one of the subarrays is empty */
while (i < middle && j < right) {
if (array[i] >= array[j]) {
temp[k] = array[i];
i++;
} else {
temp[k] = array[j];
j++;
}
k++;
}
/* insert all the remaining elements of the left subarray in the array */
for (; i < middle; i++, k++) {
temp[k] = array[i];
}
/* insert all the remaining elements of the right subarray in the array */
for (; j < right; j++, k++) {
temp[k] = array[j];
}
/* effective copying elements from temp to array */
System.arraycopy(temp, 0, array, left, temp.length);
}
}or
import java.util.*;
import java.util.stream.Collectors;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] sorted = new int[0];
final int numberOfArrays = Integer.parseInt(scanner.nextLine());
for (int i = 0; i < numberOfArrays; i++) {
final int elements = Integer.parseInt(scanner.next());
int[] array = new int[elements];
for (int j = 0; j < elements; j++) {
array[j] = Integer.parseInt(scanner.next());
}
sorted = mergeArrays(sorted, array);
}
String result = Arrays.stream(sorted)
.mapToObj(Integer::toString)
.collect(Collectors.joining(" "));
System.out.println(result);
}
public static int[] mergeArrays(int[] array1, int[] array2) {
int[] merged = new int[array1.length + array2.length];
int i = 0; // index of first array
int j = 0; // index of second array
int k = 0; // index of merged array
/* get the next greater element from one of two subarrays
and then insert it in the array until one of the subarrays is empty */
while (i < array1.length && j < array2.length) {
if (array1[i] >= array2[j]) {
merged[k] = array1[i];
i++;
} else {
merged[k] = array2[j];
j++;
}
k++;
}
/* insert all the remaining elements of the first array in the array */
System.arraycopy(array1, i, merged, k, array1.length - i);
/* insert all the remaining elements of the second array in the array */
System.arraycopy(array2, j, merged, k, array2.length - j);
return merged;
}
}The number of inversions:
The first line contains number 1 ⤠n ⤠105, second one â array A[1âŚn], containing natural numbers not greater than 109. You need to calculate the number of pairs of indexes 1 ⤠i < j ⤠n, for which A[i] > A[j].
Such pair of elements is called the inversion. The number of inversion in the array is in some way its measure of random nature: for example, there are no inversions at all in an array arranged in a non-decreasing order, and in an array, arranged in descending order, every two elements form an inversion.
The result should be long, because an array can contain a lot of inversions.
For example, the sequence 2, 4, 1, 3, 5 has three inversions: (2, 1), (4, 1), (4, 3).
Modify merge sort and solve the problem using it.
import java.util.*;
class Main {
public static long inversions = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
final int size = Integer.parseInt(scanner.nextLine());
int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
.mapToInt(Integer::parseInt)
.toArray();
mergeSort(array, 0, size);
System.out.println(inversions);
}
public static void mergeSort(int[] array, int leftIncl, int rightExcl) {
// the base case: if subarray contains <= 1 items, stop dividing because it's sorted
if (rightExcl <= leftIncl + 1) {
return;
}
/* divide: calculate the index of the middle element */
int middle = leftIncl + (rightExcl - leftIncl) / 2;
mergeSort(array, leftIncl, middle); // conquer: sort the left subarray
mergeSort(array, middle, rightExcl); // conquer: sort the right subarray
/* count inversions */
countInversions(array, leftIncl, middle, rightExcl);
}
private static void countInversions(int[] array, int left, int middle, int right) {
int i = left; // index for the left subarray
int j = middle; // index for the right subarray
int k = 0; // index for the temp subarray
int[] temp = new int[right - left]; // temporary array for merging
/* get the next lesser element from one of two subarrays
and then insert it in the array until one of the subarrays is empty */
while (i < middle && j < right) {
if (array[i] > array[j]) {
inversions += middle - i;
temp[k] = array[j];
j++;
} else {
temp[k] = array[i];
i++;
}
k++;
}
/* insert all the remaining elements of the left subarray in the array */
System.arraycopy(array, i, temp, k, middle - i);
/* insert all the remaining elements of the right subarray in the array */
System.arraycopy(array, j, temp, k, right - j);
/* effective copying elements from temp to array */
System.arraycopy(temp, 0, array, left, temp.length);
}
}