Merge k sorted arrays
Here given code implementation process.
//C Program
//Merge k sorted arrays
#include <stdio.h>
#include <stdlib.h>
#define COLS 6
void marge(int arr[][COLS],int row)
{
int counter = 0, position=-1, element=0;
int *active=(int*)calloc(row,sizeof(int));;
int status=0;
int *result=(int*)malloc(sizeof(int)*row*COLS);
do
{
status=0;
position=-1;
for (int i = 0; i < row; ++i)
{
if(active[i]<COLS)
{
if(position==-1)
{
status=1;
//get first element
element=arr[i][active[i]];
}
if(status!=0 && element >= arr[i][active[i]])
{
//Get smallest element
position=i;
element=arr[i][active[i]];
}
}
}
if(status==1)
{
//put smallest element
result[counter++]=element;
//update index
active[position]++;
}
}while(status==1);
for (int i = 0; i < row*COLS; ++i)
{
//assign bew result
*(*arr+i)=result[i];
}
free(result);
result=NULL;
free(active);
active=NULL;
}
//Print array elements
void display(int arr[][COLS],int row)
{
for (int i = 0; i < row; i++)
{
for (int j= 0; j < COLS; j++)
{
printf("%4d", arr[i][j]);
}
printf("\n");
}
}
int main()
{
int arr[][COLS]={
{1, 5, 6, 9, 11, 12},
{-1, 0, 2, 5, 7, 10},
{-5, 3, 6, 8, 14, 20},
{2, 3, 4, 14, 17, 19}
};
int rows=sizeof(arr)/sizeof(arr[0]);
printf("Before\n");
display(arr,rows);
marge(arr,rows);
printf("After\n");
display(arr,rows);
return 0;
}
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
/*
C++ Program
Merge k sorted arrays
*/
#include <iostream>
#define col 6
using namespace std;
class MyArray {
public:
void marge(int arr[][col],int row) {
int *active = new int[col];
bool status = true;
int *result = new int[row *col];
int counter = 0, position = -1, element = 0;
int i = 0, j = 0;
while (status == true) {
status = false;
position = -1;
i = 0;
while (i < row) {
if (active[i] < col) {
if (position == -1) {
status = true;
element = arr[i][active[i]];
}
if (status != false && element >= arr[i][active[i]]) {
position = i;
element = arr[i][active[i]];
}
}
i++;
}
if (status == true) {
result[counter++] = element;
active[position]++;
}
}
i = 0;
counter = 0;
while (i < row) {
j = 0;
while (j < col) {
arr[i][j] = result[counter];
j++;
counter++;
}
i++;
}
}
void display(int arr[][col],int row) {
int i = 0, j = 0;
while (i < row) {
j = 0;
while (j < col) {
cout << " "<< arr[i][j];
j++;
}
cout <<"\n";
i++;
}
}
};
int main() {
MyArray obj;
int arr[][col] = {
{
1, 5, 6, 9, 11, 12
},
{
-1, 0, 2, 5, 7, 10
},
{
-5, 3, 6, 8, 14, 20
},
{
2, 3, 4, 14, 17, 19
}
};
int row = sizeof(arr)/sizeof(arr[0]);
cout << "Before\n";
obj.display(arr,row);
obj.marge(arr,row);
cout << "After\n";
obj.display(arr,row);
}
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
/*
Java Program
Merge k sorted arrays
*/
public class MyArray {
public void marge(int[][] arr) {
int row = arr.length;
int col = arr[0].length;
int[] active = new int[row];
boolean status = true;
int[] result = new int[row *col];
int counter = 0, position = -1, element = 0;
int i = 0, j = 0;
while (status == true) {
status = false;
position = -1;
i = 0;
while (i < row) {
if (active[i] < col) {
if (position == -1) {
status = true;
//get first element
element = arr[i][active[i]];
}
if (status != false && element >= arr[i][active[i]]) {
//Get smallest element
position = i;
element = arr[i][active[i]];
}
}
i++;
}
if (status == true) {
//put smallest element
result[counter++] = element;
//update index
active[position]++;
}
}
i = 0;
counter = 0;
//set result to actual array
while (i < row) {
j = 0;
while (j < col) {
arr[i][j] = result[counter];
j++;
counter++;
}
i++;
}
}
//Print array elements
public void display(int[][] arr) {
int i = 0, j = 0;
int row = arr.length;
int col = arr[0].length;
while (i < row) {
j = 0;
while (j < col) {
System.out.print(" " + arr[i][j]);
j++;
}
System.out.print("\n");
i++;
}
}
public static void main(String[] args) {
MyArray obj = new MyArray();
int [][]arr={
{1, 5, 6, 9, 11, 12},
{-1, 0, 2, 5, 7, 10},
{-5, 3, 6, 8, 14, 20},
{2, 3, 4, 14, 17, 19}
};
System.out.print("Before\n");
obj.display(arr);
obj.marge(arr);
System.out.print("After\n");
obj.display(arr);
}
}
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
/*
C# Program
Merge k sorted arrays
*/
using System;
public class MyArray {
public void marge(int[,] arr) {
int row = arr.GetLength(0);
int col = arr.GetLength(1);
int[] active = new int[row];
Boolean status = true;
int[] result = new int[row *col];
int counter = 0, position = -1, element = 0;
int i = 0, j = 0;
while (status == true) {
status = false;
position = -1;
i = 0;
while (i < row) {
if (active[i] < col) {
if (position == -1) {
status = true;
//get first element
element = arr[i,active[i]];
}
if (status != false && element >= arr[i,active[i]]) {
//Get smallest element
position = i;
element = arr[i,active[i]];
}
}
i++;
}
if (status == true) {
//put smallest element
result[counter++] = element;
//update index
active[position]++;
}
}
i = 0;
counter = 0;
//set result to actual array
while (i < row) {
j = 0;
while (j < col) {
arr[i,j] = result[counter];
j++;
counter++;
}
i++;
}
}
//Print array elements
public void display(int[,] arr) {
int i = 0, j = 0;
int row = arr.GetLength(0);
int col = arr.GetLength(1);
while (i < row) {
j = 0;
while (j < col) {
Console.Write(" " + arr[i,j]);
j++;
}
Console.Write("\n");
i++;
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
int [,]arr={
{1, 5, 6, 9, 11, 12},
{-1, 0, 2, 5, 7, 10},
{-5, 3, 6, 8, 14, 20},
{2, 3, 4, 14, 17, 19}
};
Console.Write("Before\n");
obj.display(arr);
obj.marge(arr);
Console.Write("After\n");
obj.display(arr);
}
}
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
#C++ Program
#Merge k sorted list
class MyArray :
def marge(self, arr) :
row = len(arr)
col = len(arr[0])
active = [0]*row
status = True
result = [0]*(row * col)
counter = 0
position = -1
element = 0
i = 0
j = 0
while (status == True) :
status = False
position = -1
i = 0
while (i < row) :
if (active[i] < col) :
if (position == -1) :
status = True
element = arr[i][active[i]]
if (status != False and element >= arr[i][active[i]]) :
position = i
element = arr[i][active[i]]
i += 1
if (status == True) :
result[counter] = element
active[position] += 1
counter+=1
i = 0
counter = 0
while (i < row) :
j = 0
while (j < col) :
arr[i][j] = result[counter]
j += 1
counter += 1
i += 1
def display(self, arr) :
i = 0
j = 0
row = len(arr)
col = len(arr[0])
while (i < row) :
j = 0
while (j < col) :
print(arr[i][j],end=" ")
j += 1
print()
i += 1
def main() :
obj = MyArray()
arr = [
[1, 5, 6, 9, 11, 12],
[-1, 0, 2, 5, 7, 10],
[-5, 3, 6, 8, 14, 20],
[2, 3, 4, 14, 17, 19]
]
print("Before\n")
obj.display(arr)
obj.marge(arr)
print("After\n")
obj.display(arr)
if __name__ == "__main__":
main()
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
# Ruby Program
# Merge k sorted Array
class MyArray
def marge(arr)
row = arr.length
col = arr[0].length
active = Array.new(row,0)
status = true
result = Array.new(row*col,0)
counter = 0
position = -1
element = 0
i = 0
j = 0
while (status == true)
status = false
position = -1
i = 0
while (i < row)
if (active[i] < col)
if (position == -1)
status = true
element = arr[i][active[i]]
end
if (status != false and element >= arr[i][active[i]])
position = i
element = arr[i][active[i]]
end
end
i += 1
end
if (status == true)
result[counter] = element
active[position] += 1
counter += 1
end
end
i = 0
counter = 0
while (i < row)
j = 0
while (j < col)
arr[i][j] = result[counter]
j += 1
counter += 1
end
i += 1
end
end
def display(arr)
i = 0
j = 0
row = arr.length
col = arr[0].length
while (i < row)
j = 0
while (j < col)
print(" ", arr[i][j])
j += 1
end
print("\n")
i += 1
end
end
end
def main()
obj = MyArray.new()
arr = [
[1, 5, 6, 9, 11, 12],
[-1, 0, 2, 5, 7, 10],
[-5, 3, 6, 8, 14, 20],
[2, 3, 4, 14, 17, 19]
]
print("Before\n")
obj.display(arr)
obj.marge(arr)
print("After\n")
obj.display(arr)
end
main()
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
<?php
/*
Php Program
Merge k sorted Array
*/
class MyArray {
public function marge(&$arr) {
$row = count($arr);
$col = count($arr[0]);
$active = array_fill(0, $row, 0);
$status = true;
$result = array_fill(0, $row*$col, 0);
$counter = 0;
$position = -1;
$element = 0;
$i = 0;
$j = 0;
while ($status == true) {
$status = false;
$position = -1;
$i = 0;
while ($i < $row) {
if ($active[$i] < $col) {
if ($position == -1) {
$status = true;
$element = $arr[$i][$active[$i]];
}
if ($status != false && $element >= $arr[$i][$active[$i]]) {
$position = $i;
$element = $arr[$i][$active[$i]];
}
}
$i++;
}
if ($status == true) {
$result[$counter] = $element;
$active[$position]++;
$counter++;
}
}
$i = 0;
$counter = 0;
while ($i < $row) {
$j = 0;
while ($j < $col) {
$arr[$i][$j] = $result[$counter];
$j++;
$counter++;
}
$i++;
}
}
public function display($arr) {
$i = 0;
$j = 0;
$row = count($arr);
$col = count($arr[0]);
while ($i < $row) {
$j = 0;
while ($j < $col) {
echo(" ". $arr[$i][$j]);
$j++;
}
echo("\n");
$i++;
}
}
}
function main() {
$obj = new MyArray();
$arr = array(
array(1, 5, 6, 9, 11, 12),
array(-1, 0, 2, 5, 7, 10),
array(-5, 3, 6, 8, 14, 20),
array(2, 3, 4, 14, 17, 19)
);
echo("Before\n");
$obj->display($arr);
$obj->marge($arr);
echo("After\n");
$obj->display($arr);
}
main();
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
/*
Node JS Program
Merge k sorted Array
*/
class MyArray {
marge(arr) {
var row = arr.length;
var col = arr[0].length;
var active = Array(row).fill(0);
var status = true;
var result = Array(row*col).fill(0);
var counter = 0;
var position = -1;
var element = 0;
var i = 0;
var j = 0;
while (status == true) {
status = false;
position = -1;
i = 0;
while (i < row) {
if (active[i] < col) {
if (position == -1) {
status = true;
element = arr[i][active[i]];
}
if (status != false && element >= arr[i][active[i]]) {
position = i;
element = arr[i][active[i]];
}
}
i++;
}
if (status == true) {
result[counter] = element;
active[position]++;
counter++;
}
}
i = 0;
counter = 0;
while (i < row) {
j = 0;
while (j < col) {
arr[i][j] = result[counter];
j++;
counter++;
}
i++;
}
}
display(arr) {
var i = 0;
var j = 0;
var row = arr.length;
var col = arr[0].length;
while (i < row) {
j = 0;
while (j < col) {
process.stdout.write(" " + arr[i][j]);
j++;
}
process.stdout.write("\n");
i++;
}
}
}
function main() {
var obj = new MyArray();
var arr = [
[1, 5, 6, 9, 11, 12],
[-1, 0, 2, 5, 7, 10],
[-5, 3, 6, 8, 14, 20],
[2, 3, 4, 14, 17, 19]
];
process.stdout.write("Before\n");
obj.display(arr);
obj.marge(arr);
process.stdout.write("After\n");
obj.display(arr);
}
main();
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
/*
Swift 4 Program
Merge k sorted Array
*/
class MyArray {
func marge(_ arr: inout [[Int]] ) {
let row: Int = arr.count;
let col: Int = arr[0].count;
var active = Array(repeating:0,count:row);
var status: Bool = true;
var result = Array(repeating:0,count:row*col);
var counter: Int = 0;
var position = -1;
var element = 0;
var i: Int = 0;
var j = 0;
while (status == true) {
status = false;
position = -1;
i = 0;
while (i < row) {
if (active[i] < col) {
if (position == -1) {
status = true;
element = arr[i][active[i]];
}
if (status != false && element >= arr[i][active[i]]) {
position = i;
element = arr[i][active[i]];
}
}
i += 1;
}
if (status == true) {
result[counter] = element;
active[position] += 1;
counter += 1;
}
}
i = 0;
counter = 0;
while (i < row) {
j = 0;
while (j < col) {
arr[i][j] = result[counter];
j += 1;
counter += 1;
}
i += 1;
}
}
func display(_ arr: [[Int]] ) {
var i: Int = 0;
var j = 0;
let row: Int = arr.count;
let col: Int = arr[0].count;
while (i < row) {
j = 0;
while (j < col) {
print(arr[i][j], terminator:" ");
j += 1;
}
print();
i += 1;
}
}
}
func main() {
let obj: MyArray = MyArray();
var arr = [
[1, 5, 6, 9, 11, 12],
[-1, 0, 2, 5, 7, 10],
[-5, 3, 6, 8, 14, 20],
[2, 3, 4, 14, 17, 19]
];
print("Before\n");
obj.display(arr);
obj.marge(&arr);
print("After\n");
obj.display(arr);
}
main();
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
/*
Scala Program
Merge k sorted arrays
*/
class MyArray {
def marge(arr: Array[Array[Int]]): Unit = {
var row: Int = arr.length;
var col: Int = arr(0).length;
var active: Array[Int] = Array.fill[Int](row)(0);
var status: Boolean = true;
var result: Array[Int] = Array.fill[Int](row * col)(0);
var counter: Int = 0;
var position: Int = -1;
var element: Int = 0;
var i: Int = 0;
var j: Int = 0;
while (status == true) {
status = false;
position = -1;
i = 0;
while (i < row) {
if (active(i) < col) {
if (position == -1) {
status = true;
//get first element
element = arr(i)(active(i));
}
if (status != false &&
element >= arr(i)(active(i))) {
//Get smallest element
position = i;
element = arr(i)(active(i));
}
}
i += 1;
}
if (status == true) {
//put smallest element
result(counter) = element;
//update index
counter += 1;
active(position) += 1;
}
}
i = 0;
counter = 0;
//set result to actual array
while (i < row) {
j = 0;
while (j < col) {
arr(i)(j) = result(counter);
j += 1;
counter += 1;
}
i += 1;
}
}
//Print array elements
def display(arr: Array[Array[Int]]): Unit = {
var i: Int = 0;
var j: Int = 0;
var row: Int = arr.length;
var col: Int = arr(0).length;
while (i < row) {
j = 0;
while (j < col) {
print(" " + arr(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
var arr: Array[Array[Int]] = Array(
Array(1, 5, 6, 9, 11, 12),
Array(-1, 0, 2, 5, 7, 10),
Array(-5, 3, 6, 8, 14, 20),
Array(2, 3, 4, 14, 17, 19));
print("Before\n");
obj.display(arr);
obj.marge(arr);
print("After\n");
obj.display(arr);
}
}
Output
Before
1 5 6 9 11 12
-1 0 2 5 7 10
-5 3 6 8 14 20
2 3 4 14 17 19
After
-5 -1 0 1 2 2
3 3 4 5 5 6
6 7 8 9 10 11
12 14 14 17 19 20
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment