Java Programming Assignment: Merging K Sorted Arrays (Stable Merge)

 

Assignment Description

Language: Java

Task:
You are required to merge k sorted arrays of Student objects into a single sorted array.

• Your algorithm must be stable.

• You are NOT allowed to call the constructor of class Student, except in main.

• You may NOT modify class Student in any way.

---

Provided Starter Code

java

public class StableMerger {

    /**
     * No modification to class Student is allowed.
     * If you change anything here, your work will not be graded.
     */
    static class Student {
        String name;
        double grade;
        public Student(String n, double g) {
            name = n;
            grade = g;
        }
        public String toString() {
            return "(" + name + ", " + grade + ")";
        }
    }

    /**
     * Merge k sorted arrays into a single sorted array.
     * Your algorithm must be stable.
     * Running time: O(   ). (n is the total number of students.)
     */
    public static Student[] merge(Student[][] a) {
        // Your code here
        return null;
    }

    public static void main(String[] args) {
        String[][] names = {
            {"Gloria Tang", "Andy Lau", "McDull"},
            {"Eason Chan", "Denise Ho", "Jennifer Chan", "Joey Yung", "Kay Tse", "Jacky Cheung", "Anita Mui"},
            {"Winnie", "Mickey", "Teddy", "Peppa"}
        };
        double[][] grades = {
            {60, 60, 60},
            {40, 60, 70, 80, 90, 95, 100},
            {0, 90, 95, 100}
        };
        Student[][] a = new Student[names.length][];
        for (int i = 0; i < names.length; i++) {
            a[i] = new Student[names[i].length];
            for (int j = 0; j < names[i].length; j++)
                a[i][j] = new Student(names[i][j], grades[i][j]);
        }
        System.out.println(Arrays.toString(merge(a)));
    }
}

---

Important Constraints

• You cannot modify the Student class.

• You cannot call the Student constructor except in main.

• Your merge algorithm must be stable.

• Your solution should have efficient time complexity (O(n) where n is the total number of students, if possible).

---

Notes

• You are to complete the merge method so it merges all input arrays into a single sorted array of Student objects, maintaining stability.

• The sorting order should be based on grade.

Solution

java code

import java.util.Arrays;

import java.util.ArrayList;

import java.util.Map;

import java.util.*;

import java.util.stream.Collectors;

public class StableMerger {

static class Student {

String name;

double grade;

public Student(String n, double g) {

name = n; grade = g;

}

public String toString() {

return "(" + name + ", " + grade + ")";

}

}

public static Student[] merge(Student[][] a) {

 LinkedHashMap<String, Double> myMap = new LinkedHashMap<String, Double>();

for (int i = 0; i < a.length; i++)

for (int j = 0; j < a[i].length; j++)

 myMap.put(a[i][j].name , a[i][j].grade);

LinkedHashMap<String, Double> sortedMap = new LinkedHashMap<>();

myMap.entrySet()

    .stream()

    .sorted(Map.Entry.comparingByValue())

    .forEachOrdered(x -> sortedMap.put((String)x.getKey(), (Double)x.getValue()));

Student[] merge = new Student[sortedMap.size()];

int x = 0;

for (Map.Entry<String, Double> entry : sortedMap.entrySet()) {

    merge[x] = new Student((String)entry.getKey() , Double.valueOf(entry.getValue().toString()) );

    x++;

}

  return  merge;

}

public static void main(String[] args) {

String[][] names = {{"Gloria Tang", "Andy Lau", "McDull"},

                {"Eason Chan", "Denise Ho", "Jennifer Chan", "Joey Yung", "Kay Tse", "Jacky Cheung", "Anita Mui"},

                {"Winnie", "Mickey", "Teddy", "Peppa"}};

        double[][] grades = {{60, 60, 60}, {40, 60, 70, 80, 90, 95, 100}, {0, 90, 95, 100}};

        Student[][] a = new Student[names.length][];

        for (int i = 0; i < names.length; i++) {

            a[i] = new Student[names[i].length];

            for (int j = 0; j < names[i].length; j++)

                a[i][j]= new Student(names[i][j], grades[i][j]);

        }

        System.out.println(Arrays.toString(merge(a)));

    }// main

}// class

📩 Need a similar solution? Email me: adel455@hotmail.com