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:
How to Use if/else Logic in Java 8 Streams
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Difference Between Wait and Sleep in Java
Hướng dẫn sử dụng lớp Console trong java
Compare Two JSON Objects with Jackson
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Receive email using IMAP
Java Program to Implement Binary Search Tree
Java Program to Implement AttributeList API
Spring NoSuchBeanDefinitionException
Immutable Map Implementations in Java
Một số tính năng mới về xử lý ngoại lệ trong Java 7
Assert an Exception is Thrown in JUnit 4 and 5
Validations for Enum Types
Lấy ngày giờ hiện tại trong Java
Removing all duplicates from a List in Java
Jackson Annotation Examples
Spring Boot Security Auto-Configuration
Spring Boot - Creating Docker Image
Java Program to Implement Find all Cross Edges in a Graph
Java Program to Construct K-D Tree for 2 Dimensional Data
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to Check Multiplicability of Two Matrices
How to Round a Number to N Decimal Places in Java
Java Program to Implement ConcurrentHashMap API
Spring Boot - Scheduling
Java Scanner hasNext() vs. hasNextLine()
So sánh Array và ArrayList trong Java
Java Program to Implement the Monoalphabetic Cypher
Cơ chế Upcasting và Downcasting trong java
Guide to the ConcurrentSkipListMap
Netflix Archaius with Various Database Configurations