Быстрая сортировка Java - возможно ли сравнивать объекты без использования компаратора?

#java #quicksort #comparator

#java #быстрая сортировка #компаратор

Вопрос:

Есть ли способ быстрой сортировки элементов массива в ArrayList и в то же время изменить порядок на ArrayList основе отсортированного массива без использования Comparator<> функции?

     public ArrayList<PatientArray> ageSorter(ArrayList<PatientArray> pa) {
        if (pa.size() <= 1) {
            return pa;
        }

        ArrayList<PatientArray> sorted;
        ArrayList<PatientArray> smaller = new ArrayList<PatientArray>();
        ArrayList<PatientArray> greater = new ArrayList<PatientArray>();

        PatientArray middle = pa.get(0);
        int i;
        PatientArray j;
        for (i = 1; i < pa.size(); i  ) {
            j = pa.get(i);

            if ((new SortAge().compare(j, middle)) < 0) { // this object comparator
                smaller.add(j);
            } else {
                greater.add(j);
            }
        }
        smaller = ageSorter(smaller);
        greater = ageSorter(greater);
        smaller.add(middle);
        smaller.addAll(greater);
        sorted = smaller;

        return sorted;
    }

    class SortAge implements Comparator <PatientArray>{
    public int compare(PatientArray a1, PatientArray a2){
        return a1.age-a2.age;
    }

1. Не совсем уверен, о чем вы спрашиваете, но тот факт, что ваш класс реализует Comparator, является случайным. Интерфейс ничего не добавляет в ваш пример. compare может быть просто методом внутри того же класса, ageSorter что и, или вы можете выполнить a1.age-a2.age встроенное в if-оператор.

Ответ №1:

Самый простой способ избежать использования a Comparator — выполнить сравнение самостоятельно непосредственно в коде быстрой сортировки:

 if (pa.get(i).age < middle.age)

Хотя вы не просили комментариев общего обзора, я отмечу, что в вашем коде много ненужных команд.

 public ArrayList<PatientArray> ageSorter(ArrayList<PatientArray> pa) {
    if (pa.size() <= 1) {
        return pa;
    }

    ArrayList<PatientArray> smaller = new ArrayList<PatientArray>();
    ArrayList<PatientArray> greater = new ArrayList<PatientArray>();

    PatientArray pivot = pa.get(0);
    for (int i = 1; i < pa.size(); i  ) {
        if (pa.get(i).age < pivot.age) {
            smaller.add(j);
        } else {
            greater.add(j);
        }
    }
    smaller = ageSorter(smaller);
    greater = ageSorter(greater);
    smaller.add(middle);
    smaller.addAll(greater);
    return smaller;
}

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

Как указывает @Holger в комментариях ниже, выбор pivot (в качестве первого элемента) также оставляет желать лучшего. Причины и альтернативы объясняются здесь

Хотя технически ваш алгоритм является быстрой сортировкой, он, вероятно, не быстрый.

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

Ответ №2:

Вы можете использовать sort метод для класса List, представленный в Java 8. Итак, ваш метод будет следующим:

 public List<PatientArray> ageSorter(ArrayList<PatientArray> pa) {
   pa.sort(Comparator.comparingInt(a -> a.age));
   return pa;
}

1. Я подозреваю, что OP хочет фактически реализовать алгоритм QS, а не просто вызвать sort .

2. Да, я хочу применить алгоритм быстрой сортировки к моему списку массивов, но без использования компаратора для сравнения моих объектов