Java Quicksort сводной выбор

Question

Таким образом, когда я выбираю сводку по-разному, я сталкиваюсь с ошибками переполнения стека при выборе чего-либо, кроме последнего элемента во входящем массиве.При выборе типа «медиана 3» это происходит чаще всего.

public static <T> void quickSort (ArrayList<T> incomingArray, Comparator<? super T> cmp, int start, int end)
{
    if(start >= end) 
        return;

    T pivot = incomingArray.get(start + ((end - start)/2)); <--Stack overflow

    if(cmp.compare(incomingArray.get(start + ((end - start)/2)), incomingArray.get(0)) < 0)
    {
        swap(incomingArray, (start + ((end - start)/2)), 0);
    }
    if(cmp.compare(incomingArray.get(end), incomingArray.get(start + ((end - start)/2))) < 0)
    {
        swap(incomingArray, end, (start + ((end - start)/2)));
    }
    if(cmp.compare(incomingArray.get((start + ((end - start)/2))), incomingArray.get(end)) < 0)
    {
        swap(incomingArray, 0, end);
    }

    swap(incomingArray, (start + ((end - start)/2)), end);

    pivot = incomingArray.get(end);

    int leftBound = 0;
    int rightBound = end - 1;

    while(leftBound < rightBound)
    {
        while(cmp.compare(incomingArray.get(leftBound), pivot) <= 0 && leftBound < rightBound)
            leftBound++;
        while(cmp.compare(incomingArray.get(rightBound), pivot) >= 0 && leftBound < rightBound)
            rightBound--;

        swap(incomingArray, leftBound, rightBound);
    }

    swap(incomingArray, rightBound, end);

    quickSort(incomingArray, cmp, start, leftBound);
    quickSort(incomingArray, cmp, rightBound + 1, end);



}

Вызов swap просто меняет значения в индексных позициях в переданном массиве.

Answer 1

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

Предполагая, что quicksort(start, end) сортирует подмассив из индекса start в индекс end включительно, следующие строки не имеют большого смысла:

if (cmp.compare(incomingArray.get(start + ((end - start) / 2)), incomingArray.get(0)) < 0) {
    swap(incomingArray, (start + ((end - start) / 2)), 0);
}

Здесь в игру вступает индекс 0, который в большинстве случаев находится за пределами от start до end.То же самое со строками

swap(incomingArray, 0, end);

и

int leftBound = 0;

Исправьте проблемы с вашим алгоритмом и попробуйте снова.

Answer 2

Я просто скопировал и вставил ваш код и запустил его для 100 000 номеров, и у меня не возникло проблем переполнения стека.Вы уверены, что ваши функции подкачки и сравнения работают правильно, как и ожидалось?

Answer 3

Первое, что, похоже, не в порядке:

if(cmp.compare(incomingArray.get((start + ((end - start)/2))), incomingArray.get(end)) < 0)
{
    swap(incomingArray, 0, end);
}

сравнивает средний и последний элемент, но в результате меняет местами первый и последний элемент