Я не могу понять, почему я получаю StackOverFlowError

Question

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

public static <E extends Comparable<E>> void quickSort(MyNode<E> first, MyNode<E> last) {
    if(first != last) {
        MyNode<E> pivot = first;
        MyNode<E> currentNode = first.next;
        MyNode<E> previousNode = first;

        while(currentNode.next != last && currentNode.next != null) {
            if (currentNode.element.compareTo(pivot.element) < 0) {
                MyNode<E> temp = new MyNode<E>(currentNode.element);
                previousNode.next = currentNode.next;
                temp.next = first;
                first = currentNode;
            }
            previousNode = previousNode.next;
            currentNode = currentNode.next;
        }
        quickSort(first, pivot);
        quickSort(pivot, last);
    }

}

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

    public static <E extends Comparable<E>> void quickSort(MyNode<E> first, MyNode<E> last) {
    if(first != last && first != null) {
        E pivot = first.element;
        MyNode<E> current = first.next;
        MyNode<E> previous = first;


        while(previous != last && current != null) {
            if (current.element.compareTo(pivot) < 0) {
                previous.next = current.next;
                first = current;
                first.next = previous;
                current = previous.next;
            }
            else {
                previous = previous.next;
                current = current.next;
            }
            //recursive calls will go here... Just want to get the logic right first
        }

    }
}

Answer 1

Основная проблема (полученная ошибка StackruError) заключается в том, что вы не меняете pivot и, следовательно, рекурсивный вызов quickSort(pivot, last); будет так же, как quickSort(first, last); и поэтому first != last всегда будет верно для любого списка размером> 1.

Вы должны сначала установить pivot к среднему элементу, затем сортируйте элементы в соответствии с тем, больше или меньше, чем сводная, а затем рекурсивно вызывайте быструю сортировку для подсписков. Здесь, однако, вы не должны проходить pivot дважды, иначе вы все равно получите переполнение стека.

Предположим, вы в конечном итоге с подсписка только из двух элементов и вы выбираете один как стержень. Один рекурсивный вызов ничего не сделает, так как first = last но другой по существу будет quicksort(first, last), выбрал бы ту же точку и повторить с тем же подсписком.

Так что либо пройти pivot +/- 1 на один из рекурсивных вызовов (так как это связанный список, я бы предложил quicksort(pivot.next, last)) или проверьте, есть ли в подсписке более 2 элементов перед выполнением рекурсии.

Answer 2

С первого взгляда... вы слишком быстро повторяете цикл сортировки, и вы получаете эту ошибку.

пример

private void countUp(int x){
    System.out.println(x);
    countUp(++x);
}

для меня это будет примерно 10541 раз... перед тем как выдать эту ошибку.

Имея это в виду... у вас может быть где-то бесконечный цикл ИЛИ ваш массив слишком велик.