Бесконечный цикл / рекурсия при реализации быстрой сортировки в Java

Question

Я пытаюсь реализовать быструю сортировку в java, чтобы посчитать количество выполненных сравнений, но я сталкиваюсь с ситуацией бесконечного цикла / рекурсивного вызова, и я не могу точно понять, откуда это происходит.

Посредством отладки я определил, что внутренний цикл for выполняется сколько раз, и все вводится только в подсписок "less", а затем выполняется рекурсивный вызов быстрой сортировки (less)

    private ArrayList<Comparable> quickSort(ArrayList<Comparable> qList) {
            ArrayList<Comparable> less = new ArrayList<Comparable>();
            ArrayList<Comparable> greater = new ArrayList<Comparable>();
            if (qList.size() <= 1)
                return qList;
            Comparable pivot = qList.get(qList.size() / 2);
            for (int i = 0; i < qList.size(); i++) {
                if ((qList.get(i).compareTo(pivot)) <= 0) {
                    comps++;
                    less.add(qList.get(i));
                } else {
                    comps++;
                    greater.add(qList.get(i));
                }
            }

            ArrayList<Comparable> toReturn = new ArrayList<Comparable>(
                    quickSort(less));
            toReturn.add(pivot);
            toReturn.addAll(quickSort(greater));
            return toReturn;

        }

Если я просто запускаю код со списком размером 20, я получаю эту ошибку

Exception in thread "main" java.lang.StackOverflowError
    at java.util.Arrays.copyOf(Unknown Source)
    at java.util.ArrayList.ensureCapacity(Unknown Source)
    at java.util.ArrayList.add(Unknown Source)
    at file.quickSort(CMSC351P1.thisClass:40)
    at file.quickSort(CMSC351P1.thisClass:48)

Answer 1

Проблема в том, что вы добавляете сам элемент pivot в список 'less', чтобы базовый случай никогда не завершался.

Пример: Вы сортируете список [0, 0] по вашему алгоритму. Элементом pivot является ... 0. Список 'less', который генерирует ваш алгоритм, снова [0, 0], и вы входите в бесконечный цикл.

Answer 2

Вы не исключаете сводку из меньших / больших подсписков - фактически, вы явно включаете ее в набор подсписков. Я подозреваю, что это означает, что во многих случаях вы застряли со списками двух, которые бесконечно сортируются. Вам нужно будет исключить пивот из меньшего подсписка.

Answer 3

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

В некоторый момент, еслиpivot - самый большой элемент в списке, тогда все перейдет к списку «меньше».

Когда вы его вызовите, то же самое произойдет снова.