Переполнение стека QuickSort для отсортированных массивов (работает для других наборов данных)

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

Это часть моего курса по структурам данных в первом семестре, поэтому любой обзор кода также будет полезен. Спасибо.

public void quickSort(ArrayList<String> data, int firstIndex, int numberToSort) {
    if (firstIndex < (firstIndex + numberToSort - 1))
        if (numberToSort < 16) {
            insertionSort(data, firstIndex, numberToSort);
        } else {
            int pivot = partition(data, firstIndex, numberToSort);
            int leftSegmentSize = pivot - firstIndex;
            int rightSegmentSize = numberToSort - leftSegmentSize - 1;
            quickSort(data, firstIndex, leftSegmentSize);
            quickSort(data, pivot + 1, rightSegmentSize);
        }
}



public int partition(ArrayList<String> data, int firstIndex, int numberToPartition) {
    int tooBigNdx = firstIndex + 1;
    int tooSmallNdx = firstIndex + numberToPartition - 1;

    String string1 = data.get(firstIndex);
    String string2 = data.get((firstIndex + (numberToPartition - 1)) / 2);
    String string3 = data.get(firstIndex + numberToPartition - 1);
    ArrayList<String> randomStrings = new ArrayList<String>();
    randomStrings.add(string1);
    randomStrings.add(string2);
    randomStrings.add(string3);
    Collections.sort(randomStrings);
    String pivot = randomStrings.get(1);
    if (pivot == string2) {
        Collections.swap(data, firstIndex, (firstIndex + (numberToPartition - 1)) / 2);
    }
    if (pivot == string3) {
        Collections.swap(data, firstIndex, firstIndex + numberToPartition - 1);
    }
    while (tooBigNdx < tooSmallNdx) {
        while ((tooBigNdx < tooSmallNdx) && (data.get(tooBigNdx).compareTo(pivot) <= 0)) {
            tooBigNdx++;
        }
        while ((tooSmallNdx > firstIndex) && (data.get(tooSmallNdx).compareTo(pivot) > 0)) {
            tooSmallNdx--;
        }
        if (tooBigNdx < tooSmallNdx) {// swap
            Collections.swap(data, tooSmallNdx, tooBigNdx);
        }
    }
    if (pivot.compareTo(data.get(tooSmallNdx)) >= 0) {
        Collections.swap(data, firstIndex, tooSmallNdx);
        return tooSmallNdx;
    } else {
        return firstIndex;
    }
}

java algorithm data-structures stack-overflow quicksort
person Nate Schellink    schedule 24.04.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

В вашем методе partition вы иногда используете элемент вне диапазона:

String string1 = data.get(firstIndex);
String string2 = data.get((firstIndex + (numberToPartition - 1)) / 2);
String string3 = data.get(firstIndex + numberToPartition - 1);

(firstIndex + (numberToPartition - 1)) / 2 не является индексом среднего элемента. Это будет (firstIndex + (firstIndex + (numberToPartition - 1))) / 2

= firstIndex + ((numberToPartition - 1) / 2).

На самом деле, если firstIndex > n/2 (где n — количество элементов во входных данных), вы используете элемент с индексом меньше firstIndex. Для отсортированных массивов это означает, что вы выбираете элемент в firstIndex в качестве опорного элемента. Поэтому вы получаете глубину рекурсии в

‹code›Omega(n)‹/code›,

что вызывает переполнение стека для достаточно больших входных данных.

person fabian    schedule 25.04.2015
comment
Спасибо! Это имеет смысл. И мой код теперь работает так, как ожидалось. Если у вас есть время, у меня есть еще один вопрос. Для моего проекта я должен сделать алгоритм максимально эффективным. Поможет ли rand.nextInt() найти три случайных значения, чтобы найти лучшую медиану для несортированных данных, оптимизировать мой код для больших значений n? Или есть более эффективный способ найти полуточную медиану? - person Nate Schellink; 25.04.2015
comment
@NateSchellink: лично я предпочитаю рандомизированную версию быстрой сортировки, поскольку вы не можете придумать ввод в худшем случае. (Худший случай все еще может произойти, но это зависит от сгенерированных случайных чисел). Также избавьтесь от воссоздания 3-элементного ArrayList. Также не так сложно найти медиану 3 без вызова sort, что позволит избежать накладных расходов на вызов этого метода. - person fabian; 25.04.2015

arrow_upward
2
arrow_downward

Вы можете избежать переполнения стека, не слишком меняя алгоритм. Хитрость заключается в том, чтобы оптимизировать хвостовой вызов на самом большом разделе и использовать рекурсию только на самом маленьком. Обычно это означает, что вам нужно изменить if на while. Я не могу сейчас протестировать код Java, но он должен выглядеть примерно так:

public void quickSort(ArrayList<String> data, int firstIndex, int numberToSort) {
    while (firstIndex < (firstIndex + numberToSort - 1))
        if (numberToSort < 16) {
            insertionSort(data, firstIndex, numberToSort);
        } else {
            int pivot = partition(data, firstIndex, numberToSort);
            int leftSegmentSize = pivot - firstIndex;
            int rightSegmentSize = numberToSort - leftSegmentSize - 1;

            //only use recursion for the smallest partition
            if (leftSegmentSize < rightSegmentSize) {
                quickSort(data, firstIndex, leftSegmentSize);
                firstIndex = pivot + 1;
                numberToSort = rightSegmentSize;
            } else {
                quickSort(data, pivot + 1, rightSegmentSize);
                numberToSort = leftSegmentSize;
            }
        }
}

Это гарантирует, что размер стека вызовов будет не более O(log n), потому что при каждом вызове вы используете рекурсию только для массива размером не более n/2.

person Juan Lopes    schedule 25.04.2015
comment
Спасибо за ответ, я считаю, что вы правы в определенных ситуациях, это остановит переполнение стека, но мне нужно более элегантное решение. - person Nate Schellink; 25.04.2015
comment
Это предотвратит переполнение стека во всех случаях. Это установит теоретическую верхнюю границу максимального размера стека вызовов. Но я понимаю вашу точку зрения, реализация медианы медиан также снижает сложность выполнения алгоритма. - person Juan Lopes; 25.04.2015