How to sort map without using comparable and Comparator Interface? How to write Custom Sorting?

Question

Problem - I have a Student class, it contains Name, roll number, three subject marks m1,m2,m3, and total marks. I need to sort Student object according to their total marks if two or more students marks are equal then sort it according to their name. Note - I have to google it but not getting expected solution in stackoverflow question every one using Comparable and Comparator interface.

I have created class Studnt

public class Student {
    private String name;
    private Integer rollNumber;
    private int m1;
    private int m2;
    private int m3;
    private int totMarks;
    //Getter setter
}

Main class

public class StudentData {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enetr the number of Student");
        int totalStudent = sc.nextInt();
        Map<Integer,Student> map = new TreeMap<Integer,Student>();
        for(int i =0;i<totalStudent;i++) {
            Student ss = new Student();
            System.out.println("Enter the Student roll number");
            ss.setRollNumber(sc.nextInt());
            System.out.println("Enter the Student Name");
            ss.setName(sc.next());
            System.out.println("Enter the m1 marks ");
            ss.setM1(sc.nextInt());
            System.out.println("Enetr the m2 marks ");
            ss.setM2(sc.nextInt());
            System.out.println("Enter the m3 marks ");
            ss.setM3(sc.nextInt());
            ss.setTotMarks(ss.getM1()+ss.getM2()+ss.getM3());

            map.put(ss.getTotMarks(),ss);
            ss=null;
        }   
        //stdList.forEach(System.out::print);
        for(Map.Entry<Integer,Student> m :map.entrySet()) {
            System.out.println(m);
        }

    }
}

Actually, I am using TreeMap it sort the value by key(total marks is key in my TreeMap). but two or more students have equal marks. Then older student object (value) replaced by the new student because of Key not allowed duplicate

output

6=Student [name=ved, rollNumber=12, m1=2, m2=2, m3=2, totMarks=6]

9=Student [name=prakash, rollNumber=56, m1=3, m2=3, m3=3, totMarks=9]

the only unique totMarks stored in the map

Answer 1

Since you can't use existing Comparator or sorting algorithms, you need to do it on your own. I have implemented a static function lessOrEqual which accepts 2 Student instances, compares them and returns whether or not s1 is less or equal to s2. larger(Student s1, Student s2) which returns true ONLY IF s1 is larger than s2. There can be many different ways of doing this, it's really up to you as it's just a comprison. The function first checks the grades, if the grades match, it will then check the name and return accordingly.

EDIT: As you can see I replaced lessOrEqual with larger since the selection sort I'm using needs to find larger. It's the same effect, I only did it for better readability of the sort.

Then I implemented another static function that accepts ArrayList<Student>, sorts it and returns it sorted. The sorting algorithm used is very basic: Selection sort. It's O(N^2) which isn't efficient, but I did it for the sake of simplicity in the demo below.

Code:

import java.util.ArrayList; 

public class Student {
    private String name;
    private Integer rollNumber;
    private int m1;
    private int m2;
    private int m3;
    private int totMarks;

    public static boolean larger(Student s1, Student s2){
        if(s1.totMarks < s2.totMarks) return false; 
        else if (s1.totMarks > s2.totMarks) return true;
        // compare names
        else return s1.name.compareTo(s2.name) > 0;
    }

    public static ArrayList<Student> sortSelection(ArrayList<Student> list){
        for(int i=0; i<list.size(); i++){
            for(int j=i+1; j< list.size(); j++){
                if(larger(list.get(i), list.get(j))){ // swap
                    Student temp = list.get(i); 
                    list.set(i, list.get(j));
                    list.set(j, temp);
                }
            }
        }
        return list;
    }
    //Getter setter
    public String getName(){
        return name; 
    }

    public void setName(String name){
        this.name = name; 
    }

    public int getTotMarks(){
        return totMarks;
    }

    public void setTotMarks(int totMarks){
        this.totMarks = totMarks; 
    }

    @Override
    public String toString(){
        return String.format("Name: %20s - Total Marks: %3d", name, totMarks);
    }

    public static void main(String[] args){
        Student s1 = new Student(); 
        Student s2 = new Student();
        Student s3 = new Student();
        Student s4 = new Student();

        s1.setName("John Smith");
        s1.setTotMarks(98);
        s2.setName("Jack Smith");
        s2.setTotMarks(98);
        s3.setName("Adam Noob");
        s3.setTotMarks(100);
        s4.setName("Ved Parkash");
        s4.setTotMarks(99);

        ArrayList<Student> list = new ArrayList<>(); 
        list.add(s4);
        list.add(s3);
        list.add(s1);
        list.add(s2);

        System.out.println("Array before sorting:");
        for(int i=0; i<list.size(); i++){
            System.out.println(list.get(i).toString());
        }

        Student.sortSelection(list);

        System.out.println("Array after sorting:");
        for(int i=0; i<list.size(); i++){
            System.out.println(list.get(i).toString());
        }
    }
}

Output:

Array before sorting:
Name:          Ved Parkash - Total Marks:  99
Name:            Adam Noob - Total Marks: 100
Name:           John Smith - Total Marks:  98
Name:           Jack Smith - Total Marks:  98
Array after sorting:
Name:           Jack Smith - Total Marks:  98
Name:           John Smith - Total Marks:  98
Name:          Ved Parkash - Total Marks:  99
Name:            Adam Noob - Total Marks: 100

Notes:

1) See the order of addition of Students into the list, it's 4,3, 1 then 2. This is to prove that it sorts according to name when the grades match (Jack Smith vs John Smith).

