Posted on by Kalkicode
Code Array

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

Comment

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





Categories
Relative Post