Как отсортировать карту без использования сопоставимого и Comparator Interface?Как написать пользовательскую сортировку?

Question

Задача - У меня есть класс ученика, он содержит имя, номер броска, три предметных оценки m1, m2, m3 и итоговые оценки.Мне нужно отсортировать объект Student по общему количеству баллов, если два или более балла студентов равны, а затем отсортировать его по имени. Примечание - Я должен гуглить, но не получаю ожидаемого решения в вопросе stackoverflow, каждый из которых использует интерфейс Comparable и Comparator.

Я создал класс Studnt

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

Mainclass

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);
        }

    }
}

На самом деле, я использую TreeMap, он сортирует значение по ключу (общее количество баллов является ключевым в моем TreeMap).но двое или более учеников имеют одинаковые оценки.Затем более старый объект ученика (значение) заменяется новым учеником из-за того, что ключ не позволяет дублировать

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]

единственные уникальные общие метки, хранящиеся на карте

Answer 1

Поскольку вы не можете использовать существующие компаратор или алгоритмы сортировки, вам нужно сделать это самостоятельно.Я реализовал функцию static lessOrEqual, которая принимает 2 Student экземпляра, сравнивает их и возвращает значение, равное или меньше s1 или s2. larger(Student s1, Student s2), которое возвращает trueТОЛЬКО ЕСЛИ s1 больше s2.Может быть много разных способов сделать это, это действительно зависит от вас, так как это просто составная часть.Функция сначала проверяет оценки, если оценки совпадают, затем проверяет имя и возвращает соответственно.

РЕДАКТИРОВАТЬ: Как вы можете видеть, я заменил lessOrEqual на larger, поскольку сортировка выбора, который я использую, должна найти larger.Это тот же эффект, я сделал это только для лучшей читабельности.

Затем я реализовал другую функцию static, которая принимает ArrayList<Student>, сортирует ее и возвращает отсортированную.Используемый алгоритм сортировки очень прост: сортировка по выбору.Это O (N ^ 2), которое неэффективно, но я сделал это ради простоты в демонстрации ниже.

Код:

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());
        }
    }
}

Вывод:

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

Примечания:

1) Смотрите порядок добавления студентов в список, это4,3, 1, затем 2. Это доказывает, что сортировка происходит по названию, когда оценки совпадают (Джек Смит против Джона Смита).

2) Я жестко закодировал студентов, чтобы сделать лучшую демонстрацию.

3) Как вы можете заметить, я не задаю ни одну из других переменных, поскольку вопрос касается исключительно сортировки, и единственные переменные, способствующие сортировке: name и totMarks.Вам придется сделать все остальное.

4) Я использую ArrayList, но это не ограничивается этим, с простыми изменениями вы можете использовать его в обычном Student[] массиве.

5) Функция larger не обязательно должна быть static, вы можете сделать ее функцией-членом и использовать ее по-другому.Например, код выше изменится на:

    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

В интересах упрощения (т. Е. Принципа KISS) и объяснения моей «подсказки», касающейся составного ключа, ниже приводится обработанный пример.

«Ключ» к решению состоит в том, чтобы позволить дереву сортировать данные естественным образом (не IMHO, чтобы добавить к коду, делающему его более сложным, предоставляя ручную сортировку). Таким образом, ученический класс должен вернуть ключ, который дерево может естественно отсортировать.

Чтобы получить желаемый результат сортировки, ключ для дерева (общая оценка, имя студента).

Вот пересмотренный класс Student (за исключением получателей и установщиков, но я добавил новый конструктор, чтобы облегчить мне жизнь):

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);
    }

}

Примечание в методе getKey есть закомментированная строка кода с комментарием WRONG . Это относится к моему намеку на тестирование с однозначными баллами. Попробуйте поменять две строки кода, чтобы увидеть правильный и неправильный результат.

Вот главное, я удалил все элементы сканера - снова, чтобы облегчить мне жизнь. Надеюсь, вы сможете следить за этим и добавить его обратно в цикл сканирования.

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);
        }
    }
}

Надеюсь, вы согласны с тем, что это более простое решение. Существует также потенциальное повышение производительности, поскольку студенты сортируются по мере их загрузки в дерево (т.е. один раз). Производительность этой сортировки, я думаю, log (n). Сортировка при извлечении, вероятно, будет n log (n) или хуже.

Answer 3

Вместо того, чтобы хранить значения как ученик, сохраняйте их как карту (имя, ученик), чтобы при обнаружении ученика с такими же отметками он добавлялся на карту.

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());
        }
    }

}