2) I hardcoded the students to make for a better demo.

3) As you may notice, I'm not setting any of the other variables since the question is solely about sorting, and the only contributing variables to sorting are: name and totMarks. You will have to do the rest.

4) I am using ArrayList, but this isn't limited to that, with simple changes you can use it on a normal Student[] array.

5) The function larger doesn't have to be static, you can make it a member function and use it differently. For example, the code above would change to:

    public boolean larger(Student other){
        if(totMarks < other.totMarks) return false; 
        else if (totMarks > other.totMarks) return true;
        // compare names
        else return name.compareTo(other.name) > 0;
    }

    public static ArrayList<Student> sortSelection(ArrayList<Student> list){
        for(int i=0; i<list.size(); i++){
            for(int j=i+1; j< list.size(); j++){
                // comparison way changes accordingly
                if(list.get(i).larger(list.get(j))){ // swap
                    Student temp = list.get(i); 
                    list.set(i, list.get(j));
                    list.set(j, temp);
                }
            }
        }
        return list;
    }

Answer 2

In the interests of Keeping it simple (i.e. the KISS principle) and explaining my "hint" relating to a compound key, following is the worked example.

The "key" to the solution is to let the tree sort the data naturally (not, IMHO, to add to the code making it more complex by providing a manual sort). Thus the student class needs to return a key that the tree can naturally sort.

To produce the desired sort result, the key for the Tree is (total Marks, student name).

Here is the revised Student class (minus getters and setters, but I did add a new constructor to make life easy for me):

public class Student {
    private String name;
    private Integer rollNumber;
    private int m1;
    private int m2;
    private int m3;
    private int totMarks;
    //Getter setter

    public Student() {

    }

    public Student(String name, Integer rollNumber, int m1, int m2, int m3) {
        this.name = name;
        this.rollNumber = rollNumber;
        this.m1 = m1;
        this.m2 = m2;
        this.m3 = m3;
        this.totMarks = m1 + m2 + m3;
    }

    public String getKey() {
//      return String.format("%d-%s", totMarks, name);          // WRONG!
        return String.format("%04d-%s", totMarks, name);        // Right
    }

    public String toString() {
        return String.format("%06d: %s - %d", rollNumber, name, totMarks);
    }

}

Note there is a commented out line of code in the getKey method with the comment WRONG. This relates to my hint of testing with single digit scores. Try swapping out the two lines of code to see the correct and incorrect result.

Here is the main, I removed all of the Scanner stuff - again to make life easy for me. Hopefully you can follow it and add back in your scanner loop.

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class StudentData {
    public static void main(String[] args) {
        // Initialise a list of students (as I don't want to rekey all the details each
        // time I run the program).
        List<Student> studentList = Arrays.asList(
                    new Student("Fred", 1, 2, 2, 2),      /* Score of 6 */
                    new Student("John", 2, 2, 3, 3),      /* Score of 8 */
                    new Student("Jane", 3, 20, 25, 30),      /* Score of 75 */
                    new Student("Julie", 4, 20, 15, 10)      /* Score of 45 */
                    // add as many new students as you like, and reorder them
                    // as much as you like to see if there is any difference in the
                    // result (there shouldn't be).
        );

            // Note the key of the tree is of type String - not Integer.
            // This is the heart of the algorithm, the tree will be "sorted"
            // on the natural key provided. This "natural key" is in fact
            // a compound key that is generated by combining the total score
            // and the student name.
        Map<String,Student> map = new TreeMap<String,Student>();
        for (Student ss : studentList) {
            map.put(ss.getKey(),ss);
        }   
        //stdList.forEach(System.out::print);
        for(Map.Entry<String,Student> m :map.entrySet()) {
            System.out.println(m);
        }
    }
}

I hope you agree that this is a simpler solution. There is also a potential performance benefit as the students are sorted as they are being loaded into the tree (i.e. once). The performance of this sorting is, I think, log(n). Sort on retrieval will likely be n log(n) or worse.

Answer 3

Instead of storing the values as student store them as a map of (name, student), so that when a student with the same marks is encountered, it is added to the map.

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enetr the number of Student");
    int totalStudent = sc.nextInt();
    Map<Integer, Map<String, Student>> map = new TreeMap<>();
    for(int i =0;i<totalStudent;i++) {
        Student ss = new Student();
        System.out.println("Enter the Student roll number");
        ss.setRollNumber(sc.nextInt());
        System.out.println("Enter the Student Name");
        ss.setName(sc.next());
        System.out.println("Enter the m1 marks ");
        ss.setM1(sc.nextInt());
        System.out.println("Enetr the m2 marks ");
        ss.setM2(sc.nextInt());
        System.out.println("Enter the m3 marks ");
        ss.setM3(sc.nextInt());
        ss.setTotMarks(ss.getM1()+ss.getM2()+ss.getM3());

        Integer key = ss.getTotMarks();
        if (map.get(key) == null){  // if this is a new key in the map, then create a new TreeMap and put it
            final TreeMap<String, Student> nameAndStudentMap = new TreeMap<>();
            nameAndStudentMap.put(ss.getName(), ss);
            map.put(key, nameAndStudentMap);
        }else { // if the key already existed, then get the map stored and add to it.
            map.get(key).put(ss.getName(), ss);
        }

    }
    //stdList.forEach(System.out::print);
    for(Map.Entry<Integer,Map<String, Student>> m :map.entrySet()) {
        for (Map.Entry<String, Student> nameAndStudent : m.getValue().entrySet()) {
            System.out.println(m.getKey() + " = " + nameAndStudent.getValue());
        }
    }

}