This is a Java Program to Implement K Way Merge Algorithm. K Way Merge Algorithm is used to merge K sorted arrays of size N into a single array.
Here is the source code of the Java Program to Implement K Way Merge Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
/** * Java Program to Implement K Way Merge Algorithm **/ import java.util.Scanner; /** Class KWayMerge **/ public class KWayMerge { /** Function to merge arrays **/ private int[] merge(int[][] arr) { int K = arr.length; int N = arr[0].length; /** array to keep track of non considered positions in subarrays **/ int[] curPos = new int[K]; /** final merged array **/ int[] mergedArray = new int[K * N]; int p = 0; while (p < K * N) { int min = Integer.MAX_VALUE; int minPos = -1; /** search for least element **/ for (int i = 0; i < K; i++) { if (curPos[i] < N) { if (arr[i][curPos[i]] < min) { min = arr[i][curPos[i]]; minPos = i; } } } curPos[minPos]++; mergedArray[p++] = min; } return mergedArray; } /** Main method **/ public static void main(String[] args) { Scanner scan = new Scanner( System.in ); System.out.println("K Way Merge Test\n"); /** Accept k and n **/ System.out.println("Enter K and N"); int K = scan.nextInt(); int N = scan.nextInt(); int[][] arr = new int[K][N]; /** Accept all elements **/ System.out.println("Enter "+ K +" sorted arrays of length "+ N); for (int i = 0; i < K; i++) for (int j = 0; j < N; j++) arr[i][j] = scan.nextInt(); KWayMerge kwm = new KWayMerge(); int[] mergedArray = kwm.merge(arr); /** Print merged array **/ System.out.println("\nMerged Array : "); for (int i = 0; i < mergedArray.length; i++) System.out.print(mergedArray[i] +" "); System.out.println(); } }
K Way Merge Test Enter K and N 5 4 Enter 5 sorted arrays of length 4 2 4 6 19 1 20 35 67 3 5 7 11 45 46 47 48 3 9 100 200 Merged Array : 1 2 3 3 4 5 6 7 9 11 19 20 35 45 46 47 48 67 100 200 K Way Merge Test Enter K and N 4 5 Enter 4 sorted arrays of length 5 2 4 6 19 94 2 8 5 19 63 3 5 7 11 13 1 10 25 50 100 Merged Array : 1 2 2 3 4 5 6 7 8 5 10 11 13 19 19 25 50 63 94 100 K Way Merge Test Enter K and N 3 10 Enter 3 sorted arrays of length 10 3 6 9 12 15 18 21 24 27 30 2 5 8 11 14 17 20 23 26 29 1 4 7 10 13 16 19 22 25 28 Merged 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
Related posts:
Creating a Web Application with Spring 5
Guide to @ConfigurationProperties in Spring Boot
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays
Java Program to Check whether Directed Graph is Connected using DFS
Java Program to Implement Slicker Algorithm that avoids Triangulation to Find Area of a Polygon
Java Program to Check Cycle in a Graph using Topological Sort
Java Program to Generate Randomized Sequence of Given Range of Numbers
Java Program to Encode a Message Using Playfair Cipher
Iterable to Stream in Java
Spring Security Form Login
Spring Boot: Customize the Jackson ObjectMapper
Introduction to Project Reactor Bus
Initialize a HashMap in Java
Count Occurrences of a Char in a String
Java InputStream to Byte Array and ByteBuffer
Posting with HttpClient
Java Program to Check Whether Topological Sorting can be Performed in a Graph
Quick Guide to Spring MVC with Velocity
HashMap trong Java hoạt động như thế nào?
Java Program to Implement PrinterStateReasons API
Composition, Aggregation, and Association in Java
Request Method Not Supported (405) in Spring
Java Convenience Factory Methods for Collections
Hướng dẫn Java Design Pattern – Facade
Spring Boot - Enabling Swagger2
Convert char to String in Java
Java Program to Represent Graph Using Adjacency List
Java Program to Implement Leftist Heap
Removing all Nulls from a List in Java
Hướng dẫn sử dụng luồng vào ra ký tự trong Java
New Features in Java 10
Java Program to Implement Min Hash