Лексикографическая сортировка в Java создает странный порядок

Я пытаюсь отсортировать массив объектов по именам, которые находятся внутри массива.

grades[].name

Я использую метод вставки с лексикографической сортировкой с использованием compareTo, и он вроде работает, поэтому я знаю, что правильно использую compareTo, но не все имена перемещаются правильно, и я не уверен, правильно ли я понимаю, как работает лексикографический или если моя петля вызывает проблему. Я знаю, что лексикографический сравнивает каждую букву отдельно, чтобы определить место. Первоначально я думал, что это просто дает строке числовое значение, и искал способ найти это, но я не думаю, что это было так. Я просмотрел другие вопросы о том, как работает эта сортировка, но, похоже, это не проливает света на мою проблему. Я хотел бы знать, являются ли мои проблемы циклом, моим пониманием метода сортировки или чем-то еще, вызывающим эту проблему вывода.

У меня 3 класса. Объект, вызывающий метод .insert, является ссылкой на класс, который содержит мой фактический массив, поэтому массив может оставаться закрытым.

   `GradeArray gradeArr = new GradeArray();

    gradeArr.insert("Evans", 78, courseID);
    gradeArr.insert("Smith", 77, courseID);
    gradeArr.insert("Yee", 83, courseID);
    gradeArr.insert("Adams", 63, courseID);
    gradeArr.insert("Hashimoto", 91, courseID);
    gradeArr.insert("Stimson", 89, courseID);
    gradeArr.insert("Velasquez", 72, courseID);
    gradeArr.insert("Lamarque", 74, courseID);
    gradeArr.insert("Vang", 52, courseID);
    gradeArr.insert("Creswell", 88, courseID);`

это сделать записи в массиве.

Вот мой цикл сортировки.

`  public String reportgrades() //this is grade sorted by name 
    {
        String output = "Sorted by name ";
        int in, out;
        StudentGrade temp; //this is to hold the orginal variable. 
        //for the first letter cycle
        for (out = 1; out < nElems; out++) {
            temp = grades[out];
            in = out;
            while (in > 0 && 0 < (grades[in - 1].name.compareTo(grades[in].name))) {
                grades[in] = grades[in - 1];
                in--;
            }
            grades[in] = temp;
        }
        for (int j = 0; j < nElems; j++) {
            output += grades[j].name + ", ";
        }
        return output;
    }`

Вывод, который это создает, Sorted by name Evans, Smith, Adams, Hashimoto, Stimson, Velasquez, Lamarque, Vang, Creswell, Yee,

Я не понимаю, почему Эванс и Смит раньше Адамса. Я попытался просмотреть документы о том, как работает compareTo, но, похоже, я не нашел ничего, что могло бы дать мне какую-либо информацию об этом.


java sorting lexicographic insertion-sort
person Grimmjow56    schedule 03.02.2018    source источник
comment
Это какая-то домашняя работа, где главная задача — написать собственный алгоритм сортировки? Или почему вы не используете встроенную сортировку?   -  person Ringo Store    schedule 04.02.2018
comment
Возможно, ТАК самомотивирован и хочет написать своего рода. Это могло случиться.   -  person nicomp    schedule 04.02.2018
comment
Если серьезно, это работа для SO и его/ее отладчика. Пройдите через это.   -  person nicomp    schedule 04.02.2018
comment
цикл while прерывается, как только вы найдете «большее» имя, Адамс заменяется на Yee.that всегда «больше». Таким образом, цикл while всегда будет прерываться после достижения/перемещения Yee.   -  person user85421    schedule 04.02.2018

Ответы (4)


arrow_upward
0
arrow_downward

Есть проблема с алгоритмом при смещении значений. Вам нужно поставить оценки [in-1] = temp; внутри вашего оператора while для смены работы. Я не использовал GradeStudent просто String, но вы можете адаптироваться. Массив оценок был просто для примера.

public static String reportgrades() //this is grade sorted by name 
    {

    String[] grades = {"Evans", "Smith", "Adams", "Hashimoto", 
    "Stimson", "Velasquez", "Lamarque", "Vang", "Creswell", "Yee"};
    String output = "Sorted by name ";
    int in, out;
    String temp; //this is to hold the orginal variable. 
    //for the first letter cycle
    long nElems = grades.length; 
    for (out = 1; out < nElems; out++) {
        in = out;
        while (in > 0 &&  0 < (grades[in - 1].compareTo(grades[in]))) {
            temp = grades[in];
            grades[in] = grades[in-1];
            grades[in-1] = temp;
            in--;
        }    
    }
    for (int j = 0; j < nElems; j++) {
         output += grades[j] + ", ";
    }
    return output;
}
person vladwoguer    schedule 03.02.2018
comment
Обратите внимание, что если вам нужно учитывать Адама и Адама при заказе, вам нужно будет добавить прописные или строчные буквы. - person vladwoguer; 04.02.2018

arrow_upward
0
arrow_downward

Вы используете compareTo в порядке, но вы не сравниваете правильные элементы для сортировки вставками. Вам нужно сравнить элемент, который был в out, с каждым предыдущим элементом. Но после первого шага в вашем цикле вместо этого вы сравниваете только элементы из более раннего, чем out, друг с другом.

Вы можете изменить цикл while для сравнения с temp:

while (in > 0 && 0 < (grades[in - 1].name.compareTo(temp.name))) {

или оставьте это время, но измените цикл, чтобы поменять местами элементы в массиве, а не просто сдвинуть их вправо:

    for (out = 1; out < nElems; out++) {
        in = out;
        while (in > 0 && 0 < (grades[in - 1].name.compareTo(grades[in].name))) {
            // swap grades at in-1 and in
            StudentGrade temp = grades[in];
            grades[in] = grades[in - 1];
            grades[in - 1] = temp;
            in--;
        }
    }
person Peter Moore    schedule 03.02.2018

arrow_upward
0
arrow_downward

Сначала добавьте все имена в список, затем отсортируйте:

Collections.sort(list);
person Ozodbek Kamolov    schedule 03.02.2018

arrow_upward
0
arrow_downward

Я последовал ответу vladwoguer и переместил grades[in-1] = temp; в мой цикл while. Я не осознавал, что на самом деле не перемещал переменную, которую хотел. Я думал, что все должно быть перенесено, прежде чем я снова вставлю исходное имя.

person Grimmjow56    schedule 04.02.2018